每個鏈表節(jié)點使用一個 adlist.h/listNode 結(jié)構(gòu)來表示：

typedef struct listNode {

    // 前置節(jié)點
    struct listNode *prev;

    // 后置節(jié)點
    struct listNode *next;

    // 節(jié)點的值
    void *value;

} listNode;

多個 listNode 可以通過 prev 和 next 指針組成雙端鏈表， 如圖 3-1 所示。

雖然僅僅使用多個 listNode 結(jié)構(gòu)就可以組成鏈表， 但使用 adlist.h/list 來持有鏈表的話， 操作起來會更方便：

typedef struct list {

    // 表頭節(jié)點
    listNode *head;

    // 表尾節(jié)點
    listNode *tail;

    // 鏈表所包含的節(jié)點數(shù)量
    unsigned long len;

    // 節(jié)點值復(fù)制函數(shù)
    void *(*dup)(void *ptr);

    // 節(jié)點值釋放函數(shù)
    void (*free)(void *ptr);

    // 節(jié)點值對比函數(shù)
    int (*match)(void *ptr, void *key);

} list;

list 結(jié)構(gòu)為鏈表提供了表頭指針 head 、表尾指針 tail ， 以及鏈表長度計數(shù)器 len ， 而 dup 、 free 和 match 成員則是用于實現(xiàn)多態(tài)鏈表所需的類型特定函數(shù)：

• dup 函數(shù)用于復(fù)制鏈表節(jié)點所保存的值；
• free 函數(shù)用于釋放鏈表節(jié)點所保存的值；
• match 函數(shù)則用于對比鏈表節(jié)點所保存的值和另一個輸入值是否相等。

圖 3-2 是由一個 list 結(jié)構(gòu)和三個 listNode 結(jié)構(gòu)組成的鏈表：

Redis 的鏈表實現(xiàn)的特性可以總結(jié)如下：

• 雙端： 鏈表節(jié)點帶有 prev 和 next 指針， 獲取某個節(jié)點的前置節(jié)點和后置節(jié)點的復(fù)雜度都是  。
• 無環(huán)： 表頭節(jié)點的 prev 指針和表尾節(jié)點的 next 指針都指向 NULL ， 對鏈表的訪問以 NULL 為終點。
• 帶表頭指針和表尾指針： 通過 list 結(jié)構(gòu)的 head 指針和 tail 指針， 程序獲取鏈表的表頭節(jié)點和表尾節(jié)點的復(fù)雜度為  。
• 帶鏈表長度計數(shù)器： 程序使用 list 結(jié)構(gòu)的 len 屬性來對 list 持有的鏈表節(jié)點進(jìn)行計數(shù)， 程序獲取鏈表中節(jié)點數(shù)量的復(fù)雜度為 。
• 多態(tài)： 鏈表節(jié)點使用 void* 指針來保存節(jié)點值， 并且可以通過 list 結(jié)構(gòu)的 dup 、 free 、 match 三個屬性為節(jié)點值設(shè)置類型特定函數(shù)， 所以鏈表可以用于保存各種不同類型的值。