《Redis设计与实现》读书笔记（三） ——Redis中的链表

《Redis设计与实现》读书笔记（三） ——Redis中的链表

（原创内容，转载请注明来源，谢谢）

一、概述

链表在redis底层实现广泛，例如redis的list（列表）数据结构在底层就是用链表来实现的。链表提供了节点重排和顺序节点访问。

除了list，redis的发布订阅、慢查询、监视器等，也使用到了链表。redis还用链表保存多个客户端的状态信息，以及用链表来构建客户端的输出缓冲区。

二、链表和表节点的实现

1、节点结构

链表的节点结构，采用结构体，如下：

typedef structlistNode{
struct listNode *prev;
struct listNode *next;
struct *value;
}

其中prev指向前一个节点，next指向后一个节点，value存储着节点本身的值。多个listNode组成双向链表，如下图所示：

2、链表结构

链表的结构也是采用结构体定义，如下：

typedef structlist{
listNode *head;
listNode *tail;
unsigned long len;
void *(*dup) (void *ptr);
void *(*free) (void *ptr);
int (*match) (void *ptr, void *key);
}

其中head和tail表示链表节点的开始节点和结束节点，len表示链表的长度，dup是节点的值复制函数，free是节点的值释放存储空间函数，match是节点的值比较函数（比较两个值是否相等）。

链表如下图所示：

三、redis链表结构综述

redis的链表特性如下：

1）双向，每个listNode节点带有prev和next指针，可以找到前一个节点和后一个节点，具有双向性。

2）无环，list链表的head节点的prev和tail节点的next指针都是指向null。

3）带表头指针和尾指针，即上述的head和tail，获取头指针和尾指针的时间复杂度O(1)。

4）带链表长度计数器，即list的len属性，记录节点个数，因此获取节点个数的时间复杂度O(1)。

5）多态，链表使用void*指针来保存节点的值，可以通过list的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存不同类型的值。

四、总结

链表广泛用于redis的list、发布订阅、慢查询、监视器等地方；链表的每个节点由listNode结构实现，包含前置节点、后置节点指针以及节点值；链表本身由list结构实现，包含头尾指针、链表长度、链表的比较、复制、释放空间函数；另外redis的链表是双向、无环，通过为链表设定不同类型的特定函数，可以保存不同的值。

——written by linhxx 2017.08.29