1. 二重連結リストフレームワークを構築する

Redis では、二重リンク リストの各ノードは次の 3 つの要素で構成されます。

• ポインター prev は先行ノードを指します。
• 後継ノードへのポインタ (次)。
• 現在のノードの値へのポインター。

したがって、私はこの定義を二重リンク リスト ノードの構造にも複製しました。

 // 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つの要素が必要です。

• リンク リストの最初のノードを指すヘッド ポインター。
• リンク リストの最後のノードを指すテール ポインタ。
• `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 における双方向連結リストの最初の操作、つまりヘッド挿入を実装できます。この操作では、新しく挿入されたノードを連結リストのヘッドノードにします。この操作の手順は比較的明確です。

• 新しいノードは元のヘッドノードを指します。
• 元のヘッド ノードの先行ポインターは新しいノードを指します。
• ノード ヘッドの挿入を完了するには、ヘッド ポインタを新しいノードに設定します。

これらの操作を完了したら、リンク リストの長さ情報を維持します。

上記のアプローチに基づいて、著者は対応する実装を提供しています。これは基本的にネイティブRedis関数と入力パラメータと同じです。操作対象のリンクリストと値を渡すと、値はノードとしてカプセル化され、上記のアプローチと組み合わせることで、リンクリストの先頭ノードとして設定されます。

 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のノードの値をクエリしたい場合、インデックス2を渡します。双方向リンクリストはインデックス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 }

指定した位置に挿入

双方向リンクリストでは、指定された要素の前または後に要素を挿入できます。要素の後ろへの挿入を例に挙げると、双方向リンクリストは新しいノードを既存のノードの末尾に追加し、先行ノードと後続ノードのポインタ情報を維持します。指定されたノードの前への挿入も同様に機能します。

唯一注意すべき点は、末尾ノードに新しいノードを追加する場合、末尾ポインタを新しいノードを指すように設定する必要があることです。先頭ノードに追加する場合も同様で、先頭ポインタを新しいノードを指すように設定する必要があります。

参考までに、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の先行ノードに設定します。

注意が必要な状況は次の 2 つだけです。

• ヘッド ノードが削除された場合は、ヘッド ノードの次のノードを指すようにします。
• 末尾ノードが削除された場合、 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-- }