鏈表

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

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

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

舉個例子， 以下展示的?integers?列表鍵包含了從?1?到?1024?共一千零二十四個整數(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?列表鍵的底層實現(xiàn)就是一個鏈表， 鏈表中的每個節(jié)點都保存了一個整數(shù)值。

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

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

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