Redis 鏈表實現

// 每個鏈表節點使用一個 ListNode 結構來表示
typedef struct ListNode{
    //前置節點
    struct ListNode *prev;
    //後置節點
    struct ListNode *next;
    //節點值
    void *value;
} ListNode;

// 
typedef struct List{
    //頭節點
    struct ListNode *head;

    //尾節點
    struct ListNode *tail;

    //鏈表所包含的節點數量
    unsigned long length;

　　//節點值複製函數
　　void *(*dup) (void *ptr);

　　//節點值釋放函數
　　void *(*free) (void *ptr);

　　//節點值對比函數
　　void (*match) (void *ptr, void *key);

} List;

　　Redis 鏈表實現的特性總結如下：

1. 雙端：鏈表節點帶有 prev 和 next 指針，獲取某個節點的前置節點和後置節點
2. 無環：表頭節點的prev指針和表尾節點的next指針指向NULL，因此對鏈表的訪問以NULL終止，無環
3. 帶有表頭和表尾指針：通過List 的tail 和 head 指針，獲取鏈表的表頭和表尾節點的複雜度為O(1)
4. 帶有鏈表長度計數器：通過List 的length屬性，獲取鏈表長度的時間複雜度為O(1)
5. 多態：鏈表節點使用 void* 指針來保存節點值，並且可以通過list 結構的 dup 、free、match 三個屬性為節點值設置類型特定函數，所以鏈表可以用於保存各種不同類型的值。

鏈表被用來實現Redis 的各種功能，比如列表鍵、發佈與訂閱、慢查詢、監視器等