# 双端链表
[TOC=2,3]
链表作为数组之外的一种常用序列抽象，是大多数高级语言的基本数据类型，因为 C 语言本身不支持链表类型，大部分 C 程序都会自己实现一种链表类型，Redis 也不例外 —— 实现了一个双端链表结构。
双端链表作为一种常见的数据结构，在大部分的数据结构或者算法书里都有讲解，因此，这一章关注的是 Redis 双端链表的具体实现，以及该实现的 API ，而对于双端链表本身，以及双端链表所对应的算法，则不做任何解释。
读者如果有需要的话，可以参考维基百科的[双端链表](http://en.wikipedia.org/wiki/Doubly_linked_list) 词条，里面提供了关于双端链表的一些基本信息。
另外，一些书籍，比如[《算法：C 语言实现》](http://book.douban.com/subject/4065258/) 和[《数据结构与算法分析》](http://book.douban.com/subject/1139426/) 则提供了关于双端链表的更详细的信息。
### 双端链表的应用
双端链表作为一种通用的数据结构，在 Redis 内部使用得非常多：既是 Redis 列表结构的底层实现之一，同时为大量 Redis 模块所用，用于构建 Redis 的其他功能。
### 实现 Redis 的列表类型
双端链表还是 Redis 列表类型的底层实现之一，当对列表类型的键进行操作 ——比如执行 [RPUSH](http://redis.readthedocs.org/en/latest/list/rpush.html#rpush "(in Redis 命令参考 v2.8)") 、 [LPOP](http://redis.readthedocs.org/en/latest/list/lpop.html#lpop "(in Redis 命令参考 v2.8)") 或 [LLEN](http://redis.readthedocs.org/en/latest/list/llen.html#llen "(in Redis 命令参考 v2.8)") 等命令时，程序在底层操作的可能就是双端链表。
~~~
redis> RPUSH brands Apple Microsoft Google
(integer) 3
redis> LPOP brands
"Apple"
redis> LLEN brands
(integer) 2
redis> LRANGE brands 0 -1
1) "Microsoft"
2) "Google"
~~~
Note
Redis 列表使用两种数据结构作为底层实现：
1. 双端链表
1. 压缩列表
因为双端链表占用的内存比压缩列表要多，所以当创建新的列表键时，列表会优先考虑使用压缩列表作为底层实现，并且在有需要的时候，才从压缩列表实现转换到双端链表实现。
后续章节会对压缩链表和 Redis 类型做更进一步的介绍。
### Redis 自身功能的构建
除了实现列表类型以外，双端链表还被很多 Redis 内部模块所应用：
- 事务模块使用双端链表依序保存输入的命令；
- 服务器模块使用双端链表来保存多个客户端；
- 订阅/发送模块使用双端链表来保存订阅模式的多个客户端；
- 事件模块使用双端链表来保存时间事件（time event）；
类似的应用还有很多，在后续的章节中我们将看到，双端链表在 Redis 中发挥着重要的作用。
### 双端链表的实现
双端链表的实现由 `listNode` 和 `list` 两个数据结构构成，下图展示了由这两个结构组成的一个双端链表实例：
![digraph list_and_list_node { rankdir=LR; node [shape=record, style = filled, fillcolor = "#95BBE3"]; edge [style = bold]; list_node_1 [label = "<head>listNode |{<prev> prev| value|<next> next}", ]; list_node_2 [label = "<head>listNode |{<prev> prev| value|<next> next}"]; list_node_3 [label = "<head>listNode |{<prev> prev| value|<next> next}"]; list_node_1:next -> list_node_2:head; list_node_2:next -> list_node_3:head; list_node_2:prev -> list_node_1:head; list_node_3:prev -> list_node_2:head; node [width=1.5, style = filled, fillcolor = "#A8E270"]; list [label = "list |<head> head|<tail> tail|<dup> dup|<free> free|<match> match|<len> len"]; list:tail -> list_node_3:head; list:head -> list_node_1:head;}](https://box.kancloud.cn/2015-09-13_55f4effb30beb.svg)
其中， `listNode` 是双端链表的节点：
~~~
typedef struct listNode {
// 前驱节点
struct listNode *prev;
// 后继节点
struct listNode *next;
// 值
void *value;
} listNode;
~~~
而 `list` 则是双端链表本身：
~~~
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;
~~~
注意， `listNode` 的 `value` 属性的类型是 `void *` ，说明这个双端链表对节点所保存的值的类型不做限制。
对于不同类型的值，有时候需要不同的函数来处理这些值，因此， `list` 类型保留了三个函数指针 —— `dup` 、 `free` 和 `match` ，分别用于处理值的复制、释放和对比匹配。在对节点的值进行处理时，如果有给定这些函数，就会调用这些函数。
举个例子：当删除一个 `listNode` 时，如果包含这个节点的 `list` 的 `list->free` 函数不为空，就会先调用删除函数 `list->free(listNode->value)` 来清空节点的值，再执行余下的删除操作（比如说，释放节点）。
另外，从这两个数据结构的定义上，也可以了解到一些行为和性能特征：
- `listNode` 带有 `prev` 和 `next` 两个指针，因此，遍历可以双向进行：从表头到表尾，表尾到表头。
- `list` 保存了 `head` 和 `tail` 两个指针，因此，对链表的表头和表尾进行插入的复杂度都为 \(\theta(1)\) —— 这是高效实现 [LPUSH](http://redis.readthedocs.org/en/latest/list/lpush.html#lpush "(in Redis 命令参考 v2.8)") [http://redis.readthedocs.org/en/latest/list/lpush.html#lpush] 、 [RPOP](http://redis.readthedocs.org/en/latest/list/rpop.html#rpop "(in Redis 命令参考 v2.8)") [http://redis.readthedocs.org/en/latest/list/rpop.html#rpop] 、 [RPOPLPUSH](http://redis.readthedocs.org/en/latest/list/rpoplpush.html#rpoplpush "(in Redis 命令参考 v2.8)") [http://redis.readthedocs.org/en/latest/list/rpoplpush.html#rpoplpush] 等命令的关键。
- `list` 带有保存节点数量的 `len` 属性，所以计算链表长度的复杂度仅为 \(\theta(1)\) ，这也保证了 [LLEN](http://redis.readthedocs.org/en/latest/list/llen.html#llen "(in Redis 命令参考 v2.8)") [http://redis.readthedocs.org/en/latest/list/llen.html#llen] 命令不会成为性能瓶颈。
以下是用于操作双端链表的 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 为双端链表实现了一个[迭代器](http://en.wikipedia.org/wiki/Iterator) [http://en.wikipedia.org/wiki/Iterator] ，这个迭代器可以从两个方向对双端链表进行迭代：
- 沿着节点的 `next` 指针前进，从表头向表尾迭代；
- 沿着节点的 `prev` 指针前进，从表尾向表头迭代；
以下是迭代器的数据结构定义：
~~~
typedef struct listIter {
// 下一节点
listNode *next;
// 迭代方向
int direction;
} listIter;
~~~
`direction` 记录迭代应该从那里开始：
- 如果值为 `adlist.h/AL_START_HEAD` ，那么迭代器执行从表头到表尾的迭代；
- 如果值为 `adlist.h/AL_START_TAIL` ，那么迭代器执行从表尾到表头的迭代；
以下是迭代器的操作 API ，API 的作用以及算法复杂度：
| 函数 | 作用 | 算法复杂度 |
|-----|-----|-----|
| `listGetIterator` | 创建一个列表迭代器 | \(O(1)\) |
| `listReleaseIterator` | 释放迭代器 | \(O(1)\) |
| `listRewind` | 将迭代器的指针指向表头 | \(O(1)\) |
| `listRewindTail` | 将迭代器的指针指向表尾 | \(O(1)\) |
| `listNext` | 取出迭代器当前指向的节点 | \(O(1)\) |
### 小结
- Redis 实现了自己的双端链表结构。
- 双端链表主要有两个作用：
- 作为 Redis 列表类型的底层实现之一；
- 作为通用数据结构，被其他功能模块所使用；
- 双端链表及其节点的性能特性如下：
- 节点带有前驱和后继指针，访问前驱节点和后继节点的复杂度为 \(O(1)\) ，并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行；
- 链表带有指向表头和表尾的指针，因此对表头和表尾进行处理的复杂度为 \(O(1)\) ；
- 链表带有记录节点数量的属性，所以可以在 \(O(1)\) 复杂度内返回链表的节点数量（长度）；
