【Redis底層解析】連結清單類型

連結清單

連結清單提供了高效的節點重排能力，以及順序性的節點通路方式，并且可以通過增删節點來靈活調整連結清單的長度。

連結清單在redis中也被廣泛運用，比如在釋出與訂閱，慢查詢，螢幕等功能中也用到了連結清單。本身還使用連結清單來儲存多個用戶端的狀态資訊，以及使用連結清單來建構用戶端輸出緩沖區(output buffer)。

1. 連結清單和連結清單節點的實作

每個連結清單節點使用一個 ​

​adlist.h/listNode​

​結構來表示：

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

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

如下圖所示

雖然僅僅使用多個listNode結構就可以組成連結清單，但是用​

​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;      

• dup 用于複制連結清單節點所儲存的值
• free 函數用于釋放連結清單節點所儲存的值
• match 函數則用于對比連結清單節點所保持的值和另一個輸入值是否相等

2. 連結清單的特點

• 雙端：連結清單節點帶有​

  ​prev​

  ​​ 和​

  ​next​

  ​ 指針，擷取某個節點的前置節點和後置節點的複雜度都是O(1)
• 無環：表頭節點的​

  ​prev​

  ​​ 指針和表尾節點的​

  ​next​

  ​ 指針都指向NULL，對連結清單的通路以NULL為終點。
• 帶表頭指針和表尾指針：通過​

  ​list​

  ​​ 結構和​

  ​head指針​

  ​​ 和​

  ​tail指針​

  ​ ，程式擷取連結清單的表頭節點和表尾節點的複雜度為O(1)
• 帶由連結清單長度計數器：程式使用list結構的​

  ​len屬性​

  ​​ 來對​

  ​list​

  ​ 持有的連結清單節點進行計數，程式擷取連結清單中的節點數量複雜度也為O(1)
• 多态：連結清單節點使用​

  ​void*​

  ​ 指針來儲存節點值，并且可以通過list結構的dup，free，match三個屬性為節點值設定類型特定函數，是以連結清單可以用于儲存各種不同類型的值。