# Redis Internal Data Structure : Doubly Linked List

August 14, 2014
Author：Eric
Declaration: this work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. # Introduction

Almost every programmer uses list in their code, so does Redis Author. And there is a simple implementation for this widely used data structure.

It looks like: # Implementation

## Data Structure

Here is the list node structure, be careful about the value type, it is void*.

``````// list node
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value; // list node data
} listNode;
``````

And here is the list itself. There is a member len to record list node numbers so that we can get list length in O(1) time. Also, three function pointers used to deal with value in list node.

``````// list itself
typedef struct list {
listNode *tail;
void *(*dup)(void *ptr); // used to copy list node
void (*free)(void *ptr); // used to release list node
int (*match)(void *ptr, void *key); // used to compare list node
unsigned long len; // list length
} list;
``````

For convenience, adlist provides an iterator to traverse list node.

``````// list iterator
typedef struct listIter {
listNode *next;
int direction; // AL_START_HEAD or AL_START_TAIL
} listIter;
``````

We can use functions listGetIterator and listNext to traverse list, like this:

``````iter = listGetIterator(list,direction);
while ((node = listNext(iter)) != NULL) {
doSomething(listNodeValue(node));
``````

## Initialization

``````list *listCreate(void)
{
struct list *list;

if ((list = zmalloc(sizeof(*list))) == NULL)
return NULL;
list->len = 0;
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;
}
``````

## Destroy

``````void listRelease(list *list)
{
unsigned long len;
listNode *current, *next;

len = list->len;
while(len--) {
next = current->next;
if (list->free) list->free(current->value);
zfree(current);
current = next;
}
zfree(list);
}
``````

# ALL APIs

This simple data structure is easy to use and understand compared with Linux kernel list. All APIs are here:

``````list *listCreate(void);
void listRelease(list *list);