雙端鏈表

鏈表作為數(shù)組之外的一種常用序列抽象，是大多數(shù)高級(jí)語(yǔ)言的基本數(shù)據(jù)類型，因?yàn)?C 語(yǔ)言本身不支持鏈表類型，大部分 C 程序都會(huì)自己實(shí)現(xiàn)一種鏈表類型，Redis 也不例外 —— 實(shí)現(xiàn)了一個(gè)雙端鏈表結(jié)構(gòu)。

雙端鏈表作為一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，在大部分的數(shù)據(jù)結(jié)構(gòu)或者算法書(shū)里都有講解，因此，這一章關(guān)注的是 Redis 雙端鏈表的具體實(shí)現(xiàn)，以及該實(shí)現(xiàn)的 API ，而對(duì)于雙端鏈表本身，以及雙端鏈表所對(duì)應(yīng)的算法，則不做任何解釋。

讀者如果有需要的話，可以參考維基百科的雙端鏈表 詞條，里面提供了關(guān)于雙端鏈表的一些基本信息。

另外，一些書(shū)籍，比如《算法：C 語(yǔ)言實(shí)現(xiàn)》 和《數(shù)據(jù)結(jié)構(gòu)與算法分析》 則提供了關(guān)于雙端鏈表的更詳細(xì)的信息。

雙端鏈表的應(yīng)用

雙端鏈表作為一種通用的數(shù)據(jù)結(jié)構(gòu)，在 Redis 內(nèi)部使用得非常多：既是 Redis 列表結(jié)構(gòu)的底層實(shí)現(xiàn)之一，同時(shí)為大量 Redis 模塊所用，用于構(gòu)建 Redis 的其他功能。

實(shí)現(xiàn) Redis 的列表類型

雙端鏈表還是 Redis 列表類型的底層實(shí)現(xiàn)之一，當(dāng)對(duì)列表類型的鍵進(jìn)行操作 ——比如執(zhí)行 RPUSH 、 LPOP 或 LLEN 等命令時(shí)，程序在底層操作的可能就是雙端鏈表。

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 列表使用兩種數(shù)據(jù)結(jié)構(gòu)作為底層實(shí)現(xiàn)：

1. 雙端鏈表
2. 壓縮列表

因?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)。

后續(xù)章節(jié)會(huì)對(duì)壓縮鏈表和 Redis 類型做更進(jìn)一步的介紹。

Redis 自身功能的構(gòu)建

除了實(shí)現(xiàn)列表類型以外，雙端鏈表還被很多 Redis 內(nèi)部模塊所應(yīng)用：

• 事務(wù)模塊使用雙端鏈表依序保存輸入的命令；
• 服務(wù)器模塊使用雙端鏈表來(lái)保存多個(gè)客戶端；
• 訂閱/發(fā)送模塊使用雙端鏈表來(lái)保存訂閱模式的多個(gè)客戶端；
• 事件模塊使用雙端鏈表來(lái)保存時(shí)間事件（time event）；

類似的應(yīng)用還有很多，在后續(xù)的章節(jié)中我們將看到，雙端鏈表在 Redis 中發(fā)揮著重要的作用。

雙端鏈表的實(shí)現(xiàn)

雙端鏈表的實(shí)現(xiàn)由 listNode 和 list 兩個(gè)數(shù)據(jù)結(jié)構(gòu)構(gòu)成，下圖展示了由這兩個(gè)結(jié)構(gòu)組成的一個(gè)雙端鏈表實(shí)例：