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