Redis数据结构：链表
概要
Redis的列表键采用了两种底层数据结构实现，分别是：
- 双端链表
- 压缩列表
压缩列表占用更少的存储空间，针对小整数或者短字符串，Redis会优先使用压缩列表来存储列表键。但要注意的是，压缩列表不仅仅被作为了列表键的底层实现，也用作了哈希键的底层实现。所以压缩列表将在另一篇博文中单独讲解，本文主要讲解双端链表。
双端链表作为列表键的底层实现之一，当列表键元素较多，或者存储都是长度较长的字符串时，Redis会采用双端链表来作为列表键的实现。
除了实现列表键以外， 双端链表还被很多 Redis 内部模块所应用：
- 事务模块使用双端链表依序保存输入的命令
- 服务器模块使用双端链表来保存多个客户端
- 订阅/发送模块使用双端链表来保存订阅模式的多个客户端
- 事件模块使用双端链表来保存时间事件（time event）
双端链表具体实现
链表节点
xxxxxxxxxxtypedef struct listNode {// 前驱节点struct listNode *prev;// 后继节点struct listNode *next;// 值void *value;} listNode;要特别注意的是，value的类型为
void *，这意味着它可以是任何类型。链表本身
虽然有了链表节点，我们就已经可以表示一个链表了。但Redis额外封装了一层，增加
list结构，来表示链表本身。这样做的好处是，在list可以对链表做更多额外定义，更加灵活方便。xxxxxxxxxxtypedef struct list {// 表头指针listNode *head;// 表尾指针listNode *tail;// 节点数量unsigned long len;// 复制函数：用于复制链表中的值void *(*dup)(void *ptr);// 释放函数：用于释放链表中的值void (*free)(void *ptr);// 比对函数：用来比对链表中的值和输入进来的值是否相等。int (*match)(void *ptr, void *key);} list;
双端链表API
| 函数 | 作用 | 算法复杂度 |
|---|---|---|
listCreate | 创建新链表 | O(1) |
listRelease | 释放链表，以及该链表所包含的节点 | O(N) |
listDup | 创建给定链表的副本 | O(N) |
listRotate | 取出链表的表尾节点，并插入到表头 | O(1) |
listAddNodeHead | 将包含给定值的节点添加到链表的表头 | O(1) |
listAddNodeTail | 将包含给定值的节点添加到链表的表尾 | O(1) |
listInsertNode | 将包含给定值的节点添加到某个节点的之前或之后 | O(1) |
listDelNode | 删除给定节点 | O(1) |
listSearchKey | 在链表中查找和给定 key 匹配的节点 | O(N) |
listIndex | 给据给定索引，返回列表中相应的节点 | O(N) |
listLength | 返回给定链表的节点数量 | O(1) |
listFirst | 返回链表的表头节点 | O(1) |
listLast | 返回链表的表尾节点 | O(1) |
listPrevNode | 返回给定节点的前一个节点 | O(1) |
listNextNode | 返回给定节点的后一个节点 | O(1) |
listNodeValue | 返回给定节点的值 | O(1) |
总结
Redis的链表具有如下特性
- 双端：有前尾指针，获取一个节点的前后的复杂度均为O(1)
- 无环
- 带表头指针和表尾指针。获取整个链表表头节点和表尾节点复杂度均为O(1)
- 获取节点长度复杂度O(1)
- 多态：链表节点使用
void *来保存值，并且在list结构设置dup、free、match三个属性来为节点设置特定类型的处理函数，使得链表可以保存不同类型的值。
参考
- 书籍《Redis设计与实现》