Introduction aux Listes Chaînées

Une liste chaînée est une structure de données linéaire dans laquelle chaque élément (appelé nœud) est relié au suivant par un pointeur. Cette organisation permet de gérer dynamiquement l’espace mémoire, contrairement aux tableaux dont la taille est fixe une fois définie. Chaque nœud contient une valeur (ou données) ainsi qu’un lien vers le nœud suivant. Le dernier nœud de la liste ne pointe vers rien : son pointeur est donc défini à None.

Pourquoi utiliser une liste chaînée plutôt qu’un tableau ?

Lorsqu’on manipule des collections de données dont la taille varie fréquemment, les listes chaînées offrent une plus grande souplesse. Par exemple, l’ajout ou la suppression d’un élément ne nécessite pas de décaler les autres éléments, ce qui est le cas avec un tableau. Cela rend ces opérations plus efficaces dans certains contextes, bien qu’elles soient moins performantes pour accéder rapidement à un élément donné, puisqu’il faut le rechercher en parcourant la liste depuis le début.

Comprendre la Structure d’un Nœud

Un nœud est une entité qui encapsule une valeur ainsi qu’un pointeur vers un autre nœud. En Python, on le modélise par une classe simple :

class Node:
    def __init__(self, data):
        self.data = data      # Stocke la valeur du nœud
        self.next = None      # Pointeur vers le nœud suivant (initialement vide)

Dans ce code, le constructeur initialise le nœud avec la donnée reçue en paramètre, et définit son pointeur next à None, ce qui signifie qu’il n’est relié à aucun autre nœud pour l’instant.

Mise en place d’une Liste Chaînée

Une liste chaînée commence avec un attribut head, c’est-à-dire une référence vers le premier nœud de la liste. Si cette référence vaut None, cela signifie que la liste est vide.

class LinkedList:
    def __init__(self):
        self.head = None  # La liste est initialement vide

Cette classe LinkedList sert de conteneur à tous les nœuds. En démarrant avec head = None, on crée une structure vide à laquelle on pourra ajouter des nœuds progressivement.

Ajouter un élément au début

L’ajout au début est l’opération la plus simple et la plus rapide, car il suffit de créer un nouveau nœud et de le placer en tête, en ajustant simplement deux pointeurs :

def add_at_start(self, data):
    new_node = Node(data)        # Création d’un nouveau nœud avec la donnée
    new_node.next = self.head    # Ce nœud pointe vers l’ancien premier nœud
    self.head = new_node         # Le head est mis à jour pour désigner le nouveau nœud

Ce procédé consiste à rattacher le nouveau nœud à l’ancien début de la liste, puis à redéfinir le début de la liste comme étant ce nouveau nœud.

Exemple :

On possède la liste suivante :

On ajoute l'instruction :

ll.add_at_start(5)

Pour obtenir :

Ici, le nouveau nœud est devenu le début de la liste head. Et l’ancien début de la liste est maintenant en deuxième position.

Ajouter un élément à la fin

L’ajout à la fin est plus coûteux, car il faut parcourir toute la liste pour trouver le dernier nœud avant d’y rattacher le nouveau.

def add_at_end(self, data):
    new_node = Node(data)              # Création du nouveau nœud
    if not self.head:                  # Si la liste est vide, le nouveau nœud devient le head
        self.head = new_node
        return
    current = self.head                # Début du parcours
    while current.next:                # On continue tant qu’on n’a pas atteint le dernier nœud
        current = current.next
    current.next = new_node            # Ajout du nœud à la fin

Ce code gère aussi le cas où la liste est vide : dans ce cas, il n’y a pas besoin de parcourir quoi que ce soit, on place simplement le nouveau nœud en tête.

Supprimer un élément

La suppression consiste à parcourir la liste pour identifier le nœud à supprimer, puis à modifier le pointeur du nœud précédent pour qu’il ignore celui à supprimer.

def remove_node(self, key):
    current = self.head
    if current and current.data == key:  # Si le premier nœud contient la valeur
        self.head = current.next         # On le saute et on définit le suivant comme nouveau head
        current = None                   # Suppression du nœud
        return

    prev = None
    while current and current.data != key:
        prev = current
        current = current.next

    if not current:                      # Si l’élément n’est pas trouvé, on quitte
        return

    prev.next = current.next             # On relie le nœud précédent au suivant
    current = None                       # Le nœud est retiré

Ici encore, on traite le cas particulier où l’élément à supprimer est en tête de liste. Si ce n’est pas le cas, on avance jusqu’à ce qu’on le trouve, puis on l’exclut de la chaîne.

Exemple

On possède la liste suivante :

On ajoute l'instruction :

ll.remove_node(10)

Pour obtenir :

Complexité des Opérations

Les listes chaînées offrent un bon compromis pour certaines opérations. Ajouter un élément au début est immédiat (temps constant), tandis qu’ajouter à la fin ou supprimer un élément nécessite un parcours complet (temps linéaire) si on ne garde pas de pointeur vers la fin.

Opération	Complexité temporelle
Insertion au début	O(1)
Insertion à la fin	O(n)
Suppression d’un nœud	O(n)
Recherche d’un élément	O(n)

Exemple complet : Liste Chaînée en Python

Voici une classe complète implémentant les principales opérations vues ci-dessus :

class Node:
    def __init__(self, data):
        self.data = data        # Donnée stockée
        self.next = None        # Pointeur vers le prochain nœud

class LinkedList:
    def __init__(self):
        self.head = None        # Début de la liste

    def add_at_start(self, data):
        new_node = Node(data)         # Création du nouveau nœud
        new_node.next = self.head     # Rattachement à l’ancien head
        self.head = new_node          # Mise à jour du head

    def add_at_end(self, data):
        new_node = Node(data)
        if not self.head:             # Cas d’une liste vide
            self.head = new_node
            return
        current = self.head
        while current.next:           # Parcours jusqu’au dernier nœud
            current = current.next
        current.next = new_node       # Ajout du nœud en fin de liste

    def remove_node(self, key):
        current = self.head
        if current and current.data == key:   # Suppression en tête
            self.head = current.next
            current = None
            return
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next
        if not current:                       # Élément non trouvé
            return
        prev.next = current.next              # Suppression du nœud
        current = None

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")   # Affichage des valeurs
            current = current.next
        print("None")                         # Fin de la liste

# Exemple d'utilisation :
ll = LinkedList()
ll.add_at_start(10)
ll.add_at_end(20)
ll.add_at_start(5)
ll.display()          # Affiche : 5 -> 10 -> 20 -> None
ll.remove_node(10)
ll.display()          # Affiche : 5 -> 20 -> None

Les listes chaînées

All work licensed under CC BY-NC-SA 4.0