So implementieren Sie eine doppelt verknüpfte Liste in Golang

Doppelt verknüpfte Listen sind eine allgemeine Datenstruktur, die eine bidirektionale Zuordnung zwischen Elementen herstellen kann, wodurch Vorgänge wie Einfügen, Löschen und Durchlaufen in der verknüpften Liste sehr effizient sind. In der Go-Sprache ist die Implementierung einer doppelt verknüpften Liste sehr einfach. In diesem Artikel wird erläutert, wie Sie mit Go eine doppelt verknüpfte Liste implementieren.

Eine doppelt verknüpfte Liste ist eine verknüpfte Struktur, und jeder Knoten davon enthält drei Teile: den Vorgängerzeiger prev, den Nachfolgerzeiger next und die Datenfelddaten. In Go können wir eine Struktur definieren, um die Knoten einer doppelt verknüpften Liste darzustellen:

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

wobei prev 和 next 分别指向当前节点的前驱和后继节点，data die im Knoten gespeicherten Daten sind.

Um eine doppelt verknüpfte Liste zu implementieren, müssen wir einen LinkedList-Typ definieren, der einen Zeiger auf den Kopfknoten und den Endknoten der verknüpften Liste sowie die Länge der verknüpften Listengröße enthält:

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

Machen wir das. Implementieren Sie jede Operation der doppelt verknüpften Liste einzeln.

Elemente einfügen

Es gibt drei Hauptsituationen beim Einfügen von Elementen in eine doppelt verknüpfte Liste:

1. Elemente am Kopf einfügen die verknüpfte Liste.
2. Fügen Sie ein Element am Ende der verknüpften Liste ein.
3. Fügen Sie ein Element in die Mitte der verknüpften Liste ein.

In Go können wir eine Insert-Methode definieren, um die oben genannten drei Situationen zu realisieren:

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

Zuerst erstellen wir einen neuen Knotenknoten, um die erforderlichen Einfügungen zu speichern Daten Daten. Wenn die verknüpfte Liste leer ist, wird der neue Knoten als Kopfknoten und Endknoten verwendet. Andernfalls fügen Sie den neuen Knoten nach dem Endknoten ein und aktualisieren Sie den Endknotenzeiger auf den neuen Knoten. Abschließend wird die Länge der verknüpften Liste um 1 erhöht.

Element löschen

Ähnlich wie beim Einfügen von Elementen kann es auch beim Löschen von Elementen drei Situationen geben:

1. Löschen Sie das Kopfelement des verlinkten Elements Liste.
2. Löschen Sie das Endelement der verknüpften Liste.
3. Löschen Sie das Element in der Mitte der verknüpften Liste.

Das Folgende ist eine Beispielimplementierung der Löschmethode:

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
}

Zuerst müssen wir den zu löschenden Knotenknoten finden, was durch eine implementiert wird Hilfsfunktion finden. Wenn der zu löschende Knoten gefunden wird, müssen die Zeiger der Vorgänger- und Nachfolgerknoten basierend auf der Position des Knotens aktualisiert werden. Wenn der zu löschende Knoten der Kopfknoten ist, aktualisieren Sie den Kopfknotenzeiger auf den nächsten Knoten. Wenn der zu löschende Knoten der Endknoten ist, aktualisieren Sie den Endknotenzeiger auf den vorherigen Knoten. Reduzieren Sie abschließend die Länge der verknüpften Liste um 1.

Elemente durchqueren

Das Durchlaufen einer doppelt verknüpften Liste ist sehr einfach. Sie müssen nur am Kopfknoten beginnen und als nächstes entlang des Nachfolgerzeigers weiterlaufen. Die umgekehrte Durchquerung kann am Endknoten beginnen und entlang des Vorgängerzeigers prev durchlaufen. Im Folgenden sind zwei Methoden zum Implementieren der Vorwärts- bzw. Rückwärtsdurchquerung aufgeführt:

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
}

Beim Durchlaufen müssen wir einen Slice erstellen, um die Durchquerungsergebnisse zu speichern, und dann am Kopf- oder Endknoten beginnen und jeden Knoten durchqueren entlang des Zeigers und speichert die Daten des Knotens in Slices.

Zusammenfassung

Mit dem obigen Code haben wir die Grundoperationen einer doppelt verknüpften Liste erfolgreich implementiert. In praktischen Anwendungen gibt es viele Erweiterungen und Optimierungen für doppelt verknüpfte Listen, z. B. das Einfügen oder Löschen von Elementen an einer bestimmten Position in der verknüpften Liste, den Zugriff auf Elemente über Indizes usw. Die Leser können bei Bedarf weitere Studien und Übungen durchführen.

Das Codebeispiel dieses Artikels wurde als Referenz für die Leser auf GitHub hochgeladen: https://github.com/linjiawei123/golang-doubly-linked-list

Das obige ist der detaillierte Inhalt vonSo implementieren Sie eine doppelt verknüpfte Liste in Golang. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!