Implementierung der Golang-Liste

Golang ist eine effiziente und prägnante Programmiersprache, die große Vorteile in Bezug auf Leistung und Parallelität bietet. In Golang gibt es viele Implementierungen von Sammlungsdatenstrukturen, einschließlich Listen. Liste ist eine sehr wichtige Datenstruktur, die zum Speichern einer Reihe von Daten verwendet werden kann und das Einfügen und Löschen von Elementen an jeder beliebigen Stelle unterstützt. In diesem Artikel wird erläutert, wie Sie mit Golang eine Liste implementieren.

1. Definition von Liste

Liste ist eine Datenstruktur, bei der es sich um eine geordnete Sammlung von Elementen handelt. In einer Liste hat jedes Element einen Vorgänger und einen Nachfolger, mit Ausnahme des ersten und letzten Elements. Das erste Element hat keine Vorgängerelemente und das letzte Element hat keine Nachfolgerelemente. Die Liste bietet einige grundlegende Vorgänge, z. B. das Hinzufügen von Elementen, das Löschen von Elementen, den Zugriff auf Elemente usw.

2. Implementierung einer Liste

In Golang kann eine Liste mithilfe einer doppelt verknüpften Liste implementiert werden. Eine doppelt verknüpfte Liste enthält einen Zeigerkopf, der auf den ersten Knoten zeigt, und einen Zeigerschwanz, der auf den letzten Knoten zeigt. Jeder Knoten enthält einen Zeiger prev, der auf den vorherigen Knoten zeigt, und einen Zeiger next, der auf den nächsten Knoten zeigt, sowie einen Wert val zum Speichern des Werts des Knotens. Wie unten gezeigt:

Typ ListNode struct {

prev *ListNode // 指向前一个节点
next *ListNode // 指向后一个节点
val  interface{// 当前节点的值
} 

}
Typ List struct {

head *ListNode // 指向第一个节点
tail *ListNode // 指向最后一个节点
len  int       // List的长度

}

Bei der Implementierung von List müssen wir auf die folgenden Punkte achten:

(1) Elemente hinzufügen

Hinzufügen Liste Es gibt zwei Hauptmethoden zum Hinzufügen von Elementen: das Hinzufügen von Elementen am Kopf der Tabelle und das Hinzufügen von Elementen am Ende der Tabelle. Wir können sie mit den Methoden AddFront und AddBack implementieren.

func (list *List) AddFront(val interface{}) {

node := &ListNode{
    prev: nil,
    next: list.head,
    val:  val,
}
if list.head == nil { // 如果链表为空
    list.head = node
    list.tail = node
} else {
    list.head.prev = node
    list.head = node
}
list.len++

}

func (list *List) AddBack(val interface{}) {

node := &ListNode{
    prev: list.tail,
    next: nil,
    val:  val,
}
if list.tail == nil { // 如果链表为空
    list.head = node
    list.tail = node
} else {
    list.tail.next = node
    list.tail = node
}
list.len++

}

(2) Element löschen

Löschen Elemente werden hauptsächlich in zwei Situationen unterteilt: Löschen von Header-Elementen und Löschen von Tail-Elementen. Wir können auch die Methoden RemoveFront und RemoveBack verwenden, um Elemente zu löschen.

func (list *List) RemoveFront() {

if list.head == nil { // 如果链表为空
    return
}
if list.head == list.tail { // 如果链表只有一个元素
    list.head = nil
    list.tail = nil
    list.len = 0
    return
}
list.head = list.head.next
list.head.prev = nil
list.len--

}

func (list *List) RemoveBack() {

if list.tail == nil { // 如果链表为空
    return
}
if list.head == list.tail { // 如果链表只有一个元素
    list.head = nil
    list.tail = nil
    list.len = 0
    return
}
list.tail = list.tail.prev
list.tail.next = nil
list.len--

}

(3) So greifen Sie auf Elemente zu:

Zugriff auf Elemente in der Liste nur über die Kopfzeile Oder beginnen Sie mit dem Durchlaufen vom Ende der Tabelle nacheinander, bis Sie das gewünschte Element gefunden haben. Wir können die Front- und Back-Methoden verwenden, um auf das erste und letzte Element in der Liste zuzugreifen.

func (list *List) Front() interface{} {

if list.head == nil {
    return nil
}
return list.head.val

}

func (list *List) Back() interface{} {

if list.tail == nil {
    return nil
}
return list.tail.val

}

Das Obige ist die grundlegende Methode zum Implementieren von List in Golang können Sie entsprechend den tatsächlichen Bedürfnissen anpassen und optimieren.

3. Zusammenfassung

Die Implementierung von List in Golang ist sehr einfach. Wir müssen lediglich eine doppelt verknüpfte Liste verwenden. Die Liste wurde in der Standardbibliothek in Golang implementiert. Daher wird empfohlen, die Liste in der Standardbibliothek bei der tatsächlichen Verwendung zu verwenden. Wenn Sie die Liste anpassen müssen, können Sie den oben angegebenen Code entsprechend den tatsächlichen Anforderungen anpassen und optimieren.

Das obige ist der detaillierte Inhalt vonImplementierung der Golang-Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!