硬核復(fù)刻 Redis 底層雙向鏈表核心實(shí)現(xiàn)
1.構(gòu)建雙向鏈表基架
redis中雙向鏈表的節(jié)點(diǎn)都是由如下3個(gè)元素構(gòu)成：
- 指向前驅(qū)節(jié)點(diǎn)的指針prev。
- 指向后繼節(jié)點(diǎn)的指針next。
- 指向當(dāng)前節(jié)點(diǎn)值的指針value。
所以筆者對(duì)于雙向鏈表節(jié)點(diǎn)的結(jié)構(gòu)體的定義也按照這套定義復(fù)刻：
// Definition of the listNode structure for a doubly linked list
type listNode struct {
//Node pointing to the previous node of the current node.
prev *listNode
//Node pointing to the successor node of the current node.
next *listNode
//Record information about the value stored in the current node.
value *interface{}
}因?yàn)槭请p向鏈表，這意味著鏈表可以從前或者從后進(jìn)行鏈表操作，所以雙向鏈表就必須具備如下3個(gè)構(gòu)成部分：
- 指向鏈表第一個(gè)節(jié)點(diǎn)的head指針。
- 指向鏈表最后一個(gè)節(jié)點(diǎn)的tail指針。
- 維護(hù)鏈表長(zhǎng)度的字段len。
于是我們基于這個(gè)思路，再次給出鏈表的結(jié)構(gòu)體定義：
type list struct {
//Points to the first node of the doubly linked list
head *listNode
//points to the last node of the linked list.
tail *listNode
//Record the current length of the doubly linked list
len int64
}了解了基礎(chǔ)的結(jié)構(gòu)定義，我們就可以編寫(xiě)雙向鏈表初始化的函數(shù)listCreate，和redis初始化步驟基本一致，筆者同樣是按照：結(jié)構(gòu)體內(nèi)存空間分配、頭尾指針初始化、長(zhǎng)度設(shè)置為0，然后返回這個(gè)雙向鏈表結(jié)構(gòu)體指針的步驟進(jìn)行操作：
func listCreate() *list {
//Allocate memory space for the doubly linked list
var l *list
l = new(list)
//Initialize the head and tail pointers.
l.head = nil
l.tail = nil
//Initialize the length to 0, indicating that the current linked list has no nodes
l.len = 0
return l
}實(shí)現(xiàn)節(jié)點(diǎn)頭插和尾后追加
此時(shí)，我們就可以實(shí)現(xiàn)mini-redis中雙向鏈表的第一個(gè)操作——頭插法，該操作就是將新插入的節(jié)點(diǎn)作為鏈表的頭節(jié)點(diǎn)，該操作的步驟比較明確：
- 新節(jié)點(diǎn)指向原有頭節(jié)點(diǎn)。
- 原有頭節(jié)點(diǎn)的前驅(qū)指針指向新節(jié)點(diǎn)。
- 將head指針指向新節(jié)點(diǎn)，完成節(jié)點(diǎn)頭插。
完成這些操作之后，維護(hù)一下鏈表長(zhǎng)度信息：
基于上述思路筆者給出對(duì)應(yīng)的實(shí)現(xiàn)，和原生redis的函數(shù)和入?yún)⒒疽恢拢瑐魅胄枰僮鞯逆湵砗蛌alue值之后，將value封裝為節(jié)點(diǎn)，結(jié)合上述的思路將其設(shè)置為鏈表頭節(jié)點(diǎn)：
func listAddNodeHead(l *list, value *interface{}) *list {
//Allocate memory for a new node and set its value.
var node *listNode
node = new(listNode)
node.value = value
//If the length is 0, then both the head and tail pointers point to the new node.
if l.len == 0 {
l.head = node
l.tail = node
} else {
//Make the original head node the successor node of the new node, node.
node.prev = nil
node.next = l.head
l.head.prev = node
l.head = node
}
//Maintain the information about the length of the linked list.
l.len++
return l
}與之同理的還有尾插法，無(wú)論入?yún)⒑筒僮鞑襟E基本一致，唯一區(qū)別就是將節(jié)點(diǎn)追加到鏈表末端作為尾節(jié)點(diǎn)，讀者可以參考筆者的的實(shí)現(xiàn)和注釋了解操作細(xì)節(jié)：
func listAddNodeTail(l *list, value *interface{}) *list {
//Allocate memory for a new node and set its value.
var node *listNode
node = new(listNode)
node.value = value
//If the length is 0, then both the head and tail pointers point to the new node.
if l.len == 0 {
l.head = node
l.tail = node
} else {
//Append the newly added node after the tail node to become the new tail node.
node.prev = l.tail
node.next = nil
l.tail.next = node
l.tail = node
}
//Maintain the information about the length of the linked list.
l.len++
return l
}基于索引定位節(jié)點(diǎn)
雙向鏈表支持基于索引的方式查詢，例如我們希望查詢索引2節(jié)點(diǎn)的值，傳入index為2，雙向鏈表就會(huì)基于索引2這個(gè)值跳越兩次來(lái)到目標(biāo)節(jié)點(diǎn)并返回：
假如我們傳入負(fù)數(shù)，例如負(fù)數(shù)2，按照語(yǔ)義就是返回倒數(shù)第2個(gè)節(jié)點(diǎn)，雙向鏈表會(huì)按照公式(-index)-1得到值1，然后從尾節(jié)點(diǎn)跳1步找到目標(biāo)節(jié)點(diǎn)并返回：
對(duì)此我們給出相應(yīng)的源碼實(shí)現(xiàn)，整體思路和上述說(shuō)明一致，讀者可參考源碼和注釋了解細(xì)節(jié)：
func listIndex(l *list, index int64) *listNode {
var n *listNode
//"If less than 0, calculate the index value as a positive number n,
//then continuously jump to the node pointed to by prev based on this positive number n.
if index < 0 {
index = (-index) - 1
n = l.tail
for index > 0 && n != nil {
n = n.prev
index--
}
} else {
//Conversely, walk n steps from the front and reach the target node via next, then return.
n = l.head
for index > 0 && n != nil {
n = n.next
index--
}
}
return n
}指定位置插入
雙向鏈表支持在指定元素的前面或者后面插入元素，我們以元素后插入為例，雙向鏈表會(huì)將新節(jié)點(diǎn)追加到原有節(jié)點(diǎn)后面并維護(hù)前驅(qū)后繼指針的信息，插入到指定節(jié)點(diǎn)的前方也是同理：
唯一需要注意的就是如果新節(jié)點(diǎn)追加到尾節(jié)點(diǎn)后面，我們需要將tail指向新節(jié)點(diǎn)。追加到頭節(jié)點(diǎn)同理，我們需要將head指針指向新節(jié)點(diǎn)：
對(duì)此我們給出listInsertNode的源碼實(shí)現(xiàn)，讀者可參閱思路并結(jié)合注釋了解實(shí)現(xiàn)細(xì)節(jié)：
func listInsertNode(l *list, old_node *listNode, value *interface{}, after bool) *list {
//Allocate memory for a new node and set its value.
var node *listNode
node = new(listNode)
node.value = value
//If after is true, insert the new node after the old node.
if after {
node.prev = old_node
node.next = old_node.next
//If the old node was originally the tail node, after the modification,
//make the node the new tail node.
if l.tail == old_node {
l.tail = node
}
} else {
//Add the new node before the old node.
node.next = old_node
node.prev = old_node.prev
//If the original node is the head, then set the new node as the head
if l.head == old_node {
l.head = node
}
}
//If the node's predecessor node is not empty, then point the predecessor to the node.
if node.prev != nil {
node.prev.next = node
}
//If the node's successor node is not empty, make this successor point to the node.
if node.next != nil {
node.next.prev = node
}
//Maintain the information about the length of the linked list.
l.len++
return l
}雙向鏈表節(jié)點(diǎn)刪除
節(jié)點(diǎn)刪除則比較簡(jiǎn)單，傳入要被刪除的節(jié)點(diǎn)指針，讓被刪除節(jié)點(diǎn)d的前驅(qū)節(jié)點(diǎn)指向d的后繼節(jié)點(diǎn)，同時(shí)讓d的后繼指向d的前驅(qū)：
唯一需要注意的就是以下兩種情況：
- 刪除的是頭節(jié)點(diǎn)，則讓head指向頭節(jié)點(diǎn)的后面一個(gè)節(jié)點(diǎn)。
- 刪除的是尾節(jié)點(diǎn)，則讓tail指向尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。
最后我們斷掉被刪除節(jié)點(diǎn)的前后繼指針指向，讓go語(yǔ)言垃圾回收自動(dòng)幫我們完成節(jié)點(diǎn)刪除即可，這里我們也給出相應(yīng)的源碼實(shí)現(xiàn)：
func listDelNode(l *list, node *listNode) {
//If the predecessor node is not empty,
//then the predecessor node's next points to the successor node of the node being deleted
if node.prev != nil {
node.prev.next = node.next
} else {
//If the deleted node is the head node, set the head to point to the next node.
l.head = node.next
}
//If next is not empty, then let next point to the node before the deleted node
if node.next != nil {
node.next.prev = node.prev
} else {
//If the deleted node is the tail node, make
//the node before the deleted node the new tail node.
l.tail = node.prev
}
//help gc
node.prev = nil
node.next = nil
l.len--
}
