一、說明

鏈表提供了高效的節點重排能力， 以及順序性的節點存取方式， 並且可以通過增刪節點來靈活地調整鏈表的長度。
作爲一種常用數據結構， 鏈表內建在很多高階的程式語言裏面， 因爲Redis使用的C語言並沒有內建這種數據結構， 所以Redis構建了自己的鏈表實現。
鏈表在Redis中的應用非常廣泛， 比如列表鍵的底層實現之一就是鏈表。 當一個列表鍵包含了數量比較多的元素， 又或者列表中包含的元素都是比較長的字串時， Redis就會使用鏈表作爲列表鍵的底層實現。

二、鏈表在redis中的應用

• 鏈表被廣泛用於實現Redis的各種功能， 比如列表鍵、 發佈與訂閱、 慢查詢、監視器等

三、鏈表的定義

每個鏈表節點使用一個adlist.h/listNode結構來表示：

typedef struct listNode {
//
前置節點
struct listNode * prev;
//
後置節點
struct listNode * next;
//
節點的值
void * value;
}listNode;

多個listNode可以通過prev和next指針組成雙端鏈表，如下圖所示：

雖然僅僅使用多個listNode結構就可以組成鏈表， 但使用adlist.h/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;

list結構爲鏈表提供了表頭指針head、 表尾指針tail， 以及鏈表長度計數器len， 而dup、 free和match成員則是用於實現多型鏈表所需的型別特定函數：

• dup函數用於複製鏈表節點所儲存的值；
• free函數用於釋放鏈表節點所儲存的值；
• match函數則用於對比鏈表節點所儲存的值和另一個輸入值是否相等。
  Redis的鏈表實現的特性可以總結如下:
• 雙端： 鏈表節點帶有prev和next指針， 獲取某個節點的前置節點和後置節點的複雜度都是O（ 1） 。
• 無環： 表頭節點的prev指針和表尾節點的next指針都指向NULL， 對鏈表的存取以NULL爲終點。
• 帶表頭指針和表尾指針： 通過list結構的head指針和tail指針， 程式獲取鏈表的表頭節點和表尾節點的複雜度爲O（ 1） 。
• 帶鏈表長度計數器： 程式使用list結構的len屬性來對list持有的鏈表節點進行計數， 程式獲取鏈表中節點數量的複雜度爲O（ 1） 。
• 多型： 鏈表節點使用void*指針來儲存節點值， 並且可以通過list結構的dup、 free、 match三個屬性爲節點值設定型別特定函數， 所以鏈表可以用於儲存各種不同類型的值。

四、總結

• ·每個鏈表節點由一個listNode結構來表示， 每個節點都有一個指向前置節點和後置節點的指針， 所以Redis的鏈表實現是雙端鏈表。
• ·每個鏈表使用一個list結構來表示， 這個結構帶有表頭節點指針、 表尾節點指針， 以及鏈表長度等資訊。