Die zugrunde liegende Implementierung der Golang-verknüpften Liste

1. Einführung in die verknüpfte Liste

Eine verknüpfte Liste ist eine Datenstruktur, die aus Knoten besteht. Jeder Knoten enthält Daten und einen Zeiger auf den nächsten Knoten. Im Vergleich zu Arrays haben verknüpfte Listen den Vorteil der dynamischen Erweiterung, da sie zu Beginn keinen kontinuierlichen Speicherplatz zuweisen müssen. Verknüpfte Listen werden in viele Typen unterteilt, z. B. in eine Richtung verknüpfte Listen, doppelt verknüpfte Listen und zirkulär verknüpfte Listen.

In diesem Artikel werden wir die zugrunde liegende Implementierung von einseitig verknüpften Listen in Golang diskutieren.

2. Implementierung einer einseitig verknüpften Liste

In Golang verwendet die zugrunde liegende Implementierung einer einseitig verknüpften Liste Zeiger, um die Beziehung zwischen Knoten aufzubauen. Jeder Knoten ist wie folgt definiert:

type Node struct {
    val interface{}
    next *Node
}

wobei val den Wert des Knotens darstellt und next den Zeiger auf den nächsten Knoten darstellt. Die einseitig verknüpfte Liste ist wie folgt definiert: val 表示节点的值，next 表示指向下一个节点的指针。单向链表定义如下：

type SinglyLinkedList struct {
    head *Node
}

其中 head 表示链表的头节点，即第一个节点。

接下来，我们将实现链表的常见操作，包括插入、删除、查找和遍历。

1、插入操作

我们先介绍两种插入操作：在链表头插入和在链表末尾插入。

在链表头插入操作如下：

func (l *SinglyLinkedList) InsertAtHead(val interface{}) {
    node := &Node{val: val}
    node.next = l.head
    l.head = node
}

创建一个新节点 node，将节点的值设置为 val，然后将其指向原头节点 l.head，最后更新 l.head 指向新节点即可。

在链表末尾插入操作如下：

func (l *SinglyLinkedList) InsertAtTail(val interface{}) {
    node := &Node{val: val}
    if l.head == nil {
        l.head = node
    } else {
        curr := l.head
        for curr.next != nil {
            curr = curr.next
        }
        curr.next = node
    }
}

先创建一个新节点 node，如果链表为空，则将新节点设置为头节点。否则，从头节点开始遍历链表，直到找到最后一个节点 curr.next == nil，将其 next 指向新节点即可。

2、删除操作

删除操作包括删除一个指定节点和删除链表中的所有指定节点（相同节点值）。

删除指定节点操作如下：

func (l *SinglyLinkedList) DeleteNode(node *Node) {
    curr := l.head
    if curr == node {
        l.head = curr.next
        return
    }

    for curr.next != nil {
        if curr.next == node {
            curr.next = curr.next.next
            return
        }
        curr = curr.next
    }
}

若要删除的节点是头节点，则直接将 l.head 指向其下一个节点即可。否则从头节点开始遍历链表，找到要删除的节点（curr.next == node），将其 next 指向其下一个节点即可。

删除链表中的所有指定节点操作如下：

func (l *SinglyLinkedList) DeleteNodes(val interface{}) {
    for l.head != nil && l.head.val == val {
        l.head = l.head.next
    }

    curr := l.head
    for curr != nil {
        for curr.next != nil && curr.next.val == val {
            curr.next = curr.next.next
        }
        curr = curr.next
    }
}

若头节点的值为 val，则依次删除指定节点。接着从头节点开始遍历链表，依次删除相同值的节点即可。

3、查找操作

查找操作主要有两种方式：通过指定节点值查找节点和查找该节点在链表中的索引。

通过指定节点值查找节点操作如下：

func (l *SinglyLinkedList) FindNode(val interface{}) *Node {
    curr := l.head
    for curr != nil {
        if curr.val == val {
            return curr
        }
        curr = curr.next
    }
    return nil
}

从头节点开始遍历链表，依次比较节点的值与指定值 val，一旦匹配则返回该节点，否则返回 nil。

查找该节点在链表中的索引操作如下：

func (l *SinglyLinkedList) FindIndex(node *Node) int {
    curr := l.head
    index := 0
    for curr != nil {
        if curr == node {
            return index
        }
        curr = curr.next
        index++
    }
    return -1
}

从头节点开始遍历链表，依次比较节点是否与指定节点 node 相同，如果相同，则返回该节点所在的索引，否则返回 -1。

4、遍历操作

遍历操作主要有两种方式：遍历所有节点和遍历所有节点的值。

遍历所有节点操作如下：

func (l *SinglyLinkedList) Traverse() []*Node {
    nodes := make([]*Node, 0)
    curr := l.head
    for curr != nil {
        nodes = append(nodes, curr)
        curr = curr.next
    }
    return nodes
}

从头节点开始遍历链表，将所有节点按顺序加入 nodes 切片中，并返回该切片。

遍历所有节点的值操作如下：

func (l *SinglyLinkedList) TraverseValues() []interface{} {
    values := make([]interface{}, 0)
    curr := l.head
    for curr != nil {
        values = append(values, curr.val)
        curr = curr.next
    }

    return values
}

从头节点开始遍历链表，将所有节点的值按顺序加入 valuesrrreee

wobei head den Kopfknoten der verknüpften Liste darstellt, also den ersten Knoten.

Als nächstes werden wir allgemeine Operationen verknüpfter Listen implementieren, einschließlich Einfügen, Löschen, Suchen und Durchlaufen.

1. Einfügeoperation🎜🎜Wir führen zunächst zwei Einfügeoperationen ein: Einfügen am Kopf der verknüpften Liste und Einfügen am Ende der verknüpften Liste. 🎜🎜Der Einfügevorgang am Kopf der verknüpften Liste lautet wie folgt: 🎜rrreee🎜Erstellen Sie einen neuen Knoten node, setzen Sie den Knotenwert auf val und zeigen Sie dann darauf zum ursprünglichen Kopfknoten l.head und aktualisieren Sie schließlich l.head so, dass es auf den neuen Knoten zeigt. 🎜🎜Der Einfügevorgang am Ende der verknüpften Liste ist wie folgt: 🎜rrreee🎜Erstellen Sie zunächst einen neuen Knoten node. Wenn die verknüpfte Liste leer ist, legen Sie den neuen Knoten als Kopfknoten fest. Andernfalls durchlaufen Sie die verknüpfte Liste beginnend beim Kopfknoten, bis der letzte Knoten curr.next == nil gefunden wird, und verweisen Sie mit seinem next auf den neuen Knoten. 🎜🎜2. Löschvorgang🎜🎜Der Löschvorgang umfasst das Löschen eines angegebenen Knotens und das Löschen aller angegebenen Knoten (gleicher Knotenwert) in der verknüpften Liste. 🎜🎜Der Vorgang zum Löschen eines bestimmten Knotens ist wie folgt: 🎜rrreee🎜Wenn der zu löschende Knoten der Kopfknoten ist, zeigen Sie einfach l.head direkt auf seinen nächsten Knoten. Andernfalls durchlaufen Sie die verknüpfte Liste ausgehend vom Kopfknoten, suchen den zu löschenden Knoten (curr.next == node) und verweisen mit next auf den nächsten Knoten. 🎜🎜Der Vorgang zum Löschen aller angegebenen Knoten in der verknüpften Liste ist wie folgt: 🎜rrreee🎜Wenn der Wert des Kopfknotens val ist, löschen Sie die angegebenen Knoten nacheinander. Durchlaufen Sie dann die verknüpfte Liste ausgehend vom Kopfknoten und löschen Sie nacheinander Knoten mit demselben Wert. 🎜🎜3. Suchvorgang 🎜🎜Es gibt zwei Hauptmethoden für den Suchvorgang: Suchen nach einem Knoten durch Angabe des Knotenwerts und Suchen nach dem Index des Knotens in der verknüpften Liste. 🎜🎜Der Vorgang zum Suchen eines Knotens durch Angabe des Knotenwerts ist wie folgt: 🎜rrreee🎜Durchlaufen Sie die verknüpfte Liste ausgehend vom Kopfknoten und vergleichen Sie den Wert des Knotens nacheinander mit dem angegebenen Wert val , und geben Sie den Knoten zurück, sobald er übereinstimmt, andernfalls geben Sie nil zurück. 🎜🎜Die Operation, um den Index des Knotens in der verknüpften Liste zu finden, ist wie folgt: 🎜rrreee🎜Durchlaufen Sie die verknüpfte Liste ausgehend vom Hauptknoten und vergleichen Sie die Knoten der Reihe nach, um festzustellen, ob sie mit dem angegebenen Knoten node. Wenn sie identisch sind, geben Sie den Index zurück, an dem sich der Knoten befindet. Andernfalls geben Sie -1 zurück. 🎜🎜4. Durchlaufoperation🎜🎜Es gibt zwei Hauptmethoden für Durchlaufoperationen: Durchlaufen aller Knoten und Durchlaufen der Werte aller Knoten. 🎜🎜Der Vorgang zum Durchlaufen aller Knoten ist wie folgt: 🎜rrreee🎜Durchlaufen Sie die verknüpfte Liste ausgehend vom Kopfknoten, fügen Sie alle Knoten der Reihe nach zum Slice nodes hinzu und geben Sie den Slice zurück. 🎜🎜Der Vorgang zum Durchlaufen der Werte aller Knoten ist wie folgt: 🎜rrreee🎜Durchlaufen Sie die verknüpfte Liste ausgehend vom Kopfknoten und fügen Sie die Werte aller Knoten zum values-Slice hinzu Bestellen Sie und geben Sie das Stück zurück. 🎜🎜3. Zusammenfassung🎜🎜In Golang verwendet die zugrunde liegende Implementierung einseitig verknüpfter Listen Zeiger, um Beziehungen zwischen Knoten aufzubauen. Durch die Implementierung allgemeiner Vorgänge wie Einfügen, Löschen, Suchen und Durchlaufen verstehen wir die Natur und Vorteile verknüpfter Listen besser und verstehen auch besser, wie Golang verknüpfte Listen auf der untersten Ebene implementiert. In der tatsächlichen Entwicklung können verknüpfte Listen auf viele Szenarien angewendet werden, z. B. auf den LRU-Cache, invertierte verknüpfte Listen usw. 🎜

Das obige ist der detaillierte Inhalt vonDie zugrunde liegende Implementierung der Golang-verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!