【Redis學習筆記】底層資料結構之連結清單

連結清單

Redis 使用連結清單作為清單的鍵底層實作。

3.1 連結清單和連結清單節點的實作

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

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

多個 listNode 可以通過 prev 和 next 指針組成雙端連結清單

可以通過 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 三個屬性為節點值設定類型特定函數，是以連結清單可以用于儲存各種不同類型的值。