redis 链表

链表在列表对象、发布订阅、慢查询、监视器等功能都出现过。redis服务器本身还用链表保存多个客户端的状态信息，以及构建客户端输出缓冲区(output buffer)。

链表和链表节点的实现

链表节点结构由adlist.h/listNode来表示：

/* Node, List, and Iterator are the only data structures used currently. */

typedef struct listNode {
    struct listNode *prev;   //前直节点
    struct listNode *next;   //后置节点
    void *value;
} listNode;

可以看出多个链表节点可以组成一个双向链表。但是redis定义了链表结构list，操作起来更方便：

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;

dup、free、match 成员是用于实现多态链表所需的类型特定函数：

• dup 函数用于复制链表节点保存的值
• free 用于释放节点保存的值
• match 用于对比节点保存的值和另一个输入的值是否相等

list结构如图所示：

redis链表的特性总结如下：

1. 双向的：节点包含prev指针和next指针，获取某个节点的前置节点和后置节点的时间复杂度都是O(1).
2. 无环：表头的前置指针和表尾的后置指针都指向NULL，链表访问以NULL为终点.
3. 带表头指针和表尾指针：通过list的head指针和tail指针，获取头结点和尾节点的时间复杂度为O(1).
4. 带链表长度计数器：list的len属性对节点计数，获取链表长度的时间复杂度为O(1).
5. 多态：链表节点使用void *指针来保存节点值，再加上list结构的三个方法，使得链表可以保存不同类型的值.