redis系列之------鏈表

前言

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

作為一種常用數據結構， 鏈表內置在很多高級的編程語言裡面， 因為 Redis 使用的 C 語言並沒有內置這種數據結構， 所以 Redis 構建了自己的鏈表實現。

大家可以把Redis的鏈表實現，和Java的LinkedList實現進行對比，看下哪個更加厲害一點。

鏈表定義

 1 typedef struct listNode {
 2 
 3     // 前置節點
 4     struct listNode *prev;
 5 
 6     // 後置節點
 7     struct listNode *next;
 8 
 9     // 節點的值
10     void *value;
11 
12 } listNode;

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

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

 1 typedef struct list {
 2 
 3     // 表頭節點
 4     listNode *head;
 5 
 6     // 表尾節點
 7     listNode *tail;
 8 
 9     // 鏈表所包含的節點數量
10     unsigned long len;
11 
12     // 節點值複製函數
13     void *(*dup)(void *ptr);
14 
15     // 節點值釋放函數
16     void (*free)(void *ptr);
17 
18     // 節點值對比函數
19     int (*match)(void *ptr, void *key);

我們可以看到，list包含鏈表的頭節點，尾節點以及長度。這就為鏈錶帶來了很多的好處，如下：

• 雙端： 鏈表節點帶有 prev 和 next 指針， 獲取某個節點的前置節點和後置節點的複雜度都是 O(1) 。
• 無環： 表頭節點的 prev 指針和表尾節點的 next 指針都指向 NULL ， 對鏈表的訪問以 NULL 為終點。
• 帶表頭指針和表尾指針： 通過 list 結構的 head 指針和 tail 指針， 程式獲取鏈表的表頭節點和表尾節點的複雜度為 O(1) 。
• 帶鏈表長度計數器： 程式使用 list 結構的 len 屬性來對 list 持有的鏈表節點進行計數， 程式獲取鏈表中節點數量的複雜度為 O(1)。