從 Redis 源碼了解雙向鏈表的設計與實現
近期一直嘗試用go語言復刻redis，所以開始深入研究redis那些巧妙的數據結構設計與實現，本篇文章將針對redis中鏈表的設計與實現進行源碼級別的分析，希望對你有所啟發。
詳解redis中鏈表的設計與實現
鏈表底層結構的設計
鏈表是由無數個節點也就是我們常說的listNode構成，每個節點通過前驅和后繼節點指針維護其前驅和后繼節點信息：
對應的我們也給出redis中鏈表節點listNode 的源碼，它位于adlist.h的定義中，可以看到它通過prev指針和next指針分別管理當前節點的前驅節點和后繼節點，然后通過value指針維護當前節點的值，由這一個個節點的串聯構成雙向鏈表：
typedef struct listNode {
//指向前驅節點
struct listNode *prev;
//指向后繼節點
struct listNode *next;
//維護當前節點的值的指針
void *value;
} listNode;雙向鏈表需要一個頭指針和尾指針管理首尾節點，從而實現后續靈活的頭插法和尾插法的操作，所以在設計雙向鏈表的時候，我們就需要一個head和tail指針管理鏈表的首尾節點。同時，為了實現O(1)級別的長度計算，在元素添加或者刪除操作的時候，我們還需要一個len字段記錄當前鏈表的長度：
而redis中雙向鏈表的結構體list 也是同理：
typedef struct list {
//頭節點指針
listNode *head;
//尾節點指針
listNode *tail;
//......
//鏈表長度
unsigned long len;
} list;了解了基本的數據結構，我們再來說說鏈表的初始化，redis中的雙向鏈表會為其分配一塊內存空間，然后將頭尾節點的指針設置為空，長度初始化為0：
對應的我們給出雙向鏈表初始化的源碼即位于adlist.c的listCreate函數，它完成空間分配和指針、長度初始化之后返回這個鏈表的指針：
list *listCreate(void)
{
//為list結構體分配內存空間
struct list *list;
if ((list = zmalloc(sizeof(*list))) == NULL)
return NULL;
//頭尾指針初始化設置為空
list->head = list->tail = NULL;
//鏈表長度設置為0
list->len = 0;
//......
return list;
}節點頭插法的實現
通過上文我們了解了鏈表的基本數據結構，接下來我們就來聊聊鏈表的第一個操作，也就是頭插法，這個操作就是將最新的節點插入的鏈表的首部，我們以初次插入為例，此時鏈表全空，雙向鏈表初始化節點之后，就會讓鏈表的頭尾指針指向這個node，然后長度自增為1：
若非第一次操作，則初始化一個新節點之后，讓這個節點指向原有的頭節點，最后讓原有的頭節點作為新節點的后繼即可：
圖片
對此我們也給出頭插法的源碼，可以看到它會傳入當前需要操作的鏈表和新節點的value指針完成節點生成和頭插工序，對應的源碼操作細節和上述講解大體一致，讀者可自行參閱：
list *listAddNodeHead(list *list, void *value)
{
//初始化node節點內存空間
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
//value指針指向傳入的值
node->value = value;
//如果鏈表長度為0，則讓首尾節點指向這個node，然后node前驅和后繼節點為空
if (list->len == 0) {
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
//節點的前驅指向空，后繼節點指向原有的頭節點，完成后再讓原有的頭節點作為新節點的后繼節點
//最后head指針指向當前node
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
//維護一下鏈表的長度+1
list->len++;
return list;
}尾插法的實現
尾插法就是將最新節點插入到鏈表末尾，初次插入和頭插法一致，即頭指針head和尾指針tail都指向最新node節點，這里就不做贅述。 我們重點說說常規操作的尾插法，雙向鏈表在進行尾插法時步驟如下：
- 新節點前驅節點指向原有尾節點。
- 原有的尾節點后繼指針指向新節點。
- 修改tail指針指向，讓新節點作為最新的尾節點。
尾插法的函數為listAddNodeTail，入參為要進行操作的list指針和value值，操作步驟的上圖表述基本一致，讀者可結合注釋自行參閱：
list *listAddNodeTail(list *list, void *value)
{
listNode *node;
//分配node內存空間
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
//node的value指針指向value
node->value = value;
//如果長度為0，則首尾指針指向這個node
if (list->len == 0) {
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
//新節點的前驅節點指向尾節點，然后讓原有尾節點指向新節點，最后讓tail指針指向新節點
node->prev = list->tail;
node->next = NULL;
list->tail->next = node;
list->tail = node;
}
//長度信息維護一下
list->len++;
return list;
}指定節點插入
該函數會傳入修改前驅后繼關系的節點，如果希望將新節點n插入到舊節點后面，則會讓新節點n的前驅指向原有節點，后繼節點指向原有節點的后繼，最后讓新節點的前驅后繼節點指向插入的新節點n:
同理插入前面也很節點后添加差不多，這里就不多贅述，對此我們給出listInsertNode的源碼，可以看到它傳入需要進行操作的list指針，再傳入需要維護新關系的old_node指針和需要插入的value，將value封裝為node之后，如果after為1則執行上述所說的old_node后節點插入操作：
- node的前驅指向old_node。
- node后繼指向old_node的后繼。
- old_node的next指針和old_node的后繼節點都指向node。
對應的源碼如下，讀者可參考筆者上述圖解并結合源碼注釋了解整個插入過程：
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
listNode *node;
//節點初始化并設置value
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
//如果after為1則將新節點插入到old_node后面
if (after) {
//node前驅指向old_node，node指向old_node的后繼
node->prev = old_node;
node->next = old_node->next;
//如果old_node是尾節點，則讓tail指向新插入的node
if (list->tail == old_node) {
list->tail = node;
}
} else {
//將新節點插入到old_node前面
node->next = old_node;
node->prev = old_node->prev;
//如果old_node是頭節點，則修改head指向，讓其指向新節點
if (list->head == old_node) {
list->head = node;
}
}
//將node原有的前驅后繼節點指向當前node維護的前驅和后繼節點
if (node->prev != NULL) {
node->prev->next = node;
}
if (node->next != NULL) {
node->next->prev = node;
}
//維護一下長度
list->len++;
return list;
}獲取指定位置的元素
雙向鏈表支持基于索引查找指定位置的元素，操作時間復雜度為O(n)，我們以從頭查找為例，如果希望查找索引2的元素，也就是第3個元素，它就會從head開始跳越2條，由此走到第3個節點的位置并返回這個節點的指針：
對應我們給出listIndex的源碼，可以看到如果傳入的index為負數，則說明調用者要從后往前找，假設我們傳入-2也就是要找到倒數第2個元素，最終取正計算得到1，這也就意味著我們只需從尾節點跳1下就能得到倒數第2個元素，而index若為正數則是順序查找，原理如上圖解析，這里就不多贅述了，讀者可自行查閱listIndex函數及其源碼：
listNode *listIndex(list *list, long index) {
listNode *n;
//如果小于0，說明從后往前照
if (index < 0) {
//將負數轉為正數，例如傳入-2，也就找倒數第2個元素，轉為正為1，也就是往前1跳，返回這個node
index = (-index)-1;
n = list->tail;
while(index-- && n) n = n->prev;
} else {
//說明從前往后照，跳n跳即可得到對應元素
n = list->head;
while(index-- && n) n = n->next;
}
return n;
}刪除指定位置的元素
最后一個就是鏈表刪除操作了，操作比較簡單，讓被刪除節點的前驅和后繼節點構成關聯關系，然后釋放當前被刪節點，然后減小一下長度即可：
對應的源碼如下，讀者可自行參閱學習：
void listDelNode(list *list, listNode *node)
{
//如果node前驅有節點，則讓這個節點指向被刪除節點的后繼
//反之說明這個節點是頭節點，則讓head指向這個后繼節點
if (node->prev)
node->prev->next = node->next;
else
list->head = node->next;
//如果這個節點有后繼節點，則讓這個后繼的prev指向被刪節點的前驅
//反之說明被刪的是尾節點，則讓tail指針指向被刪節點的后繼
if (node->next)
node->next->prev = node->prev;
else
list->tail = node->prev;
//釋放被刪除節點的內存空間，并減小鏈表長度
if (list->free) list->free(node->value);
zfree(node);
list->len--;
}小結
自此我們將redis底層的雙向鏈表的設計與實現的源碼進行的深入分析，從中了解到redis雙向鏈表數據結構設計和節點操作的實現細節，希望對你有所幫助。
