链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度，但是由于C语言没有链表的数据结构，所以Redis的链表是自己定义的结构。
链表的数据结构
链表是由一个个链表节点加上一些属性和函数组成的。
链表节点结构
链表单节点的数据结构如下，包含三部分属性，prev、next以及value，用来描述一个链表单节点的结构体：
typedef struct listNode { // 前置节点 struct listNode *prev; // 后置节点 struct listNode *next; // 节点的值 void *value; } listNode;
示例如下图所示：
链表结构
同时Redis为了方便的操作链表，提供了一个list结构来持有链表，也就是我们的链表结构，如下所示
list结构为链表提供了表头指针head、表尾指针tail，以及链表长度计数器len，而dup、free和match成员则是用于实现多态链表所需的类型特定函数：
- dup函数用于复制链表节点所保存的值
- free函数用于释放链表节点所保存的值
- match函数则用于对比链表节点所保存的值和另一个输入值是否相等
用代码来描述如下所示：
typedef struct list{ //表头节点 listNode *head; //表尾节点 listNode *tail; //链表所包含的节点数量 unsigned long len; //节点值复制函数 void *(*dup)(void *ptr); //节点值释放函数 void *(*free)(void *ptr); //节点值对比函数 int (*match)(void *ptr,void *key); }list;
链表结构优势
链表结构的优势其实在很多语言中都有体现，在Redis这里由于特殊的设计结构，又有些不一样的地方，总而言之如下：
- 双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O（1）
- 无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点
- 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O（1）
- 带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O（1）
- 多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值
正是由于这些优势，链表编码有广泛的用途：比如Redis列表数据对象、发布与订阅、慢查询、监视器等
链表常用API
链表的常用API如下所示，可以看到大多数操作都是O（1）的，可以说Redis的数据结构设计都是以牺牲空间为代价追求时间的，速度一定要快，我是缓存我一定要快！
参考《Redis的设计与实现》、Redis数据结构——链表
