Redis 数据结构：链表

• 采用连续或非连续的物理地址
• 不需要预分配存储空间的大小
• 插入和删除的时间复杂度为O(1)
• 查询的时间复杂度为O(n)
• 不会出现溢出等

除此之外
，链表的实现方式也有很多种。比如：单链表，双向链表，循环链表等。

基于链表的特点，Redis也构建了自己的链表实现。其特性类似C语言中的链表，在Reids中，它采用了
无环双端链表。

简称 adlist 

即一个通用的双端链表实现
。

其中，redis的列表键的底层实现之一就有链表。另外还有发布、订阅、慢查询、监视器等均使用到了链表。

二、Redis中的链表List

每个链表都有一个 adlist.h/list 结构
， 结构如下。

typedef stuct list {

    listNode *head; # 表头节点

    listNode *tail; # 表尾节点

    unsigned long len; # 链表所包含的节点数量

    void *(*dup)(void *ptr); # 节点值复制函数

    void *(*free)(void *ptr); # 节点值释放函数

    int (*match) (void *ptr, void *key);     

}list;

由上文代码可以知

• head 用于指向表头节点的指针。

• tail 用于指向表尾节点的指针。同表头指针既可以完成链表双端的特点。

• dup 函数用于复制链表节点所保存的值。

• free 函数用于释放链表节点所保存的值。

• match 函数则用于对比链表节点所保存的值和另一个输入值释放相等。

三、Redis中的链表节点listNode的实现

每个链表节点使用 adlist.h/listNode 结构，
结构如下。

typedef struct listNode {

    struct listNode *prev; # 前置节点

    struct listNode *next; # 后置节点

    void *value; # 节点的值

}listNode;

链表的每个结点都包含如上listNode结构，可通过前置节点和后置节点进行链接，从而形成了一个双端链表，由于表尾指向NULL而并非指向表头。所以称作为双端无环链表。

如上图所示。体现了多个listNode组成的双端无环链表，通过前置指针prev指向节点的上一个地址，通过后置指针next指向下一个节点的地址。

如上图所示，体现了一个链表list 对应了3个listNode节点所组成的链表结构图。

分析上图，Redis的链表list 表头指针head 指向了 listNode的第一个节点，Redis的链表list 表尾指针 tail 指向了 listNode的最后一个节点。list 中的 len 等于 3 说明这个list中包含了 3 个 listNode节点值。另外dup 复制函数和free 释放函数 以
及
match 函数分别指向了各个具体函数的实现。而listNode的第一个节点的前置指针和最后一个节点的后继指针都分别指向了null。

通过以上分析，我们可以总结Redis的链表特点如下：

1）
双端

链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度为O(1)

2）
无环

表头节点的prev指针和表尾节点的next指针都指向了null，对链表的访问以null为终点

3）
带表头指针和表尾指针

通过list结构的head 指针和 tail 指针，程序获取链表的头节点和尾节点的复杂度为O(1)

4）
带链表长度计数器

通过list结构的len用于计数listNode的长度，所以获取链表节点数量的复杂度为O(1)

5）
多态

链表节点使用 void* 指针保存节点的值，并且可以通过list 结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值

四、参考文献

    
《redis设计与实现》