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设计与实现》