實(shí)現(xiàn) Redis 的列表類型
<pre>
雙端鏈表還是 Redis 列表類型的底層實(shí)現(xiàn)之一甲捏， 當(dāng)對(duì)列表類型的鍵進(jìn)行操作 —— 比如執(zhí)行 [RPUSH]魁淳、 [LPOP] 或 [LLEN] 等命令時(shí)， 程序在底層操作的可能就是雙端鏈表哩罪。
</pre>
<pre>
Redis 列表使用兩種數(shù)據(jù)結(jié)構(gòu)作為底層實(shí)現(xiàn)：
雙端鏈表
壓縮列表
因?yàn)殡p端鏈表占用的內(nèi)存比壓縮列表要多呀狼， 所以當(dāng)創(chuàng)建新的列表鍵時(shí)， 列表會(huì)優(yōu)先考慮使用壓縮列表作為底層實(shí)現(xiàn)里烦， 并且在有需要的時(shí)候凿蒜， 才從壓縮列表實(shí)現(xiàn)轉(zhuǎn)換到雙端鏈表實(shí)現(xiàn)。
</pre>
Redis 自身功能的構(gòu)建
<pre>
除了實(shí)現(xiàn)列表類型以外胁黑， 雙端鏈表還被很多 Redis 內(nèi)部模塊所應(yīng)用：
事務(wù)模塊使用雙端鏈表依序保存輸入的命令废封；
服務(wù)器模塊使用雙端鏈表來保存多個(gè)客戶端；
訂閱/發(fā)送模塊使用雙端鏈表來保存訂閱模式的多個(gè)客戶端丧蘸；
事件模塊使用雙端鏈表來保存時(shí)間事件（time event）漂洋；
類似的應(yīng)用還有很多 。
</pre>
其中力喷， listNode 是雙端鏈表的節(jié)點(diǎn)：
<pre>
typedef struct listNode {
// 前驅(qū)節(jié)點(diǎn)
struct listNode *prev;
// 后繼節(jié)點(diǎn)
struct listNode *next;
// 值
void *value;
} listNode;
</pre>
而 list 則是雙端鏈表本身：
<pre>
typedef struct list {
// 表頭指針
listNode *head;
// 表尾指針
listNode *tail;
// 節(jié)點(diǎn)數(shù)量
unsigned long len;
// 復(fù)制函數(shù)
void (dup)(void ptr);
// 釋放函數(shù)
void (free)(void ptr);
// 比對(duì)函數(shù)
int (match)(void *ptr, void *key);
} list;
</pre>
注意刽漂， listNode 的 value 屬性的類型是 void * ，說明這個(gè)雙端鏈表對(duì)節(jié)點(diǎn)所保存的值的類型不做限制弟孟。
<pre>
對(duì)于不同類型的值贝咙，有時(shí)候需要不同的函數(shù)來處理這些值，因此拂募， list 類型保留了三個(gè)函數(shù)指針 —— dup 庭猩、 free 和 match 乌奇，分別用于處理值的復(fù)制、釋放和對(duì)比匹配眯娱。在對(duì)節(jié)點(diǎn)的值進(jìn)行處理時(shí)礁苗，如果有給定這些函數(shù)，就會(huì)調(diào)用這些函數(shù)徙缴。
舉個(gè)例子：當(dāng)刪除一個(gè) listNode 時(shí)试伙，如果包含這個(gè)節(jié)點(diǎn)的 list 的 list->free 函數(shù)不為空，就會(huì)先調(diào)用刪除函數(shù) list->free(listNode->value) 來清空節(jié)點(diǎn)的值于样，再執(zhí)行余下的刪除操作（比如說疏叨，釋放節(jié)點(diǎn)）。
另外穿剖，從這兩個(gè)數(shù)據(jù)結(jié)構(gòu)的定義上蚤蔓，也可以了解到一些行為和性能特征：
listNode 帶有 prev 和 next 兩個(gè)指針，因此糊余，遍歷可以雙向進(jìn)行：從表頭到表尾秀又，表尾到表頭。
list 保存了 head 和 tail 兩個(gè)指針贬芥，因此吐辙，對(duì)鏈表的表頭和表尾進(jìn)行插入的復(fù)雜度都為 θ(1)θ(1) —— 這是高效實(shí)現(xiàn) LPUSH 、 RPOP 蘸劈、 RPOPLPUSH 等命令的關(guān)鍵昏苏。
list 帶有保存節(jié)點(diǎn)數(shù)量的 len 屬性，所以計(jì)算鏈表長度的復(fù)雜度僅為 θ(1)θ(1) 威沫，這也保證了 LLEN 命令不會(huì)成為性能瓶頸贤惯。
</pre>
以下是用于操作雙端鏈表的 API ，它們的作用以及算法復(fù)雜度：
迭代器
<pre>
Redis 為雙端鏈表實(shí)現(xiàn)了一個(gè)迭代器 棒掠， 這個(gè)迭代器可以從兩個(gè)方向?qū)﹄p端鏈表進(jìn)行迭代：
沿著節(jié)點(diǎn)的 next 指針前進(jìn)孵构，從表頭向表尾迭代；
沿著節(jié)點(diǎn)的 prev 指針前進(jìn)句柠，從表尾向表頭迭代浦译；
以下是迭代器的數(shù)據(jù)結(jié)構(gòu)定義：
typedef struct listIter {
// 下一節(jié)點(diǎn)
listNode *next;
// 迭代方向
int direction;
} listIter;
direction 記錄迭代應(yīng)該從那里開始：
如果值為 adlist.h/AL_START_HEAD ，那么迭代器執(zhí)行從表頭到表尾的迭代溯职；
如果值為 adlist.h/AL_START_TAIL ，那么迭代器執(zhí)行從表尾到表頭的迭代帽哑；
</pre>
以下是迭代器的操作 API 谜酒，API 的作用以及算法復(fù)雜度：
小結(jié)
<code>
Redis 實(shí)現(xiàn)了自己的雙端鏈表結(jié)構(gòu)。
雙端鏈表主要有兩個(gè)作用：
作為 Redis 列表類型的底層實(shí)現(xiàn)之一妻枕；
作為通用數(shù)據(jù)結(jié)構(gòu)僻族，被其他功能模塊所使用粘驰；
雙端鏈表及其節(jié)點(diǎn)的性能特性如下：
節(jié)點(diǎn)帶有前驅(qū)和后繼指針，訪問前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)的復(fù)雜度為 O(1)O(1) 述么，并且對(duì)鏈表的迭代可以在從表頭到表尾和從表尾到表頭兩個(gè)方向進(jìn)行蝌数；
鏈表帶有指向表頭和表尾的指針，因此對(duì)表頭和表尾進(jìn)行處理的復(fù)雜度為 O(1)O(1) 度秘；
鏈表帶有記錄節(jié)點(diǎn)數(shù)量的屬性顶伞，所以可以在 O(1)O(1) 復(fù)雜度內(nèi)返回鏈表的節(jié)點(diǎn)數(shù)量（長度）；
</code>
