雙端鏈表 · Redis 設計與實現（第一版）

# 雙端鏈表 [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)\) 復雜度內返回鏈表的節點數量（長度）；