Go Language Programming Guide: Detaillierte Erläuterung der Implementierung einer einzelnen verknüpften Liste

Go-Sprachprogrammierhandbuch: Detaillierte Erläuterung der Implementierung einfach verknüpfter Listen

In der Go-Sprache ist eine einfach verknüpfte Liste eine allgemeine Datenstruktur, die zum Speichern einer Reihe von Elementen und zum sequenziellen Zugriff darauf verwendet wird. In diesem Artikel wird das Implementierungsprinzip einer einfach verknüpften Liste ausführlich vorgestellt und spezifische Codebeispiele für die Go-Sprache gegeben.

Definition einer einfach verknüpften Liste

Eine einfach verknüpfte Liste ist eine lineare Listendatenstruktur, in der jedes Element (Knoten) zwei Teile enthält: das Datenfeld und das Zeigerfeld. Das Datenfeld wird zum Speichern des Werts des Elements verwendet und das Zeigerfeld zeigt auf den nächsten Knoten. Das Zeigerfeld des letzten Knotens ist normalerweise leer, was das Ende der verknüpften Liste anzeigt.

Knotendefinition einer einfach verknüpften Liste

Zuerst definieren wir den Knotentyp einer einfach verknüpften Liste:

type Node struct {
    data int
    next *Node
}

Unter diesen speichert das data字段存储节点的值，next-Feld den Zeiger auf den nächsten Knoten.

Initialisierung einer einfach verknüpften Liste

Als nächstes definieren wir die Initialisierungsfunktion einer einfach verknüpften Liste:

type LinkedList struct {
    head *Node
}

func NewLinkedList() *LinkedList {
    return &LinkedList{}
}

In der Initialisierungsfunktion erstellen wir eine leere verknüpfte Liste und initialisieren den Kopfknotenzeiger auf leer.

Einfügevorgang einer einfach verknüpften Liste

Der Einfügevorgang einer einfach verknüpften Liste kann in zwei Situationen unterteilt werden: Einfügen eines Knotens am Kopf der verknüpften Liste und Einfügen eines Knotens am Ende der verknüpften Liste.

Die erste ist die Funktion zum Einfügen eines Knotens am Kopf der verknüpften Liste:

func (list *LinkedList) InsertAtBeginning(value int) {
    newNode := &Node{data: value}
    newNode.next = list.head
    list.head = newNode
}

In dieser Funktion erstellen wir zunächst einen neuen Knoten und initialisieren seinen Wert auf den übergebenen Wert. Zeigen Sie dann mit dem Zeiger des neuen Knotens auf den Kopf der verknüpften Liste und aktualisieren Sie schließlich den Kopfknoten der verknüpften Liste auf den neuen Knoten.

Als nächstes folgt die Funktion zum Einfügen eines Knotens am Ende der verknüpften Liste:

func (list *LinkedList) InsertAtEnd(value int) {
    newNode := &Node{data: value}
    if list.head == nil {
        list.head = newNode
        return
    }

    current := list.head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
}

Diese Funktion erstellt zunächst einen neuen Knoten und ermittelt, ob die verknüpfte Liste leer ist. Wenn es leer ist, wird der neue Knoten direkt als Hauptknoten festgelegt. Andernfalls wird die verknüpfte Liste durchlaufen, bis der letzte Knoten gefunden wird, und dann wird der neue Knoten nach dem letzten Knoten eingefügt.

Löschvorgang einer einfach verknüpften Liste

Der Löschvorgang ist in zwei Situationen unterteilt: Löschen des Kopfknotens und Löschen des Knotens mit dem angegebenen Wert.

Die erste ist die Funktion zum Löschen des Kopfknotens:

func (list *LinkedList) DeleteAtBeginning() {
    if list.head == nil {
        return
    }
    list.head = list.head.next
}

Diese Funktion zeigt den Kopfknotenzeiger direkt auf den nächsten Knoten und löscht dadurch den Kopfknoten.

Als nächstes folgt die Funktion zum Löschen des Knotens mit dem angegebenen Wert:

func (list *LinkedList) DeleteByValue(value int) {
    if list.head == nil {
        return
    }
    if list.head.data == value {
        list.head = list.head.next
        return
    }

    prev := list.head
    current := list.head.next
    for current != nil {
        if current.data == value {
            prev.next = current.next
            return
        }
        prev = current
        current = current.next
    }
}

In dieser Funktion müssen wir zunächst feststellen, ob die verknüpfte Liste leer ist. Durchlaufen Sie dann die verknüpfte Liste ausgehend vom Kopfknoten, suchen Sie den Knoten, in dem sich der Zielwert befindet, und löschen Sie ihn.

Durchlaufoperation für einfach verknüpfte Listen

Die letzte ist die Durchlaufoperation für einfach verknüpfte Listen:

func (list *LinkedList) Print() {
    current := list.head
    for current != nil {
        fmt.Print(current.data, " ")
        current = current.next
    }
    fmt.Println()
}

Diese Funktion druckt den Wert der Knoten nacheinander, beginnend vom Kopfknoten bis zum Ende der verknüpften Liste.

Beispielcode

Das Folgende ist ein vollständiger Beispielcode, der zeigt, wie eine einfach verknüpfte Liste verwendet wird:

package main

import "fmt"

type Node struct {
    data int
    next *Node
}

type LinkedList struct {
    head *Node
}

func NewLinkedList() *LinkedList {
    return &LinkedList{}
}

func (list *LinkedList) InsertAtBeginning(value int) {
    newNode := &Node{data: value}
    newNode.next = list.head
    list.head = newNode
}

func (list *LinkedList) InsertAtEnd(value int) {
    newNode := &Node{data: value}
    if list.head == nil {
        list.head = newNode
        return
    }

    current := list.head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
}

func (list *LinkedList) DeleteAtBeginning() {
    if list.head == nil {
        return
    }
    list.head = list.head.next
}

func (list *LinkedList) DeleteByValue(value int) {
    if list.head == nil {
        return
    }
    if list.head.data == value {
        list.head = list.head.next
        return
    }

    prev := list.head
    current := list.head.next
    for current != nil {
        if current.data == value {
            prev.next = current.next
            return
        }
        prev = current
        current = current.next
    }
}

func (list *LinkedList) Print() {
    current := list.head
    for current != nil {
        fmt.Print(current.data, " ")
        current = current.next
    }
    fmt.Println()
}

func main() {
    list := NewLinkedList()

    list.InsertAtEnd(1)
    list.InsertAtEnd(2)
    list.InsertAtEnd(3)
    list.Print()

    list.DeleteByValue(2)
    list.Print()

    list.DeleteAtBeginning()
    list.Print()
}

Das Obige ist eine detaillierte Anleitung zur Implementierung einer einfach verknüpften Liste mit der Go-Sprache. Ich hoffe, dass die Leser durch die Einführung und den Beispielcode dieses Artikels ein tieferes Verständnis für die Prinzipien und die Implementierung einfach verknüpfter Listen erlangen können.

Das obige ist der detaillierte Inhalt vonGo Language Programming Guide: Detaillierte Erläuterung der Implementierung einer einzelnen verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!