硬核復刻 Redis 底層雙向鏈表核心實現

作者：碼農SharkChili 2024-11-22 15:00:00

本文將介紹一下筆者的開源項目mini-redis中對于鏈表的復刻思路，希望對你閱讀我們的項目源碼有所幫助。

1.構建雙向鏈表基架

redis中雙向鏈表的節點都是由如下3個元素構成：

指向前驅節點的指針prev。
指向后繼節點的指針next。
指向當前節點值的指針value。

所以筆者對于雙向鏈表節點的結構體的定義也按照這套定義復刻：

// 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{}
}

因為是雙向鏈表，這意味著鏈表可以從前或者從后進行鏈表操作，所以雙向鏈表就必須具備如下3個構成部分：

指向鏈表第一個節點的head指針。
指向鏈表最后一個節點的tail指針。
維護鏈表長度的字段len。

于是我們基于這個思路，再次給出鏈表的結構體定義：

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
}

了解了基礎的結構定義，我們就可以編寫雙向鏈表初始化的函數listCreate，和redis初始化步驟基本一致，筆者同樣是按照：結構體內存空間分配、頭尾指針初始化、長度設置為0，然后返回這個雙向鏈表結構體指針的步驟進行操作：

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
}

實現節點頭插和尾后追加

此時，我們就可以實現mini-redis中雙向鏈表的第一個操作——頭插法，該操作就是將新插入的節點作為鏈表的頭節點，該操作的步驟比較明確：

新節點指向原有頭節點。
原有頭節點的前驅指針指向新節點。
將head指針指向新節點，完成節點頭插。

完成這些操作之后，維護一下鏈表長度信息：

基于上述思路筆者給出對應的實現，和原生redis的函數和入參基本一致，傳入需要操作的鏈表和value值之后，將value封裝為節點，結合上述的思路將其設置為鏈表頭節點：

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
}

與之同理的還有尾插法，無論入參和操作步驟基本一致，唯一區別就是將節點追加到鏈表末端作為尾節點，讀者可以參考筆者的的實現和注釋了解操作細節：

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

}

基于索引定位節點

雙向鏈表支持基于索引的方式查詢，例如我們希望查詢索引2節點的值，傳入index為2，雙向鏈表就會基于索引2這個值跳越兩次來到目標節點并返回：

假如我們傳入負數，例如負數2，按照語義就是返回倒數第2個節點，雙向鏈表會按照公式(-index)-1得到值1，然后從尾節點跳1步找到目標節點并返回：

對此我們給出相應的源碼實現，整體思路和上述說明一致，讀者可參考源碼和注釋了解細節：

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
}

指定位置插入

雙向鏈表支持在指定元素的前面或者后面插入元素，我們以元素后插入為例，雙向鏈表會將新節點追加到原有節點后面并維護前驅后繼指針的信息，插入到指定節點的前方也是同理：

唯一需要注意的就是如果新節點追加到尾節點后面，我們需要將tail指向新節點。追加到頭節點同理，我們需要將head指針指向新節點：

對此我們給出listInsertNode的源碼實現，讀者可參閱思路并結合注釋了解實現細節：

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

}

雙向鏈表節點刪除

節點刪除則比較簡單，傳入要被刪除的節點指針，讓被刪除節點d的前驅節點指向d的后繼節點，同時讓d的后繼指向d的前驅：

唯一需要注意的就是以下兩種情況：

刪除的是頭節點，則讓head指向頭節點的后面一個節點。
刪除的是尾節點，則讓tail指向尾節點的前一個節點。

最后我們斷掉被刪除節點的前后繼指針指向，讓go語言垃圾回收自動幫我們完成節點刪除即可，這里我們也給出相應的源碼實現：

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

}

責任編輯：趙寧寧來源：寫代碼的SharkChili

開源 Redis 鏈表