Verknüpfte Listen

Verknüpfte Listen sind eine gängige Datenstruktur in der Informatik. Du kannst eine verknüpfte Liste verwenden, um z. B. eine Musikwiedergabeliste oder den Verlauf von Aktionen darzustellen.

Überblick

Eine verknüpfte Liste ist eine lineare Datenstruktur, in der jedes Element einen Verweis auf das nächste Element in der Liste speichert. Jedes Element in einer verknüpften Liste wird als Knoten bezeichnet. Ein Knoten ist ein Container, der Daten und eine Referenz auf den nächsten Knoten enthält.

Durch die Verknüpfung verschiedener Knoten in einer Sequenz entsteht eine verknüpfte Liste. Der erste Knoten in der Liste wird als Kopfknoten und der letzte Knoten als Endknoten bezeichnet. Um die Liste zu durchlaufen, beginne am Kopf und gehe über den Verweis in jedem Knoten zum nächsten Element.

Wann verwenden

Verknüpfte Listen sind ein guter Ausgangspunkt für die Implementierung anderer Datenstrukturen wie Stapel oder Warteschlangen. Verknüpfte Listen sind eine einfache Möglichkeit, Daten für den sequentiellen Zugriff zu speichern, und sie unterstützen das schnelle Einfügen neuer Elemente. Im Gegensatz zu Arrays sind verknüpfte Listen im Speicher nicht zusammenhängend (nebeneinander). Das bedeutet, dass sich ein Knoten überall im Speicher befinden kann, und der Verweis auf den nächsten Knoten gibt Auskunft über die Position. Um Knoten aus einer verknüpften Liste einzufügen oder zu löschen, musst du lediglich die Verweise auf den nächsten Knoten ändern.

Wann nicht verwenden

Wenn dein Programm einen zufälligen Zugriff auf Elemente erfordert (z. B. die Auswahl eines zufälligen Spielers aus einer Liste). Diese Funktion fehlt bei verknüpften Listen. Verknüpfte Listen sind weniger effizient als Arrays, wenn du auf einen bestimmten Knoten in der Mitte der Liste zugreifen musst, da du am Kopf der Liste beginnen und zu dem gewünschten Knoten durchlaufen musst.

Implementierung von Verse

Die Verse-API verfügt nicht über eine eingebaute Implementierung von verknüpften Listen, aber du kannst selbst eine erstellen.

Verknüpfte Listen bestehen aus Knoten, und du musst eine Klasse definieren, die sie repräsentiert. Ein Beispiel für einen allgemeinen Knotentyp findest du unten:

# A container node that contains data and a reference
# to the next node in the list.
list_node := class<unique>:
    var Next:?list_node = false
    Data:any = {}

Hier speichert die Optionsvariable Next eine Referenz auf den nächsten Knoten in der Liste, der vom Typ list_node ist. Beachte, dass Next eine option-Variable sein muss, da ein Knoten möglicherweise nicht immer einen nächsten Knoten hat, auf den er zeigen kann (z. B. der Endknoten einer verknüpften Liste). Wenn du die Verknüpfung deiner Liste dynamisch ändern möchtest, muss Next eine var sein. Der Knoten enthält auch einen Wert, der in Data gespeichert wird. Da es sich um einen generischen Knoten-Typ handelt, ist Data vom Typ any, und der Knoten kann jeden Daten-Typ enthalten. Es könnte ein allgemeiner Typ, ein Container oder sogar eine andere verknüpfte Liste sein!

Node1 := list_node{ Next := false, Data := 1 } # An int
Node2 := list_node{ Next := false, Data := "String" } # A string
Node3 := list_node{ Next := false, Data := []int} # An array
Node4 := list_node{ Next := false, Data := list_node } # list_node class
Node5 := list_node{ Next := false, Data := Node1 } # The first node

Der Bezeichner <unique> lässt list_node comparable (vergleichbar) sein. So kannst du prüfen, ob ein Knoten gleich einem anderen Knoten ist, z. B. ob dein Knoten der Kopf oder das Ende einer Liste ist.

Wenn du eine spezifischere Implementierung benötigst, z. B. einen Knoten, der nur Zahlen oder Strings verarbeitet, stelle sicher, dass du den Typ von Data entsprechend anpasst. Wenn Data vom Typ comparable ist, kannst du den Wert in Data mit einem anderen Wert vergleichen, um einen bestimmten Knoten zu finden.

# A container node that contains integer data and a reference
# to the next node in the list.
list_node_int := class(list_node):
    # Reference to the next node in the list.
    var Next<override>:?list_node = false
    Data<override>:int

# A container node that contains string data and a reference
# to the next node in the list.
list_node_string := class(list_node):

Einzeln verknüpfte Listen

Der grundlegendste Typ einer verknüpften Liste ist eine einfach verknüpfte Liste, bei der jeder Knoten eine Referenz auf den nächsten Knoten enthält (ein einzelner Link). Um deine Knoten in eine Liste zu verwandeln, verlinke sie miteinander, indem du die Next-Referenzen in jedem Knoten verwendest.

# Link each Node to the next Node in the list
set Node1.Next = option{Node2}
set Node2.Next = option{Node3}
set Node3.Next = option{Node4}
set Node4.Next = option{Node5}

Obwohl deine Knoten verknüpft sind, solltest du deine verknüpfte Liste in einer Klasse definieren. Dies erleichtert die Ausführung von Funktionen unter Verwendung deiner Liste, anstatt jedes Mal auf den ersten Knoten zu verweisen.

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.linked_list := class:
    var Head:list_node

Eine grundlegende linked_list-Klasse enthält nur eine Referenz auf den Knoten. Um eine Instanz deiner Klasse linked_list zu erstellen, verbinde deine Knoten miteinander und instantiiere dann deine Liste mit Hilfe des Kopfknotens.

# Create a Linked List with node1 as the head.
BasicList:linked_list = linked_list{Head := Node1}

Um die Liste zu durchlaufen, beginne am Kopfknoten und durchlaufe die Liste, wobei du am Ende der Liste anhältst. Du kannst dies entweder in einer externen Funktion oder in einer Klassenfunktion innerhalb deiner Klasse linked_list tun. Im Folgenden findest du eine Beispielfunktion, die die gesamte Liste vom Kopf bis zum Ende durchläuft:

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.linked_list := class:
    var Head:list_node

    TraverseList():void=
        var CurrentNode:?list_node := option{Head} # The node you're currently on
        var NodeNumber:int = 1 # The number of the current node
        Print("Starting at the Head Node...")
        # If the current node has a next node, set the current node to
        # the next node in the list

Hier prüft die Funktion TraverseList(), ob CurrentNode eine Next-Referenz enthält, und speichert sie in NextNode. Wenn dies der Fall ist, wird CurrentNode wiederholt auf NextNode gesetzt, bis der Endknoten erreicht ist. Der Endknoten hat keine Next-Referenz, so dass die Schleife hier endet.

Doppelt verknüpfte Listen

Im Gegensatz zu einfach verknüpften Listen enthalten die Knoten in einer doppelt verknüpften Liste auch eine Referenz auf den Knoten davor, der als vorheriger Knoten bezeichnet wird.

# A container node that contains data and a reference to both
# the next and previous nodes in the list.
doubly_linked_node := class<unique>:
    var Next:?doubly_linked_node = false
    var Previous:?doubly_linked_node = false
    Data:any = {}

Wie bei einfach verknüpften Knoten musst du sicherstellen, dass du den entsprechenden Datentyp änderst, wenn du eine spezifischere Implementierung benötigst, die nur bestimmte Data-Typen verarbeitet.

# A container node that contains integer data and a reference to both
# the next and previous nodes in the list.
doubly_linked_int_node := class(doubly_linked_node):
    Data<override>:int

# A container node that contains string data and a reference to both
# the next and previous nodes in the list.
doubly_linked_string_node := class(doubly_linked_node):
    Data<override>:string

Dies bedeutet, dass du Knoten in einer doppelt verknüpften Liste sowohl vorwärts als auch rückwärts durchlaufen kannst. Dies kann entweder in einer externen Funktion oder in einer Klassenfunktion geschehen. Im Folgenden findest du eine Beispielfunktion, die die Liste vom Kopf bis zum Ende und zurück durchläuft:

# A data structure that links multiple list_node structures together to create a chain. 
# Uses doubly linked nodes which contain references to both the next and previous nodes.
doubly_linked_list := class():
    var Head:doubly_linked_node

    # Traverse a LinkedList, but both backward and forward!
    TraverseDoublyLinkedList():void=
        var CurrentNode:?doubly_linked_node := option{Head}
        var NodeNumber:int = 1
        Print("Starting at the Head Node, and going forward...")

Zirkulär verknüpfte Listen

In einer zirkulär verknüpften Liste ist der Knoten mit dem Endknoten verknüpft. Das bedeutet, dass du die gesamte Liste über den Endknoten hinaus durchlaufen kannst und wieder am Kopf ankommst. Zirkulär verknüpfte Listen können einzeln oder doppelt verknüpft sein. Die einzige Voraussetzung ist, dass der Kopfknoten mit dem Schwanzknoten verbunden ist oder umgekehrt.

Iteratoren

Ein Iterator ist ein Objekt, mit dem du über einen Container iterieren und dabei Operationen durchführen kannst. Du kannst dir das wie einen Zugwaggon voller Passagiere vorstellen. Der Zug fährt auf einem Gleis und hält an jeder Station auf dem Weg. An jedem Bahnhof führt der Zug eine Aufgabe aus, z. B. das Ein- oder Aussteigen von Fahrgästen. Bei verknüpften Listen ist jede Station ein Knoten in der Liste. Der Zug (Iterator) fährt die Liste bis zu jedem Knoten ab und kann dort, wo er anhält, Operationen durchführen.

Iteratoren sind für verknüpfte Listen nützlich, da sie es ermöglichen, Operationen an bestimmten Stellen durchzuführen, und nicht nur am Kopf- oder Endknoten.

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # If there is a NextNode for the iterator to travel to, travel to that node
    Next()<transacts><decides>:list_node=
        set CurrentNode = CurrentNode.Next?

Hier enthält der Iterator eine Referenz auf die Liste, die er iteriert, und einen CurrentNode, an dem der Iterator gerade angehalten wird. Die Funktion Next() prüft, ob der CurrentNode einen nachfolgenden Knoten hat, und springt dann zu diesem. Beachte, dass Next() hier die Bezeichner <transacts> und <decides> enthält. Die Funktion muss <transacts> sein, da sie die var des CurrentNode aktualisiert, und du solltest <decides> verwenden, da du durch die Fehlbarkeit von Next() weißt, ob du zum nächsten Knoten iteriert hast oder nicht.

Obwohl es den Anschein hat, dass ein Iterator am Kopf einer Liste beginnen sollte, muss er tatsächlich vor dem Kopf beginnen. Dadurch kann der Iterator Operationen am Kopfknoten durchführen, wie z. B. das Einfügen von Knoten vor dem Kopf oder das vollständige Löschen des Kopfes.

Um den Iterator vor dem Kopf zu initialisieren, kannst du CurrentNode auf einen Dummy-Knoten mit dem Kopf der Liste als nächsten Knoten initialisieren. In Verse kann man nicht auf die List zugreifen, wenn man CurrentNode initialisiert, da auf Klassenvariablen nicht aus demselben Bereich zugegriffen werden kann, sondern nur aus verschiedenen Bereichen, z. B. innerhalb einer Funktion.

linked_list_iterator := class:
    List:linked_list
    # The below line will fail because you can't access List from this scope
    var CurrentNode:list_node := list_node{Next := option{List.Head}}

Um einen Iterator zu instanziieren, kannst du stattdessen eine Constructor-Funktion verwenden. Ein Construktor ist ein zusammengesetzter Typ, der eine Instanz der Klasse erzeugt, mit der er verbunden ist. Der Constructor setzt anfängliche Werte für ein Objekt und ermöglicht den Zugriff auf den Wert von „List“ und die Zuweisung von CurrentNode an seinen Kopf.

# Construct an Iterator with CurrentNode as a dummy node before the head of the given list.
MakeIterator<constructor>(List:linked_list) := linked_list_iterator:
    List := List
    # You can access List from this scope in a constructor function
    CurrentNode:= list_node{Next := option{List.Head}}

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

Die Initialisierung eines Iterators für eine doppelt verknüpfte Liste sieht sehr ähnlich aus, nur dass du ihn mit doppelt verknüpften Knoten initialisierst.

# Construct an Iterator with CurrentNode as a dummy node before the head of the given list.
MakeDoublyLinkedIterator<constructor>(List:doubly_linked_list) := doubly_linked_list_iterator:
    List := List
    # You can access List from this scope in a constructor function
    CurrentNode:= doubly_linked_node{Next := option{List.Head}}

# Iterates over a doubly_linked_list and can add nodes or remove nodes as it iterates.
doubly_linked_list_iterator := class:
    List:doubly_linked_list
    var CurrentNode:doubly_linked_node

Iterieren zwischen Knoten

Du kannst den Iterator je nach Verknüpfung deiner Liste vorwärts oder rückwärts bewegen. Iteratoren in einer einfach verknüpften Liste können nur vorwärts laufen, während Iteratoren in einer doppelt verknüpften Liste in beide Richtungen laufen können. Diese Funktionalität ist in zwei Funktionen definiert, Next() und Previous(). Denke daran, dass einfach verknüpfte Listen keine Previous()-Funktion haben. Zirkulär verknüpfte Listen können beide Funktionen haben, je nachdem, ob sie einfach oder doppelt verknüpft sind.

# If there is a NextNode for the iterator to travel to, travel to that node
Next()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Next?

# If there is a PreviousNode for the iterator to travel to, travel to that node
Previous()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Previous?

Hinzufügen von Knoten

Du kannst Iteratoren verwenden, um Knoten an bestimmten Stellen in der verknüpften Liste hinzuzufügen. Beim Hinzufügen eines Knotens ist es wichtig, den Ort zu wählen, an dem der Knoten hinzugefügt werden soll. Du könntest den Knoten vor oder nach dem aktuellen Knoten hinzufügen, aber das hängt von der Struktur deiner Liste ab. In einer einfach verknüpften Liste kannst du nur Knoten nach anderen Knoten hinzufügen, da du keine Referenz auf einen Previous-Knoten hast, auf den du dich beziehen könntest. In einer doppelt verknüpften Liste kannst du Knoten vor oder nach anderen Knoten hinzufügen.

# Adds a new node after CurrentNode.
AddNextNode(NewNode:list_node):void=
    if(NextNode := CurrentNode.Next?):
        set NewNode.Next = option{NextNode}
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

Hier fügt die Funktion AddNode einen Knoten zwischen CurrentNode und dem nachfolgenden Knoten ein. Dies erfolgt durch:

• Setzen der Next-Referenz des CurrentNode auf NewNode.

• Setzen der Next-Referenz von NewNode auf den NextNode. Wenn es keinen NextNode gibt (z.B. am Ende einer Liste), setzt die Funktion nur NewNode als nächsten Knoten.

In einer doppelt verknüpften Liste hast du die Option, Knoten vor oder nach CurrentNode hinzuzufügen. Du kannst diese Funktionalität in zwei Funktionen aufteilen, AddNodeAfter() und AddNodeBefore(). Die Implementierung ist der in der einfach verknüpften Liste sehr ähnlich, außer dass man daran denken muss, auch die Previous-Referenz für jeden Knoten zu setzen.

# Adds a new node after CurrentNode.
AddNodeAfter(NewNode:doubly_linked_node):void=
    if(NextNode := CurrentNode.Next?):
        set NewNode.Next = option{NextNode}
        set NewNode.Previous = option{CurrentNode}
        set CurrentNode.Next = option{NewNode}
        set NextNode.Previous = option{NewNode}
        Print("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}

Entfernen von Knoten

Um Knoten zu entfernen, musst du alle Verweise auf diesen Knoten löschen, wobei die Reihenfolge der Liste erhalten bleibt. Dazu musst du alle Knoten vor dem entfernten Knoten mit den Nachfolgeknoten verbinden, nenn der zu entfernende Knoten Nachfolgeknoten hat. In einer einfach verknüpften Liste kannst du nur Knoten nach dem CurrentNode entfernen, da du keine Referenzen auf Previous hast.

# Remove the next node after CurrentNode. If the next node
# has a Next reference, set that node to the next node of CurrentNode.
RemoveNextNode():void=
    if(RemovedNode := CurrentNode.Next?):
        if(NodeAfter := RemovedNode.Next?, set RemovedNode.Next = false):
            set CurrentNode.Next = option{NodeAfter}
            Print("Removed the node between CurrentNode and the node after it")
            # If the removed node is the Head node, set the next node as the new Head.
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")

Beachte, dass du zum Entfernen vom Kopfknoten einen Sonderfall benötigst. In diesem Fall musst du den Knoten nach dem Kopfknoten auf den neuen Kopf setzen, da deine verknüpfte Liste sonst keinen Ausgangspunkt hat.

Wie beim Hinzufügen von Knoten kann das Entfernen von Knoten in einer doppelt verknüpften Liste in das Entfernen des Knotens vor oder nach dem aktuellen Knoten aufgeteilt werden.

# Remove the node after CurrentNode
RemoveNodeAfter():void=
    if(RemovedNode := CurrentNode.Next?):
        if:
            NodeAfter := RemovedNode.Next?
            set RemovedNode.Next = false
            set RemovedNode.Previous = false
            set NodeAfter.Previous = option{CurrentNode}
            set CurrentNode.Next = option{NodeAfter}
        then:

Vollständiger Code

Es folgt der vollständige Code für jede der Klassen in diesem Beispiel.

list_node

# A container node that contains data and a reference
# to the next node in the list.
list_node := class<unique>:
    # Reference to the next node in the list.
    var Next:?list_node = false
    Data:any = {}


# A container node that contains integer data and a reference
# to the next node in the list.

linked_list

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.
linked_list := class:
    # The first node in the list.
    var Head:list_node
 
    # Traverses the linked list forward starting from the CurrentNode.
    TraverseList():void=
        var CurrentNode:?list_node := option{Head} # The node you're currently on
        var NodeNumber:int = 1 # The number of the current node.

linked_list_iterator

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # If there is a NextNode for the iterator to travel to, travel to that node.
    Next()<transacts><decides>:list_node=
        NextNode := CurrentNode.Next?
        set CurrentNode = NextNode

Eigenständig

Es gibt mehrere Möglichkeiten, verknüpfte Listen zu verbessern, und du solltest verschiedene Möglichkeiten zur Hinzufügung von Funktionen untersuchen. Im Folgenden findest du einige Möglichkeiten, wie du deine verknüpften Listen verbessern kannst:

• Was wäre, wenn jede Liste auch eine Referenz auf den Endknoten speichern würde?

• Kannst du eine ToString()-Methode implementieren, um den Inhalt deiner Knoten auszugeben?

• Kannst du eine Liste umkehren? Kannst du eine Length()-Funktionalität implementieren?

• Kannst du dem Iterator mehr Methoden hinzufügen, um neue Operationen durchzuführen?