Listy powiązane

Listy powiązane są strukturą danych często stosowaną w informatyce. Listę powiązaną można wykorzystać na przykład do utworzenia reprezentacji listy odtwarzania muzyki lub śledzenia historii czynności.

Przegląd

Lista powiązana jest liniową strukturą danych, w której każdy element zawiera odwołanie do kolejnego elementu na liście. Każdy element w liście powiązanej nazywany jest węzłem. Węzeł to kontener, który przechowuje pewne dane oraz odwołanie do kolejnego węzła.

Powiązanie ze sobą w sekwencję różnych węzłów tworzy listę powiązaną. Pierwszy węzeł na liście to węzeł głowy, a ostatni węzeł to węzeł ogona. Przejście przez listę rozpoczyna się od głowy, a następnie przez kolejne elementy z wykorzystaniem odwołania zawartego w każdym węźle.

Kiedy stosować

Listy powiązane stanowią dobry punkt wyjścia do implementowania innych struktur danych, takich jak stosy czy kolejki. Listy powiązane są uproszczonym sposobem przechowywania danych, do których dostęp odbywa się sekwencyjnie, i obsługują one możliwość szybkiego wstawiania nowych elementów. W przeciwieństwie do tablic listy powiązane nie sąsiadują ze sobą (nie znajdują się obok siebie) w pamięci. Oznacza to, że węzeł może znajdować się w dowolnym miejscu w pamięci i to odwołanie do kolejnego węzła wskazuje lokalizację. Aby wstawić węzły do listy powiązanej lub je z niej usunąć, wystarczy zmienić odwołania do kolejnego węzła.

Kiedy nie stosować

Jeśli program wymaga losowego dostępu do elementów (na przykład wybrania losowego gracza z listy), listy powiązane się nie sprawdzą. Listy powiązane są mniej wydajne niż tablice, jeśli musisz uzyskać dostęp do konkretnego węzła znajdującego się w środku listy, ponieważ trzeba zacząć od głowy, aby przejść do konkretnego węzła, który jest potrzebny.

Implementacja w Verse

Interfejs API Verse nie ma wbudowanej implementacji list powiązanych, jednak można ją samodzielnie utworzyć.

Listy powiązane składają się z węzłów i trzeba zdefiniować klasę, która będzie je reprezentować. Poniżej zaprezentowano przykład ogólnego typu węzła:

# 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 = {}

W tym przypadku zmienna opcji Next przechowuje odwołanie do kolejnego węzła na liście, którego typ to list_node. Zwróć uwagę, że Next musi być zmienną typu option, ponieważ węzeł nie zawsze musi mieć kolejny węzeł, który wskazuje (dotyczy to na przykład węzła ogona listy powiązanej). Aby dynamicznie zmieniać powiązanie swojej listy, Next musi być var. Węzeł zawiera również pewną wartość przechowywaną w Data. Jest to ogólny typ węzła, dlatego Data ma typ any, a węzeł może zawierać dane dowolnego typu. Mogą to być dane często spotykanego typu, kontener, a nawet inna lista powiązana!

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

Specyfikator <unique> sprawia, że klasa list_node jest porównywalna. Dzięki temu możesz sprawdzić, czy węzeł jest równy innemu węzłowi, na przykład sprawdzając, czy konkretny węzeł jest głową lub ogonem listy.

Jeśli potrzebujesz bardziej konkretnej implementacji, na przykład węzła obsługującego wyłącznie liczby lub ciągi tekstowe, musisz odpowiednio zmienić typ Data. Jeśli typ Data to comparable, można porównać wartość Data z inną wartością w celu znalezienia konkretnego węzła.

# 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):

Listy jednokierunkowe

Najbardziej podstawowym typem listy powiązanej jest lista jednokierunkowa, w której każdy węzeł zawiera odwołanie do następnego węzła (jedno powiązanie). Aby przekształcić węzły w listę, należy powiązać je za pomocą odwołań Next w każdym węźle.

# 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}

Pomimo powiązania węzłów, listę powiązaną i tak trzeba zdefiniować w klasie. Ułatwi to wykonywanie funkcji przy użyciu listy, eliminując konieczność odwoływania się za każdym razem do pierwszego węzła.

# 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

Klasa bazowa linked_list zawiera jedynie odwołanie do węzła głowy. Aby utworzyć instancję klasy linked_list, powiąż ze sobą swoje węzły, a następnie utwórz instancję swojej listy przy użyciu węzła głowy.

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

Przejście przez listę rozpoczyna się od węzła głowy, a następnie odbywa się iteracyjnie przez kolejne węzły, zatrzymując się przy ogonie. Operację tę można wykonać w funkcji zewnętrznej lub w funkcji klasy należącej do klasy linked_list. Poniżej przedstawiono przykładową funkcję, która wykonuje przejście przez całą listę, od głowy do ogona:

# 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

W tym przypadku funkcja TraverseList() sprawdza, czy CurrentNode zawiera odwołanie Next i zapisuje je w NextNode. Jeśli tak, ustawia w sposób powtarzalny CurrentNode jako NextNode, aż do osiągnięcia węzła ogona. Węzeł ogona nie ma odwołania Next, więc pętla zatrzymuje się w tym miejscu.

Listy dwukierunkowe

W przeciwieństwie do list jednokierunkowych węzły na liście dwukierunkowej zawierają także odwołanie do węzła poprzedzającego nazywanego węzłem poprzednim (previous).

# 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 = {}

Podobnie jak w przypadku węzłów jednokierunkowych, jeśli potrzebujesz bardziej konkretnej implementacji, która obsługuje tylko określone typy danych, musisz zmienić typ danych, aby były zgodne.

# 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

Oznacza to, że przejście po dwukierunkowej liście węzłów może odbywać się do przodu lub do tyłu. Operację tę można wykonać w funkcji zewnętrznej lub w funkcji klasy. Poniżej przedstawiono przykładową funkcję, w której przejście po liście odbywa się od głowy do ogona, a następnie wstecz:

# 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...")

Listy cykliczne

Na liście cyklicznej węzeł głowy jest połączony z węzłem ogona. Oznacza to możliwość wykonania przejścia przez całą listę i węzeł ogona, aby dotrzeć z powrotem do głowy. Listy cykliczne mogą być jedno- lub dwukierunkowe, wymagane jest jedynie, aby węzeł głowy był powiązany z węzłem ogona lub odwrotnie.

Iteratory

Iterator jest obiektem umożliwiającym iteracyjne przeszukiwanie kontenera oraz wykonywanie operacji w trakcie tego procesu. Można go porównać do wagonu pociągu pełnego pasażerów. Pociąg jedzie po torach, zatrzymując się po drodze na każdej stacji. Na każdej stacji pociąg wykonuje zadanie, takie jak wysadzenie pasażerów lub zabranie nowych. W przypadku list powiązanych każda stacja będzie węzłem na liście. Pociąg (iterator) będzie jechał w dół listy do każdego węzła i w chwili zatrzymania wykonywał operacje.

Iteratory są przydatnym narzędziem na listach powiązanych, ponieważ umożliwiają wykonywanie operacji w konkretnych miejscach, a nie tylko w węźle głowy lub ogona.

# 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?

W tym przypadku iterator zawiera odwołanie do listy, którą przeszukuje iteracyjnie, a także węzeł CurrentNode, w którym iterator jest obecnie zatrzymany. Funkcja Next() sprawdza, czy za węzłem CurrentNode znajduje się węzeł, a następnie przeskakuje do tego węzła. Zwróć uwagę, że metoda Next() zawiera w tym przypadku specyfikatory <transacts> i <decides>. Funkcja musi mieć specyfikator <transacts>, ponieważ aktualizuje var CurrentNode, a specyfikator <decides> jest pożądany, ponieważ nadanie Next() charakteru wyrażenia zawodnego pozwala dowiedzieć się, czy nastąpiła iteracja do kolejnego węzła.

Choć może się wydawać, że iterator powinien rozpoczynać iterację od głowy listy, w rzeczywistości musi on rozpocząć przed głową. Dzięki temu iterator może wykonywać na węźle głowy takie operacje, jak wstawienie węzłów przed głową lub całkowite usunięcie głowy.

Aby zainicjować iterator przed głową, można zainicjować CurrentNode do węzła pozornego, którego kolejnym węzłem będzie głowa listy. W Verse nie można uzyskać dostępu do List podczas inicjowania CurrentNode, ponieważ nie można uzyskać dostępu do zmiennej składowych klasy z poziomu tego samego zakresu, tylko z innych zakresów, na przykład z poziomu funkcji.

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}}

Zamiast tworzenia instancji iteratora, można użyć funkcji konstruktora. Konstruktor jest typem złożonym, który tworzy instancję klasy, z którą jest powiązany. Konstruktor ustawia wartości początkowe dla obiektu i umożliwia dostęp do wartości listy oraz przypisanie CurrentNode do jej głowy.

# 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

Inicjowanie iteratora w przypadku listy dwukierunkowej wygląda bardzo podobnie. Jedyna różnica polega na tym, że do inicjowania używa się węzłów dwukierunkowych.

# 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

Iterowanie między węzłami

W zależności od sposobu powiązania listy, iterator może wykonywać przejście do przodu lub wstecz. Na liście jednokierunkowej iteratory mogą wykonywać przejścia wyłącznie do przodu, natomiast na liście dwukierunkowej kierunek przejścia jest dowolny. Funkcjonalność tę definiuje się w dwóch funkcjach: Next() oraz Previous(). Pamiętaj, że na listach jednokierunkowych funkcja Previous() nie będzie występować. W przypadku list cyklicznych występować może każda z funkcji, w zależności od tego, czy taka lista jest jedno- czy dwukierunkowa.

# 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?

Dodawanie węzłów

Za pomocą iteratorów można dodawać węzły w konkretnych miejscach na liście powiązanej. Podczas dodawania węzła ważny jest wybór miejsca jego dodania. Węzeł można dodać przed węzłem bieżącym lub po nim, jednak to zależy od struktury listy. Na liście jednokierunkowej węzły można dodawać tylko po innych węzłach, ponieważ nie ma odwołania do węzła Previous, do którego można się odwołać. Na liście dwukierunkowej węzły można dodawać przed innymi węzłami lub po nich.

# 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!")

W tym przypadku funkcja AddNode dodaje węzeł między węzłem CurrentNode a węzłem, który następuje po nim. Wykonuje tę operację poprzez:

• Ustawienie odwołania Next węzła CurrentNode na NewNode.

• Ustawienie odwołania Next węzła NewNode na NextNode. Jeśli nie ma żadnego węzła NextNode (gdy na przykład dotarliśmy do ogona listy), funkcja ustawia jedynie NewNode jako kolejny węzeł.

Na liście dwukierunkowej węzły można dodawać przed węzłem CurrentNode lub po nim. Tę funkcjonalność można podzielić na dwie funkcje AddNodeAfter() i AddNodeBefore(). Implementacja jest bardzo podobna, jak w przypadku listy jednokierunkowej, jednak trzeba tutaj pamiętać, aby dodatkowo ustawić odwołanie Previous dla każdego węzła.

# 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}

Usuwanie węzłów

Aby usunąć węzły, trzeba usunąć wszelkie odwołania do konkretnego węzła, przy jednoczesnym zachowaniu kolejności na liście. Jeśli zatem po węźle przeznaczonym do usunięcia znajdują się jakiekolwiek węzły, trzeba powiązać wszelkie węzły poprzedzające usuwany węzeł z węzłami, które następują po nim. W przypadku listy jednokierunkowej można usuwać jedynie węzły znajdujące się po węźle CurrentNode ze względu na brak odwołania Previous.

# 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")

Usunięcie węzła głowy wymaga zastosowania przypadku szczególnego. W tej sytuacji węzeł następujący po węźle głowy trzeba ustawić jako nową głowę, inaczej lista powiązana nie będzie miała punktu początkowego.

Podobnie jak w przypadku dodawania węzłów, usuwanie węzłów na listach dwukierunkowych można podzielić na usuwanie węzła poprzedzającego węzeł bieżący lub następującego po nim.

# 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:

Complete Code

Poniżej znajduje się kompletny kod dla każdej klasy ilustrujący ten przykład.

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

Praca własna

Listy powiązane można rozbudowywać na wiele sposobów i warto zapoznać się z odmiennymi sposobami dodawania funkcji. Poniżej wskazano kilka pomysłów, które można wykorzystać do rozbudowy list powiązanych:

• Co się stanie, jeśli każda lista będzie również zawierała odwołanie do węzła ogona?

• Czy można zaimplementować metodę ToString() w celu wyświetlenia zawartości węzłów?

• A co z odwracaniem listy? Czy można zaimplementować funkcję Length()?

• Czy można dodać do iteratora więcej metod w celu wykonania nowych operacji?