链表在redis的应用
由于redis的c语言没有内置链表结构类型，因此redis自身实现了一套链表结构。链表主要应用在几个方面：
- 应用于较长的list结构中
- 发布与订阅
- 监视器
- 保存多个客户端状态信息等等
链表在redis中的实现
我们翻到源码src/adlist.h中的listNode结构体，这个结构体也就是链表节点的实现：
/*
* 双端链表节点
*/
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
可以看到，如果画成图，那么多个listNode就会变成这样的一个链表：
image.png
为了操作更方便，redis还实现了一个链表
list，源码位于src/adlist.h的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：用来比对节点值，通常用来查找某个值是否在链表中
那么，为什么要抽出这三个成独立的字段呢？答案就是为了多态，我们都知道void*在C语言是表示任意类型的指针，加上链表节点的value也是用void*保存的，因此通过dup、free、match三个字段函数就可以操作各种类型的值，也让链表节点能够保存任何类型的值了。
redis中链表的特性总结
总体来说，redis的链表结构非常简单高效，主要体现以下几方面：
- 双端链表。每个链表节点
listNode都包含了prev和next字段，用来指向该节点前一个节点和后一个节点，这样可以使得节点查找前一个和后一个节点的计算复杂度变为O(1)。 - 无环。
listNode的prev和next字段都是指向NULL，因此链表是无环的。 - 带表头的表尾指针。链表
list带有head和tail指针，使得查找链表的表头和表尾节点的计算复杂度变为O(1)。 - 链表长度计算器。链表
list有一个字段len，使得计算链表长度的复杂度变为O(1)，而不用通过遍历链表来获取总长度。
文章参考自：<<Redis设计与实现>> 第二版
