Redis provides a generic doubly linked list implementation, which is widely used in Redis. If a list key involves two many elements or there are many long strings in the list, Redis will apply linked list for it. Publish-subscribe, slow query, monitor also make use of linked list. Redis keeps the states of clients in linked list, and client’s output buffer use it too.

This post will plough into the implementation of doubly linked list.

The code analyzed in this post is based on 5.0.0

Node and List

Each node in the doubly list is represented by a listNode in adlist.h.

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

Multiple nodes can constitute a linked list with next pointing to their next nodes and prev pointing to the previous nodes.

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

The features of this linked list can be concluded as following:

Doubly with prev and next pointer. It’s easy to get the previous or next node of a specified node.
No cycle. The prev of head and next of tail point to None.
Two pointers making it effortless to get the head or tail.
Node counter. len attribute is updated every times when the length changes.
Polymorphism. The value of node is stored in void*, and dup, free, match can change its value to a different type.

Functions Implemented as Macros

The time complexity of these functions is O(1).

#define listLength(l) ((l)->len)
#define listFirst(l) ((l)->head)
#define listLast(l) ((l)->tail)
#define listPrevNode(n) ((n)->prev)
#define listNextNode(n) ((n)->next)
#define listNodeValue(n) ((n)->value)

#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))

#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

Create a List

When creating a new list, only the header of list is allocated, the other member variables are assigned to NULL or 0.

// Time complexity: O(1)

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

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

The created list can be freed with AlFreeList(), but private value of every node need to be freed by the user before to call AlFreeList().

Remove All Elements

listEmpty(list*) is called to remove all the elements from the list but not destroy the list itself.

It costs O(n) time complexity because it frees each node in a traversal. if free function is available, it will be used to release the value of every node. After that, the memory of the node will be collected.

// Time complexity: O(n)

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

    current = list->head;
    len = list->len;
    while(len--) {
        next = current->next;
        if (list->free) list->free(current->value);
        zfree(current);
        current = next;
    }
    list->head = list->tail = NULL;
    list->len = 0;
}

While listRelease(list*) free the whole list including the header.

void listRelease(list *list)
{
    listEmpty(list);
    zfree(list);
}

Add a New Head

listAddNodeHead add a new node to the list as the new head. If the list is empty (list->len == 0), the new node will be the only node with head and tail pointing to it. Or, the old head will be moved after the new node and pointers should be updated too.

// Time complexity: O(1)

list *listAddNodeHead(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    list->len++;
    return list;
}

Insert a Node

The situation becomes more complicated if you want to insert a new node. Note that after is indicator whether the new node is inserted before or after old_node.

If you insert a node before old_node, you may update the head of the list. Whereas the tail of the list may be modified if you insert after old_node.

// Time complexity: O(1)

list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (after) {
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) {
            list->tail = node;
        }
    } else {
        node->next = old_node;
        node->prev = old_node->prev;
        if (list->head == old_node) {
            list->head = node;
        }
    }
    if (node->prev != NULL) {
        node->prev->next = node;
    }
    if (node->next != NULL) {
        node->next->prev = node;
    }
    list->len++;
    return list;
}

Remove a Node

If you remove the specified node from the specified list, you need to call listDelNode function. Before freeing the value and memory space of the node, you must change the pointers of its previous and next nodes. And the length also should be updated after your deletion.

// Time complexity: O(1)

void listDelNode(list *list, listNode *node)
{
    if (node->prev)
        node->prev->next = node->next;
    else
        list->head = node->next;
    if (node->next)
        node->next->prev = node->prev;
    else
        list->tail = node->prev;
    if (list->free) list->free(node->value);
    zfree(node);
    list->len--;
}

Returns a List Iterator

listGetIterator returns a list iterator iter. After the initialization every call to listNext() will return the next element of the list.

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

listIter *listGetIterator(list *list, int direction)
{
    listIter *iter;

    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

listNode *listNext(listIter *iter)
{
    listNode *current = iter->next;

    if (current != NULL) {
        if (iter->direction == AL_START_HEAD)
            iter->next = current->next;
        else
            iter->next = current->prev;
    }
    return current;
}

Rotate the List

Rotating the list means removing the tail node and inserting it to the head.

// Time complexity: O(1)

void listRotate(list *list) {
    listNode *tail = list->tail;

    if (listLength(list) <= 1) return;

    /* Detach current tail */
    list->tail = tail->prev;
    list->tail->next = NULL;
    /* Move it as head */
    list->head->prev = tail;
    tail->prev = NULL;
    tail->next = list->head;
    list->head = tail;
}

Join Two Lists

listJoin(list *l, list *o) adds all the elements of the list o at the end of the list l. The list o remains empty but otherwise valid.

// Time complexity: O(1)

void listJoin(list *l, list *o) {
    if (o->head)
        o->head->prev = l->tail;

    if (l->tail)
        l->tail->next = o->head;
    else
        l->head = o->head;

    if (o->tail) l->tail = o->tail;
    l->len += o->len;

    /* Setup other as an empty list. */
    o->head = o->tail = NULL;
    o->len = 0;
}

Node and List#

Functions Implemented as Macros#

Create a List#

Remove All Elements#

Add a New Head#

Insert a Node#

Remove a Node#

Returns a List Iterator#

Rotate the List#

Join Two Lists#