Golang implementiert eine doppelt verknüpfte Liste

Doppelt verknüpfte Listen sind eine häufig verwendete Datenstruktur, die es uns ermöglicht, Einfügungs-, Lösch- oder Abfragevorgänge an jeder Position in der verknüpften Liste innerhalb der Zeitkomplexität von O(1) durchzuführen.

Die Implementierung einer doppelt verknüpften Liste in Golang erfordert die Verwendung von Zeigern, da alle Typen in Golang Werttypen sind und die Originaldaten nicht direkt geändert werden können. Durch Zeiger können wir Werte leicht ändern und übertragen und so die Funktionsweise doppelt verknüpfter Listen realisieren.

Das Folgende ist eine einfache Golang-Implementierung einer doppelt verknüpften Liste:

package main

import "fmt"

type Node struct {
    data     int
    previous *Node
    next     *Node
}

type LinkedList struct {
    head *Node
    tail *Node
}

func (list *LinkedList) insertAtBeginning(data int) {
    newNode := &Node{
        data:     data,
        previous: nil,
        next:     nil,
    }

    if list.head == nil {
        list.head = newNode
        list.tail = newNode
        return
    }

    newNode.next = list.head
    list.head.previous = newNode
    list.head = newNode
}

func (list *LinkedList) insertAtEnd(data int) {
    newNode := &Node{
        data:     data,
        previous: nil,
        next:     nil,
    }

    if list.tail == nil {
        list.head = newNode
        list.tail = newNode
        return
    }

    newNode.previous = list.tail
    list.tail.next = newNode
    list.tail = newNode
}

func (list *LinkedList) delete(data int) bool {
    currentNode := list.head

    for currentNode != nil {
        if currentNode.data == data {
            if currentNode == list.head {
                list.head = currentNode.next
                list.head.previous = nil
            } else if currentNode == list.tail {
                list.tail = currentNode.previous
                list.tail.next = nil
            } else {
                currentNode.previous.next = currentNode.next
                currentNode.next.previous = currentNode.previous
            }

            return true
        }

        currentNode = currentNode.next
    }

    return false
}

func (list *LinkedList) display() {
    currentNode := list.head

    for currentNode != nil {
        fmt.Printf("%d ", currentNode.data)
        currentNode = currentNode.next
    }

    fmt.Println()
}

func main() {
    list := LinkedList{}

    list.insertAtEnd(1)
    list.insertAtEnd(2)
    list.insertAtEnd(3)
    list.insertAtBeginning(4)

    list.display()

    list.delete(3)

    list.display()
}

Im obigen Code definieren wir zunächst eine Node-Struktur, die die für jeden Knoten in der verknüpften Liste Drei erforderlichen Informationen enthält Daten: data, previous und next. Unter diesen speichert data den Wert des Knotens, previous speichert die Adresse des vorherigen Knotens und next speichert die Adresse des nächsten Knotens . Node 结构体，该结构体包含链表中的每个节点所需的三个数据：data、previous 和 next。其中，data 存储节点的值，previous 存储上一个节点的地址，next 存储下一个节点的地址。

然后，我们定义了一个 LinkedList 结构体来表示整个链表。该结构体包含链表的头指针 head 和尾指针 tail。

下面是实现双向链表所需的几个方法：

// 在链表头部插入一个元素
func (list *LinkedList) insertAtBeginning(data int) {
    newNode := &Node{
        data:     data,
        previous: nil,
        next:     nil,
    }

    if list.head == nil {
        list.head = newNode
        list.tail = newNode
        return
    }

    newNode.next = list.head
    list.head.previous = newNode
    list.head = newNode
}

// 在链表尾部插入一个元素
func (list *LinkedList) insertAtEnd(data int) {
    newNode := &Node{
        data:     data,
        previous: nil,
        next:     nil,
    }

    if list.tail == nil {
        list.head = newNode
        list.tail = newNode
        return
    }

    newNode.previous = list.tail
    list.tail.next = newNode
    list.tail = newNode
}

// 删除链表中指定的元素
func (list *LinkedList) delete(data int) bool {
    currentNode := list.head

    for currentNode != nil {
        if currentNode.data == data {
            if currentNode == list.head {
                list.head = currentNode.next
                list.head.previous = nil
            } else if currentNode == list.tail {
                list.tail = currentNode.previous
                list.tail.next = nil
            } else {
                currentNode.previous.next = currentNode.next
                currentNode.next.previous = currentNode.previous
            }

            return true
        }

        currentNode = currentNode.next
    }

    return false
}

// 打印链表的所有元素
func (list *LinkedList) display() {
    currentNode := list.head

    for currentNode != nil {
        fmt.Printf("%d ", currentNode.data)
        currentNode = currentNode.next
    }

    fmt.Println()
}

在定义了这几个方法后，我们可以在 main 函数中实例化一个链表对象并进行操作：

func main() {
    list := LinkedList{}

    list.insertAtEnd(1)
    list.insertAtEnd(2)
    list.insertAtEnd(3)
    list.insertAtBeginning(4)

    list.display()

    list.delete(3)

    list.display()
}

在上面的代码中，我们首先实例化了一个 LinkedList 对象 list，然后我们按顺序插入了四个元素：1、2、3 和 4。我们在第一次调用 display 方法时，将输出链表的内容：

4 1 2 3

接着，我们删除了元素 3，并再次调用 display

Dann definieren wir eine LinkedList-Struktur, um die gesamte verknüpfte Liste darzustellen. Diese Struktur enthält den Kopfzeiger head und den Schwanzzeiger tail der verknüpften Liste.

Die folgenden Methoden sind zum Implementieren einer doppelt verknüpften Liste erforderlich: 🎜

4 1 2

🎜Nachdem wir diese Methoden definiert haben, können wir ein verknüpftes Listenobjekt in der Funktion main instanziieren und Operationen ausführen: 🎜rrreee 🎜In der Im obigen Code instanziieren wir zunächst ein LinkedList-Objekt list und fügen dann vier Elemente in der Reihenfolge ein: 1, 2, 3 und 4. Wenn wir die Methode display zum ersten Mal aufrufen, geben wir den Inhalt der verknüpften Liste aus: 🎜rrreee🎜Dann löschen wir Element 3 und rufen die Methode display erneut auf um den Inhalt der verknüpften Liste auszugeben Neuester Inhalt: 🎜rrreee🎜Diese einfache Golang-Implementierung einer doppelt verknüpften Liste zeigt, wie Zeiger zum Erstellen und Ändern verknüpfter Listen verwendet werden und wie Vorgänge wie Einfügen, Löschen und Abfragen verknüpfter Listen implementiert werden . Wenn Sie doppelt verknüpfte Listen verwenden müssen, um effiziente Datenstrukturen zu erstellen, lesen Sie bitte den obigen Code, um zu erfahren, wie Sie doppelt verknüpfte Listen in Golang implementieren. 🎜

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