redis 源码见闻录（二）

双端链表

双端链表是redis list类型的实现之一，另一种是压缩列表。因为双端链表占的内存比较高，一般都是优先压缩列表，有需要时再转换为双端链表。

双端链表的应用范围

1. 事务模块使用双端链表依序保存输入的命令。
2. 服务器模块用来保存多个客户端。
3. 订阅/发送模块来保存订阅模式的多个客户端。
4. 事件模块使用来保存时间事件。

双端链表的数据结构组成

typedef struct listNode {

    // 前驱节点
    struct listNode *prev;

    // 后继节点
    struct listNode *next;

    // 值
    void *value;

} listNode;

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;

可以看到，双端链表里面嵌套了一个双向链表，使用两个指针分别指向了这个双向链表的表头和表尾。所以无论是头插还是尾插，都不用遍历链表，可以直接进行链表的操作，时间复杂度为O(1)，能高效实现lpush,rpop,rpoplpush等命令。
双端链表里还有存储链表节点数量的len变量，那么对链表长度的计算也是O(1)。