Elenchi collegati

Gli elenchi collegati sono una struttura di dati standard nell'ambito dell'informatica. Ad esempio, puoi utilizzare un elenco collegato per rappresentare una playlist musicale o per tracciare una cronologia di azioni.

Panoramica

Un elenco collegato è una struttura di dati lineare in cui ciascun elemento memorizza un riferimento all'elemento successivo dell'elenco. Ogni elemento di un elenco collegato è definito nodo. Il nodo è un contenitore che contiene dei dati e un riferimento al nodo successivo.

Il collegamento di diversi nodi in una sequenza determina la creazione di un elenco collegato. Il primo nodo nell'elenco è chiamato nodo head e l'ultimo nodo è chiamato nodo tail . Per scorrere un elenco, si parte dall'inizio passando all'elemento successivo usando il riferimento in ogni nodo.

Quando utilizzare

Gli elenchi collegati sono un buon punto di partenza per implementare altre strutture di dati come stack o code. Rappresentano un modo semplice per memorizzare i dati per l'accesso sequenziale e consentono di inserire rapidamente nuovi elementi. A differenza degli array, gli elenchi collegati non sono contigui (uni accanto all'altro) in memoria. Ciò significa che un nodo può trovarsi in qualsiasi punto della memoria e il riferimento al nodo successivo ne indica la posizione. Per inserire o rimuovere nodi da un elenco collegato, è sufficiente cambiare i riferimenti al nodo successivo.

Quando non utilizzare

Se il tuo programma necessita di accedere in modo casuale agli elementi, ad esempio selezionando un giocatore a caso da un elenco, gli elenchi collegati non sono la scelta adatta poiché non supportano questa funzionalità. Gli elenchi collegati sono meno efficienti degli array se devi accedere a un determinato nodo al centro dell'elenco, poiché è necessario iniziare dall'inizio dell'elenco e scorrere tutti i nodi precedenti per raggiungere quello desiderato.

Implementazione di Verse

Sebbene l'API Verse non fornisca un'implementazione predefinita degli elenchi collegati, hai la possibilità di crearne una autonomamente.

Gli elenchi collegati sono formati da nodi e devi definire una classe per rappresentarli. Di seguito è riportato un tipo di nodo generico:

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

In questo caso, la variabile opzionale Next memorizza un riferimento al nodo successivo dell'elenco che è di tipo list_node. Nota che Next deve essere una variabile option, dato che un nodo potrebbe non avere sempre un nodo successivo a cui puntare (come ad esempio il nodo di coda di un elenco collegato). Se vuoi cambiare dinamicamente il collegamento del tuo elenco, Next deve essere una var. Il nodo contiene anche un valore memorizzato in Data. Trattandosi di un tipo di nodo generico, Data è di tipo any e il nodo può contenere qualsiasi tipo di dato. Potrebbe essere un tipo comune, un contenitore o persino un altro elenco collegato!

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

Lo specificatore <unique> permette a list_node di essere comparable. In questo modo puoi verificare se un nodo è uguale a un altro nodo, ad esempio per verificare se il tuo nodo è la testa o la coda di un elenco.

Se hai bisogno di un'implementazione più specifica, come ad esempio un nodo che gestisce solo numeri o stringhe, assicurati di cambiare il tipo di Data in modo corrispondente. Se Data è di tipo comparable, puoi confrontare il valore in Data con un altro valore per trovare un nodo specifico.

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

Elenchi collegati singoli

Il tipo più basilare di elenco collegato è un elenco collegato singolo, in cui ogni nodo contiene un riferimento al nodo successivo (un singolo collegamento). Per trasformare i tuoi nodi in un elenco, collegali tra loro utilizzando i riferimenti Next di ogni nodo.

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

Anche se i nodi sono collegati, definisci il tuo elenco collegato in una classe. In questo modo sarà più facile eseguire le funzioni utilizzando l'elenco invece di fare riferimento ogni volta al primo nodo.

# 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

Una classe linked_list base contiene solo un riferimento al nodo di testa. Per creare un'istanza della classe linked_list, collega i nodi tra loro, quindi istanzia l'elenco utilizzando il nodo di testa.

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

Per scorrere l'elenco, parti dal nodo di testa e fino al nodo di coda che segna la fine. Puoi farlo utilizzando una funzione esterna o una funzione di classe all'interno della classe linked_list. Un esempio di funzione che scorre l'intero elenco dalla testa alla coda è riportato di seguito:

# 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

Qui, la funzione TraverseList() controlla se CurrentNode contiene un riferimento Next e lo memorizza in NextNode. In caso affermativo, imposta CurrentNode su NextNode ripetutamente fino a raggiungere il nodo di coda. Il nodo di coda non ha un riferimento Next, quindi il loop si interrompe qui.

Elenchi collegati doppi

A differenza degli elenchi collegati singoli, i nodi di un elenco collegato doppio contengono anche un riferimento al nodo che li precede chiamato nodo precedente.

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

Come per i nodi a collegamento singolo, se hai bisogno di un'implementazione più specifica che gestisca solo determinati tipi di dati, assicurati di cambiare il tipo di Data in modo corrispondente.

# 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

Questo significa che puoi scorrere i nodi di un elenco collegato doppio sia in avanti che indietro. Puoi farlo, utilizzando una funzione esterna o una funzione di classe. Un esempio di funzione che scorre l'elenco dalla testa alla coda è riportato di seguito:

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

Elenchi collegati circolari

In un elenco collegato circolare, il nodo di testa è collegato al nodo di coda. Questo significa che puoi scorrere l'intero elenco passando per il nodo di coda per tornare al nodo di testa. Gli elenchi collegati circolari possono essere collegati singoli o doppi, l'unica condizione è che il nodo di testa sia collegato al nodo di coda o viceversa.

Iteratori

Un iteratore è un oggetto che ti permette di iterare un contenitore ed eseguire operazioni lungo il percorso. Può essere paragonato a una carrozza di un treno piena di passeggeri. Il treno viaggia lungo un binario, fermandosi a ogni stazione lungo il percorso. In ogni stazione, il treno esegue un task, come ad esempio l'imbarco o lo sbarco dei passeggeri. Negli elenchi collegati, ogni stazione è un nodo dell'elenco. Il treno (iteratore) percorre l'elenco scorrendo ogni nodo e può eseguire operazioni dove si ferma.

Gli iteratori sono elementi utili negli elenchi collegati perché permettono di eseguire operazioni in punti specifici, anziché solo nel nodo di testa o di coda.

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

Qui, l'iteratore contiene un riferimento all'elenco su cui sta effettuando le iterazioni e un CurrentNode che rappresenta il nodo cui l'iteratore è attualmente fermo. La funzione Next() controlla se il CurrentNode ha un nodo successivo e salta a quel nodo. Nota: Next() include gli specificatori <transacts> e <decides>. La funzione deve essere di tipo <transacts> perché aggiorna la var CurrentNode, e devi includere <decides> perché rendere Next() fallibile ti permette di sapere se hai iterato al nodo successivo o meno.

Anche se potrebbe sembrare che un iteratore debba iniziare dalla testa di un elenco, in realtà deve iniziare prima della testa. Questo permette all'iteratore di eseguire operazioni sul nodo di testa, come l'inserimento di nodi prima del nodo di testa o l'eliminazione completa del nodo di testa.

Per inizializzare l'iteratore prima della testa, puoi inizializzare CurrentNode su un nodo fittizio impostando il nodo di testa dell'elenco come nodo successivo. In Verse, non puoi accedere a List quando inizializzi CurrentNode, perché le variabili dei membri della classe non possono essere accessibili dallo stesso ambito, ma solo da ambiti diversi, ad esempio all'interno di una funzione.

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

Al contrario, per istanziare un iteratore puoi utilizzare una funzione costruttore. Un costruttore è un tipo composito che crea un'istanza della classe a cui è associato. Il costruttore definisce i valori iniziali di un oggetto e ti permette di accedere al valore List e di assegnare CurrentNode al nodo di testa.

# 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

L'inizializzazione di un iteratore di un elenco collegato doppio è più o meno la stessa, tranne per il fatto che l'inizializzazione avviene solo con i nodi a collegati doppi.

# 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

Iterazione tra i nodi

Puoi spostare l'iteratore in avanti o indietro a seconda di come è collegato il tuo elenco. Gli iteratori in un elenco collegato singolo possono muoversi solo in avanti, mentre gli iteratori in un elenco collegato doppio possono muoversi sia in avanti che indietro. Questa funzionalità è definita in due funzioni: Next() e Previous(). Ricorda che gli elenchi collegati singoli non hanno una funzione Previous(). Gli elenchi collegati circolari possono avere entrambe le funzioni, a seconda che siano collegati singoli o doppi.

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

Aggiunta di nodi

Puoi utilizzare iteratori per aggiungere nodi in specifici punti dell'elenco collegato. Quando aggiungi un nodo, devi definire con precisione la posizione in cui verrà aggiunto. Puoi aggiungere il nodo prima o dopo il nodo attuale a seconda della struttura del tuo elenco. In un elenco collegato singolo, puoi aggiungere nodi solo dopo altri nodi, perché non esiste un riferimento al nodo Previous a cui rimandare. In elenco collegato doppio, puoi aggiungere nodi prima o dopo altri nodi.

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

Qui la funzione AddNode aggiunge un nodo tra CurrentNode e il nodo successivo. Procede come segue:

• Imposta il riferimento Next di CurrentNode a NewNode.

• Impostazione del riferimento Next di NewNode a NextNode. Se non esiste un NextNode (come alla coda di un elenco), la funzione imposta semplicemente NewNode come nodo successivo.

In un elenco collegato doppio, hai la possibilità di aggiungere nodi prima o dopo CurrentNode. Puoi dividere questa funzionalità in due funzioni: AddNodeAfter() e AddNodeBefore(). L'implementazione è molto simile a quella dell'elenco collegato singolo, con la differenza che è necessario anche definire il riferimento Previous per ogni nodo.

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

Rimozione di nodi

Per eliminare un nodo, devi rimuovere tutti i riferimenti ad esso mantenendo l'ordine dell'elenco. Per fare ciò, se il nodo che vuoi rimuovere è seguito da altri nodi, devi collegare tutti i nodi prima del nodo rimosso ai nodi successivi. In un elenco collegato singolo, dato che non esiste un riferimento Previous, puoi rimuovere solo i nodi posizionati dopo CurrentNode.

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

Tieni presente che il nodo di testa può essere eliminato solo in casi particolari. Dovrai quindi definire il nodo successivo a quello di testa come nuovo nodo di testa, altrimenti l'elenco collegato non avrà un punto di partenza.

Come per l'aggiunta di nodi, l'eliminazione di nodi da un elenco collegato doppio può essere suddivisa eliminando il nodo prima o dopo il nodo corrente.

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

Codice completo

Di seguito è riportato il codice completo per ciascuna delle classi in questo esempio.

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

In autonomia

Ci sono varie strategie per potenziare gli elenchi collegato e devi esplorare diverse opzioni per arricchirne le funzionalità. Ecco alcune idee per migliorare i tuoi elenchi collegati:

• E se ogni elenco contenesse anche un riferimento al nodo di coda?

• Puoi implementare un metodo ToString() per stampare il contenuto dei tuoi nodi?

• E per invertire un elenco? Puoi implementare una funzionalità Length()?

• Puoi aggiungere altri metodi all'iteratore per eseguire nuove operazioni?