1. 概述

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

• 作為一種常用數據結構，鏈表內置在很多高級的編程語言里面，因為Redis使用的C語言并沒有內置這種數據結構，所以Redis構建了自己的鏈表實現。

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

• 除了鏈表鍵之外，發布與訂閱、慢查詢、監視器等功能也用到了鏈表，Redis服務器本身還使用鏈表來保存多個客戶端的狀態信息，以及使用鏈表來構建客戶端輸出緩沖區output buffer )。

2. 鏈表和鏈表節點的實現

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

typedef struct listNode {
    
    //前置節點
    struct listNode * prev;

    //后置節點
    struct listNode * next;

    //節點的值
    void * value;
    
}listNode;

• 僅有多個鏈表節點可以組成鏈表

• ?使用adlist.h/list來持有鏈表，操作起來會更方便

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

1. dup函數用于復制鏈表節點所保存的值
2. free函數用于釋放鏈表節點所保存的值
3. match函數則用于對比鏈表節點所保存的值和另一個輸入值是否相等

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結構和三個listNode結構組成的鏈表

• ?Redis中鏈表實現的特性總結

雙端:鏈表節點帶有prev和next指針，獲取某個節點的前置節點和后置節點的復雜度都是O(1)。

無環:表頭節點的prev指針和表尾節點的next指針都指向NULL，對鏈表的訪問以NULL為終點。

帶表頭指針和表尾指針:通過list結構的head指針和tail指針，程序獲取鏈表的表頭節點和表尾節點的復雜度為O(1)。

帶鏈表長度計數器:程序使用list結構的len屬性來對list持有的鏈表節點進行計數，程序獲取鏈表中節點數量的復雜度為O(1)。

多態:鏈表節點使用void*指針來保存節點值，并且可以通過list結構的dup、free、match三個屬性為節點值設置類型特定函數，所以鏈表可以用于保存各種不同類型的值。

?3. 鏈表和鏈表節點的API

• 常用的API如下表