数据结构

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

多个 listNode 可以通过 prev 和 next 指针组成双端链表， 如图 3-1 所示：

图 3-1

虽然仅仅使用多个 listNode 结构就可以组成链表， 但使用 list 来持有链表的话， 操作起来会更方便：

struct list {
    listNode *head; // 表头节点
    listNode *tail; // 表尾节点
    unsigned long len; // 链表所包含的节点数量
};

图 3-2 是由一个 list 结构和三个 listNode 结构组成的链表：

图 3-2

Redis 的链表实现的特性可以总结如下：

• 双端： 链表节点带有 prev 和 next 指针， 获取某个节点的前置节点和后置节点的复杂度都是 O(1)
• 无环： 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL ， 对链表的访问以 NULL 为终点
• 带表头指针和表尾指针： 通过 list 结构的 head 指针和 tail 指针， 程序获取链表的表头节点和表尾节点的复杂度为 O(1)
• 带链表长度计数器： 程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数， 程序获取链表中节点数量的复杂度为 O(1)