Listes chaînées

Les listes chaînées sont une structure de données courante en informatique. Vous pouvez utiliser une liste chaînée pour représenter une playlist musicale ou suivre un historique d'actions, par exemple.

Vue d'ensemble

Une liste chaînée est une structure de données linéaire dans laquelle chaque élément stocke une référence à l'élément suivant de la liste. Chaque élément d'une liste chaînée est appelé un nœud. Un nœud est un conteneur qui contient des données et une référence au nœud suivant.

L'enchaînement de différents nœuds en séquence crée une liste chaînée. Le premier nœud de la liste est appelé le nœud de tête et le dernier nœud est appelé le nœud de queue. Pour parcourir la liste, nous partons de la tête et passons à l'élément suivant en utilisant la référence dans chaque nœud.

Quand l'utiliser

Les listes chaînées constituent un bon point de départ pour l'implémentation d'autres structures de données telles que les piles ou les files d'attente. Les listes chaînées sont un moyen simple de stocker des données pour un accès séquentiel et elles permettent l'insertion rapide de nouveaux éléments. Contrairement aux matrices, les listes chaînées ne sont pas contiguës (les unes à côté des autres) en mémoire. Cela signifie qu'un nœud peut se trouver n'importe où dans la mémoire et que la référence au nœud suivant indique son emplacement. Pour insérer ou supprimer des nœuds dans une liste chaînée, il suffit de modifier les références au nœud suivant.

Quand ne pas l'utiliser

Si votre programme nécessite un accès aléatoire aux éléments (comme le choix d'un joueur au hasard dans une liste), les listes chaînées n'offrent pas cette fonctionnalité. Les listes chaînées sont moins efficaces que les matrices si l'on doit accéder à un nœud particulier au milieu de la liste, car il faut partir de la tête de la liste et la parcourir jusqu'au nœud spécifique recherché.

Implémentation dans Verse

L'API Verse ne dispose pas d'une implémentation intégrée des listes chaînées, mais vous pouvez en créer une vous-même.

Les listes chaînées sont composées de nœuds, et vous devrez définir une classe pour les représenter. Un exemple de type générique de nœud est présenté ci-dessous :

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

Ici, la variable d'option Next stocke une référence au nœud suivant dans la liste, qui est de type list_node. Notez que Next doit être une variable d'option, car un nœud peut ne pas toujours avoir un nœud suivant vers lequel pointer (comme le nœud de queue d'une liste chaînée). Si vous souhaitez modifier le chaînage de votre liste de manière dynamique, Next doit être une var. Le nœud contient également une valeur, qui est stockée dans Data. Étant donné qu'il s'agit d'un type de nœud générique, Data est de type any, et le nœud peut contenir n'importe quel type de données. Il pourrait s'agir d'un type commun, d'un conteneur ou même d'une autre liste chaînée !

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

Le spécificateur <unique> permet à list_node d'être comparable. Cela vous permet de vérifier si un nœud est égal à un autre nœud, par exemple de vérifier si votre nœud est la tête ou la queue d'une liste.

Si vous avez besoin d'une implémentation plus spécifique, comme un nœud qui ne gère que des nombres ou des chaînes, assurez-vous de changer le type de Data de manière à le faire correspondre. Si Data est de type comparable, vous pouvez comparer la valeur de Data à une autre valeur pour trouver un nœud spécifique.

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

Listes simplement chaînées

Le type le plus élémentaire de liste chaînée est la liste simplement chaînée, où chaque nœud contient une référence au nœud suivant (un seul lien). Pour transformer vos nœuds en liste, reliez-les entre eux en utilisant les références Next dans chaque nœud.

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

Bien que vos nœuds soient liés, il vous faudra définir votre liste chaînée dans une classe. Il sera ainsi plus facile d'exécuter des fonctions à l'aide de votre liste, plutôt que de référencer votre premier nœud à chaque fois.

# 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

Une classe linked_list élémentaire ne contient qu'une référence au nœud de tête. Pour créer une instance de votre classe linked_list, liez vos nœuds ensemble, puis instanciez votre liste à l'aide du nœud de tête.

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

Pour parcourir la liste, commencez par le nœud de tête et itérez la liste, le nœud de queue marquant la fin. Vous pouvez passer par une fonction externe ou par une fonction de classe à l'intérieur de votre classe linked_list. Un exemple de fonction qui parcourt la liste entière de la tête à la queue est fourni ci-dessous :

# 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

Ici, la fonction TraverseList() vérifie si CurrentNode contient une référence Next et la stocke dans NextNode. Si c'est le cas, elle définit CurrentNode sur NextNode de façon répétée jusqu'à ce qu'elle atteigne le nœud de queue. Le nœud de queue n'a pas de référence Next ; la boucle s'arrête donc ici.

Listes doublement chaînées

Contrairement aux listes simplement chaînées, les nœuds d'une liste doublement chaînée contiennent également une référence au nœud qui les précède, appelé Previous, nœud précédent.

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

Comme pour les nœuds chaînés individuellement, si vous avez besoin d'une implémentation plus spécifique qui ne gère que certains types de données, assurez-vous de modifier le type de Data de manière à le faire correspondre.

# 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

Cela signifie que vous pouvez parcourir les nœuds d'une liste doublement chaînée tant vers l'avant que vers l'arrière. Cela peut se faire dans une fonction externe ou dans une fonction de classe. Un exemple de fonction qui parcourt une liste de la tête à la queue et inversement est fourni ci-dessous :

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

Listes chaînées circulaires

Dans une liste chaînée circulaire, le nœud de tête est lié au nœud de queue. Cela signifie que vous pouvez parcourir toute la liste en passant par le nœud de queue pour revenir au nœud de tête. Les listes chaînées circulaires peuvent être simplement ou doublement chaînées, la seule condition étant que le nœud de tête soit relié au nœud de queue ou vice versa.

Itérateurs

Un itérateur est un objet qui permet de parcourir un conteneur et d'effectuer des opérations en cours de route. On peut l'assimiler à un wagon de train rempli de passagers. Le train se déplace sur une voie ferrée, s'arrêtant à chaque gare en cours de route. À chaque gare, le train effectue une tâche, comme l'embarquement ou le débarquement de passagers. En ce qui concerne les listes chaînées, chaque gare est un nœud de la liste. Le train (itérateur) parcourt la liste jusqu'à chaque nœud et peut effectuer des opérations où il s'arrête.

Les itérateurs sont utiles pour les listes chaînées, car ils permettent d'effectuer des opérations à des endroits spécifiques, plutôt qu'au nœud de tête ou de queue seulement.

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

Ici, l'itérateur contient une référence à la liste sur laquelle il itère et un CurrentNode où l'itérateur est actuellement arrêté. La fonction Next() vérifie si le CurrentNode a un nœud après lui, puis saute vers ce nœud. Notez que Next() inclut ici les spécificateurs <transacts> et <decides>. La fonction doit être <transacts> car elle met à jour la variable CurrentNode, et vous souhaitez inclure <decides> car rendre Next() faillible vous permet de savoir si vous avez effectué une itération vers le nœud suivant ou non.

Même s'il peut sembler qu'un itérateur doive commencer en tête d'une liste, il doit en fait commencer avant la tête. L'itérateur peut ainsi effectuer des opérations sur le nœud de tête, comme l'insertion de nœuds avant le nœud de tête ou la suppression complète du nœud de tête.

Pour initialiser l'itérateur avant la tête, vous pouvez initialiser CurrentNode sur un nœud factice avec la tête de la liste comme nœud suivant. Dans Verse, vous ne pouvez pas accéder à la liste lors de l'initialisation de CurrentNode, car les variables des membres de classe ne sont pas accessibles à partir de la même étendue, mais uniquement à partir d'étendues différentes, comme dans une fonction.

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

Au lieu de cela, pour instancier un itérateur, vous pouvez utiliser une fonction de constructeur. Un constructeur est un type composite qui crée une instance de la classe à laquelle il est associé. Le constructeur définit les valeurs initiales d'un objet et vous permet d'accéder à la valeur de List et d'assigner CurrentNode à son nœud de tête.

# 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'initialisation d'un itérateur pour une liste doublement chaînée est à peu près identique, sauf que l'initialisation n'a lieu qu'avec des nœuds doublement chaînés.

# 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

Itération entre les nœuds

Vous pouvez déplacer l'itérateur vers l'avant ou vers l'arrière en fonction de l'enchaînement de votre liste. Les itérateurs d'une liste simplement chaînée ne peuvent se déplacer que vers l'avant, tandis que les itérateurs d'une liste doublement chaînée peuvent se déplacer dans les deux sens. Cette fonctionnalité est définie dans deux fonctions, Next() et Previous(). Rappelez-vous que les listes simplement chaînées n'ont pas de fonction Previous(). Les listes chaînées circulaires peuvent avoir l'une ou l'autre fonction, selon qu'elles sont simplement ou doublement chaînées.

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

Ajout de nœuds

Vous pouvez utiliser des itérateurs pour ajouter des nœuds à des endroits spécifiques de la liste chaînée. Lors de l'ajout d'un nœud, il est important de choisir l'endroit où il sera ajouté. Vous pouvez ajouter le nœud avant ou après le nœud actuel, mais cela dépend de la structure de votre liste. Dans une liste simplement chaînée, on ne peut ajouter des nœuds qu'après d'autres nœuds, car il n'existe pas de référence de nœud Previous à laquelle se référer. Dans une liste doublement chaînée, vous pouvez ajouter des nœuds avant ou après d'autres nœuds.

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

Ici, la fonction AddNode ajoute un nœud entre CurrentNode et le nœud qui le suit. Elle procède comme suit :

• Définition de la référence Next du CurrentNode sur NewNode.

• Définition de la référence Next de NewNode sur NextNode. S'il n'y a pas de NextNode (comme à la fin d'une liste), la fonction définit seulement NewNode comme le nœud suivant.

Dans une liste doublement chaînée, vous avez la possibilité d'ajouter des nœuds avant ou après CurrentNode. Vous pouvez diviser cette fonctionnalité en deux fonctions, AddNodeAfter() et AddNodeBefore(). L'implémentation est très similaire à celle de la liste simplement chaînée, mais vous devez également vous souvenir de définir la référence Previous pour chaque nœud.

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

Suppression de nœuds

Pour supprimer un nœud, vous devez supprimer toute référence à ce nœud tout en préservant l'ordre de la liste. Pour ce faire, si le nœud que vous souhaitez supprimer est suivi d'autres nœuds, vous devez lier tous les nœuds situés avant le nœud supprimé aux nœuds situés après lui. Dans une liste simplement chaînée, puisque vous n'avez pas de référence Previous, vous ne pouvez supprimer que les nœuds situés après le 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")

Notez que le nœud de tête ne peut être supprimé que dans des cas spéciaux. Vous devez alors définir le nœud qui suit le nœud de tête comme nouveau nœud de tête, sinon votre liste chaînée n'aura pas de point de départ.

Comme pour l'ajout de nœuds, la suppression de nœuds dans une liste doublement chaînée peut être fractionnée par suppression du nœud précédant ou suivant le nœud actuel.

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

Code complet

Voici le code complet pour chacune des classes de cet exemple.

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

À vous de jouer

Il existe de nombreuses façons d'améliorer les listes chaînées, et vous devriez explorer différentes manières d'ajouter des fonctionnalités. Voici quelques idées d'améliorations que vous pouvez apporter à vos listes chaînées :

• Et si chaque liste stockait également une référence au nœud de queue ?

• Pouvez-vous implémenter une méthode ToString() pour afficher le contenu de vos nœuds ?

• Qu'en est-il de l'inversion d'une liste ? Pouvez-vous implémenter une fonctionnalité Length() ?

• Pouvez-vous ajouter plus de méthodes à l'itérateur pour effectuer de nouvelles opérations ?