鏈表

鏈表

鏈表提供了高效的節(jié)點(diǎn)重排能力， 以及順序性的節(jié)點(diǎn)訪問(wèn)方式， 并且可以通過(guò)增刪節(jié)點(diǎn)來(lái)靈活地調(diào)整鏈表的長(zhǎng)度。

作為一種常用數(shù)據(jù)結(jié)構(gòu)， 鏈表內(nèi)置在很多高級(jí)的編程語(yǔ)言里面， 因?yàn)?Redis 使用的 C 語(yǔ)言并沒(méi)有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)， 所以 Redis 構(gòu)建了自己的鏈表實(shí)現(xiàn)。

鏈表在 Redis 中的應(yīng)用非常廣泛， 比如列表鍵的底層實(shí)現(xiàn)之一就是鏈表： 當(dāng)一個(gè)列表鍵包含了數(shù)量比較多的元素， 又或者列表中包含的元素都是比較長(zhǎng)的字符串時(shí)， Redis 就會(huì)使用鏈表作為列表鍵的底層實(shí)現(xiàn)。

舉個(gè)例子， 以下展示的?integers?列表鍵包含了從?1?到?1024?共一千零二十四個(gè)整數(shù)：

redis> LLEN integers
(integer) 1024

redis> LRANGE integers 0 10
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
6) "6"
7) "7"
8) "8"
9) "9"
10) "10"
11) "11"

integers?列表鍵的底層實(shí)現(xiàn)就是一個(gè)鏈表， 鏈表中的每個(gè)節(jié)點(diǎn)都保存了一個(gè)整數(shù)值。

除了鏈表鍵之外， 發(fā)布與訂閱、慢查詢、監(jiān)視器等功能也用到了鏈表， Redis 服務(wù)器本身還使用鏈表來(lái)保存多個(gè)客戶端的狀態(tài)信息， 以及使用鏈表來(lái)構(gòu)建客戶端輸出緩沖區(qū)（output buffer）， 本書后續(xù)的章節(jié)將陸續(xù)對(duì)這些鏈表應(yīng)用進(jìn)行介紹。

本章接下來(lái)的內(nèi)容將對(duì) Redis 的鏈表實(shí)現(xiàn)進(jìn)行介紹， 并列出相應(yīng)的鏈表和鏈表節(jié)點(diǎn) API 。

因?yàn)橐呀?jīng)有很多優(yōu)秀的算法書籍對(duì)鏈表的基本定義和相關(guān)算法進(jìn)行了詳細(xì)的講解， 所以本章不會(huì)介紹這些內(nèi)容， 如果不具備關(guān)于鏈表的基本知識(shí)的話， 可以參考《算法：C 語(yǔ)言實(shí)現(xiàn)（第 1 ～ 4 部分）》一書的 3.3 至 3.5 節(jié)， 或者《數(shù)據(jù)結(jié)構(gòu)與算法分析：C 語(yǔ)言描述》一書的 3.2 節(jié)， 又或者《算法導(dǎo)論（第三版）》一書的 10.2 節(jié)。