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

typedef struct listNode {

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

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

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

} listNode;

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

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

typedef struct list {

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

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

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

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

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

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

} list;

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

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

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

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

轉載文章
Redis 設計與實現(xiàn)