Redis 鏈表和鏈表節(jié)點(diǎn)的實(shí)現(xiàn)

每個(gè)鏈表節(jié)點(diǎn)使用一個(gè) adlist.h/listNode 結(jié)構(gòu)來(lái)表示：

typedef struct listNode {

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

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

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

} listNode;

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

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

typedef struct list {

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

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

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

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

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

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

} list;

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

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

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

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

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