链表在redis中使用非常频繁，常用的list数据就是使用链表数据结构，除此之外，还有发布与订阅、监视器也用到了链表。

数据结构

redis的链表由多个链表节点组成，每个链表节点分别保存了前驱和后继节点，形成了一个双向链表。最终的链表会包含一个头节点、尾节点以及链表长度。具体定义如下。

1、链表节点

typedef struct listNode {
    // 前驱节点
    struct listNode *prev;
    // 后继节点
    struct listNode *next;
    // 节点数据
    void *value;
} listNode;

2、链表

typedef struct list {
    // 链表头
    listNode *head;
    // 链表尾
    listNode *tail;
    // 链表包含的节点数量
    unsigned long len;
    // 节点复制函数
    void *(*dup)(void *ptr);
    // 节点释放函数
    void (*free)(void *ptr);】
    // 节点比较函数
    int (*match)(void *ptr, void *key);
} list;

特点

1、双端。每个节点都有前驱和后继节点。

2、无环。链表头节点的前驱和链表的尾节点的后继都是null。

3、自带链表长度。查找链表长度为O(1)。

4、多态。用户可以自己定义复制、释放以及比较函数。

源码

1、链表初始化

/* Create a new list. The created list can be freed with
 * listRelease(), but private value of every node need to be freed
 * by the user before to call listRelease(), or by setting a free method using
 * listSetFreeMethod.
 *
 * On error, NULL is returned. Otherwise the pointer to the new list. */
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;
}

2、增加节点

节点的增加操作可以在头和尾都能进行。

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;
}