Introduction

Les listes chaînées sont une structure de données qui représente une collection linéaire de nœuds. Une caractéristique spécifique des listes chaînées est que l’ordre des nœuds n’est pas dicté par leur présence en mémoire, mais plutôt par les pointeurs que chaque nœud possède vers le nœud suivant dans la séquence.

Il existe plusieurs types de listes chaînées :

• Listes chaînées simples – Une liste chaînée classique, comme celle présentée dans l’image ci-dessus. Les nœuds des listes à liens simples contiennent un pointeur vers le nœud suivant de la liste.
• Listes doublement chaînées – Ce type de liste chaînée contient à la fois un pointeur vers le nœud suivant, mais aussi un pointeur vers le nœud précédent de la liste.
• Listes chaînées circulaires – Au lieu de contenir un pointeur nul à la fin de la liste, le dernier nœud de ces listes contient un pointeur vers le premier nœud, ce qui les rend circulaires.

Nous aborderons ici la liste chainée simple.

Liste chaînée simple

Une seule liste chaînée est la plus simple de toutes les variantes de listes chaînées. Chaque nœud d’une liste chaînée unique contient un élément et une référence à l’élément suivant, et c’est tout.

Dans cette partie, nous verrons comment créer un nœud pour la liste chaînée unique ainsi que les fonctions pour les différents types d’insertion, de parcourt et de suppression.

Création de la classe de nœuds

La première chose à faire est de créer une classe pour les nœuds. Les objets de cette classe seront les nœuds réels que nous insérerons dans notre liste de liens. Nous savons qu’un nœud pour une seule liste chaînée contient l’objet et la référence au nœud suivant. Par conséquent, notre classe de nœuds contiendra deux variables membres : item et ref. La valeur de l’élément sera fixée par la valeur passée dans le constructeur, tandis que la référence sera initialement fixée à zéro.

Exécutez le script suivant :

class Node:
    def __init__(self, data):
        self.item = data
        self.ref = None

Création de la classe de liste chainée simple

Ensuite, nous devons créer une classe pour la liste des liens. Cette classe contiendra les méthodes pour insérer, supprimer, parcourir et trier la liste. Au départ, la classe ne contiendra qu’un seul membre start_node qui pointera vers le nœud de départ ou le premier nœud de la liste. La valeur de start_node sera fixée à null à l’aide du constructeur puisque la liste liée sera vide au moment de sa création. Le script suivant crée une classe pour la liste chaînée.

class LinkedList:
    def __init__(self):
        self.start_node = None

Nous avons maintenant créé une classe pour notre liste unique. L’étape suivante consiste à ajouter une fonction d’insertion pour insérer des éléments dans la liste chaînée. Mais avant cela, nous allons ajouter une fonction pour parcourir une liste chaînée. Cette fonction nous aidera à lire les données de notre liste.

Parcourir les éléments de la liste liée

Le code Python pour la fonction de parcours est le suivant. Ajoutez la fonction ci-dessous à la classe LinkedList que nous avons créée dans la dernière section.

def traverse_list(self):
    if self.start_node is None:
        print("Pas d'élément dans la liste")
        return
    else:
        n = self.start_node
        while n is not None:
            print(n.item , " ")
            n = n.ref

Voyons ce qui se passe dans la fonction ci-dessus. Cette fonction comporte deux parties principales. Premièrement, elle vérifie si la liste chaînée est vide ou non. Le code suivant vérifie cela :

    if self.start_node is None:
        print("Pas d'élément dans la liste")
        return

Si la liste chaînée est vide, cela signifie qu’il n’y a pas d’élément à itérer. Dans ce cas, la fonction traverse_list() affiche simplement l’instruction que la liste n’a pas d’élément.

Sinon, si la liste comporte un élément, le code suivant s’exécutera :

        n = self.start_node
        while n is not None:
            print(n.item , " ")
            n = n.ref

Comme nous l’avons dit précédemment, la variable de départ contiendra une référence aux premiers nœuds. Par conséquent, nous initialisons une variable n avec la variable de départ. Ensuite, nous exécutons une boucle qui s’exécute jusqu’à ce que n devienne nul. À l’intérieur de la boucle, nous imprimons l’élément stocké au nœud actuel, puis nous fixons la valeur de la variable n à n.ref, qui contient la référence au nœud suivant. La référence du dernier noeud est None puisqu’il n’y a pas de noeud après cela. Par conséquent, lorsque n devient None, la boucle se termine.

Maintenant, nous avons une fonction pour parcourir une liste chaînée, nous verrons dans un prochain article  comment nous pouvons ajouter des éléments à une  liste chaînée.