golangで二重リンクリストを実装する方法

二重リンク リストは、要素間の双方向の関連付けを確立できる一般的なデータ構造であり、リンク リスト内での挿入、削除、走査などの操作を非常に効率的に行うことができます。 Go 言語では二重リンク リストの実装が非常に簡単なので、この記事では Go を使用して二重リンク リストを実装する方法を紹介します。

二重リンク リストはリンクされた構造であり、その各ノードには先行ポインタ prev、後続ポインタ next、およびデータ フィールド data の 3 つの部分が含まれます。 Go では、二重リンク リストのノードを表す構造体を定義できます。

type ListNode struct {
    prev *ListNode
    next *ListNode
    data interface{}
}

その中で、prev と next は先行ノードと後続ノードを指します。 data は、ノードによって保存されたデータです。

二重リンク リストを実装するには、リンク リストの先頭ノードと末尾ノードへのポインタ、およびリンク リスト サイズの長さを含む LinkedList タイプを定義する必要があります。

type LinkedList struct {
    head *ListNode
    tail *ListNode
    size int
}

各演算ごとに二重リンクリストを実装してみましょう。

要素の挿入

二重リンク リストに要素を挿入する主な状況は 3 つあります:

1. 要素をリンク リストの先頭に挿入します。
2. リンクされたリストの最後に要素を挿入します。
3. リンクされたリストの中央に要素を挿入します。

Go では、上記の 3 つの状況を実現するために Insert メソッドを定義できます。

func (list *LinkedList) Insert(data interface{}) {
    node := &ListNode{data: data}
    if list.head == nil {
        list.head = node
        list.tail = node
    } else {
        node.prev = list.tail
        list.tail.next = node
        list.tail = node
    }
    list.size++
}

まず、挿入するデータを格納する新しいノードノードを作成します。リンクされたリストが空の場合、新しいノードがヘッド ノードとテール ノードとして使用されます。それ以外の場合は、末尾ノードの後に​​新しいノードを挿入し、末尾ノード ポインタを新しいノードに更新します。最後に、リンクされたリストの長さが 1 増加します。

要素の削除

要素の挿入と同様に、要素の削除にも 3 つの状況が含まれる場合があります。

1. リンクされたリストの先頭要素を削除します。
2. リンクされたリストの末尾要素を削除します。
3. リンクされたリストの中央にある要素を削除します。

以下は、Delete メソッドの実装例です。

func (list *LinkedList) Delete(data interface{}) {
    node := list.find(data)
    if node != nil {
        if node.prev != nil {
            node.prev.next = node.next
        } else {
            list.head = node.next
        }
        if node.next != nil {
            node.next.prev = node.prev
        } else {
            list.tail = node.prev
        }
        list.size--
    }
}

func (list *LinkedList) find(data interface{}) *ListNode {
    node := list.head
    for node != nil && node.data != data {
        node = node.next
    }
    return node
}

まず、削除するノードノードを見つける必要があります。これは、補助関数 find によって実装されます。削除するノードが見つかった場合は、そのノードの位置に基づいて先行ノードと後続ノードのポインタを更新する必要があります。削除対象のノードが先頭ノードの場合は先頭ノードポインタを次のノードに更新し、削除対象のノードが末尾ノードの場合は末尾ノードポインタを前のノードに更新します。最後に、リンクされたリストの長さを 1 減らします。

要素のトラバース

二重リンク リストのトラバースは非常に簡単で、ヘッド ノードから開始して、次に後続ポインタに沿ってトラバースを続けるだけです。逆方向トラバーサルは末尾ノードから開始し、先行ポインタ prev に沿ってトラバースできます。以下は、順方向トラバーサルと逆方向トラバーサルをそれぞれ実装する 2 つの方法です。

func (list *LinkedList) Traverse() []interface{} {
    result := make([]interface{}, list.size)
    node := list.head
    for i := 0; i < list.size; i++ {
        result[i] = node.data
        node = node.next
    }
    return result
}

func (list *LinkedList) ReverseTraverse() []interface{} {
    result := make([]interface{}, list.size)
    node := list.tail
    for i := 0; i < list.size; i++ {
        result[i] = node.data
        node = node.prev
    }
    return result
}

トラバースするときは、スライスを作成してトラバーサル結果を保存する必要があります。次に、先頭ノードまたは末尾ノードから開始して、ノードに沿って各ノードをトラバースします。 pointer を作成し、ノードのデータをスライスに保存します。

概要

上記のコードにより、二重リンク リストの基本操作を正常に実装できました。実際のアプリケーションでは、リンク リスト内の特定の位置での要素の挿入または削除、インデックスを介した要素へのアクセスなど、二重リンク リストに対する多くの拡張と最適化が行われます。読者は必要に応じてさらなる学習と実践を行うことができます。

この記事のコード例は、読者の参考のために GitHub にアップロードされています: https://github.com/linjiawei123/golang-doubly-linked-list

以上がgolangで二重リンクリストを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。