Implémenter une liste chaînée en Python étape par étape

La liste chaînée est sans doute la première structure de données qu’un développeur devrait coder à la main pour comprendre la mécanique des pointeurs et la différence entre référence et copie. En Python, on n’en a presque jamais besoin en production — list et collections.deque couvrent 99 % des cas. Mais l’écrire de zéro reste l’exercice formateur par excellence : ça force à raisonner en termes d’invariants, à manipuler des références, et à mesurer ce que coûte chaque opération. Ce tutoriel construit une liste chaînée simple en Python, avec toutes les opérations classiques, des tests qui vérifient la correction, et un détour par la détection de cycles avec l’algorithme du lièvre et de la tortue.

Pour la vue d’ensemble des structures de données et des algorithmes, lire d’abord le guide principal Algorithmes et structures de données : repères 2026 pour devs.

Prérequis

• Python 3.10 ou plus récent (pour les annotations X | None sans typing)
• Un éditeur capable de lancer un script (VS Code, PyCharm, ou simplement python tonfichier.py en ligne de commande)
• Bases du langage : classes, méthodes, exceptions
• Niveau attendu : débutant en algorithmique, intermédiaire en Python
• Temps estimé : 45 minutes pour suivre, 90 minutes pour expérimenter

Étape 1 — Comprendre le modèle mental

Une liste chaînée est une suite de boîtes appelées nœuds. Chaque nœud contient deux choses : une donnée (un nombre, une chaîne, n’importe quel objet) et un pointeur vers le nœud suivant. Le dernier nœud pointe vers None pour signaler la fin. La liste elle-même n’est qu’une référence vers le premier nœud, qu’on appelle la tête. Si la tête vaut None, la liste est vide. C’est tout. Cette simplicité est ce qui rend la structure pédagogiquement précieuse : il n’y a pas d’astuce cachée.

La différence essentielle avec un tableau, c’est que les nœuds ne sont pas contigus en mémoire. Le système d’exploitation alloue chaque nœud où il a de la place. C’est ce qui explique le coût de l’accès au n-ième élément : on ne peut pas faire un calcul d’adresse comme dans un tableau, il faut suivre la chaîne, ce qui prend O(n). En contrepartie, insérer un élément en tête ne coûte qu’une réaffectation de pointeur — O(1) garanti. Toute la suite du tutoriel s’appuie sur cette intuition.

Étape 2 — Définir la classe Node

Le premier code qu’il faut écrire est la classe qui représente un nœud. On lui donne deux attributs : data pour la valeur stockée, et next pour la référence vers le nœud suivant. On utilise __slots__ pour deux raisons : économiser de la mémoire (chaque instance pèse environ 30 % de moins que la version avec __dict__), et empêcher les fautes de frappe sur les noms d’attributs — si vous écrivez node.nxt = ... par erreur, Python lèvera une AttributeError au lieu de créer silencieusement un nouvel attribut.

class Node:
    __slots__ = ('data', 'next')

    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node

    def __repr__(self):
        return f"Node({self.data!r})"

À l’exécution, créer un nœud isolé donne Node(42) avec next à None. Si vous tapez n = Node(1) ; n.next = Node(2), vous venez de créer une liste chaînée de deux éléments à la main, sans classe enveloppe. La classe LinkedList que nous écrivons à l’étape suivante n’est qu’une commodité qui mémorise la tête et expose des opérations propres.

Étape 3 — Construire la classe LinkedList et l’opération push_front

La liste possède deux attributs internes : head, la référence vers le premier nœud (ou None si la liste est vide), et _size, un compteur qu’on maintient à jour pour répondre à len() en O(1). Maintenir un compteur évite de devoir parcourir toute la liste à chaque appel de len, ce qui transformerait une opération qu’on attend rapide en boucle linéaire silencieuse.

class LinkedList:
    def __init__(self):
        self.head = None
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self.head is None

    def push_front(self, data):
        """Insère en tête. O(1)."""
        self.head = Node(data, self.head)
        self._size += 1

L’astuce de push_front est dans la ligne self.head = Node(data, self.head). On crée le nouveau nœud avec son next qui pointe vers l’ancienne tête, puis on remplace la tête par ce nouveau nœud. Trois opérations atomiques : allocation, assignation interne, réaffectation de la tête. Aucune ne dépend de la taille de la liste, donc c’est bien O(1). Si vous testez ll = LinkedList(); ll.push_front(3); ll.push_front(2); ll.push_front(1), vous obtenez la chaîne 1 → 2 → 3 → None avec len(ll) == 3.

Étape 4 — Implémenter pop_front et le parcours

Le retrait en tête est le miroir exact de l’insertion en tête. On récupère la donnée stockée à la tête, on déplace la tête vers le nœud suivant, et on décrémente le compteur. Là encore, aucune dépendance à la taille — O(1). Le seul cas spécial est la liste vide : on choisit de lever une IndexError par cohérence avec list.pop() en Python, qui se comporte ainsi sur une liste vide.

    def pop_front(self):
        """Retire et renvoie la tête. O(1)."""
        if self.head is None:
            raise IndexError("pop_front from empty list")
        data = self.head.data
        self.head = self.head.next
        self._size -= 1
        return data

    def __iter__(self):
        """Itération naturelle : for x in ll."""
        current = self.head
        while current is not None:
            yield current.data
            current = current.next

    def __repr__(self):
        return ' -> '.join(repr(x) for x in self) + ' -> None'

L’implémentation de __iter__ avec yield est élégante et économe : Python crée un générateur qui retient la position courante entre deux appels à next(). Cela permet d’écrire for x in ll, list(ll), ou any(x > 10 for x in ll) sans construire de liste intermédiaire. Si vous avez tapé tout le code jusque-là, lancez maintenant ll.pop_front() sur la liste de l’étape 3 : la fonction renvoie 1 et la chaîne devient 2 → 3 → None.

Étape 5 — Insertion en queue (et pourquoi elle coûte O(n))

Insérer en queue est instructif parce qu’il révèle la limite de la liste chaînée simple. Comme on n’a qu’un pointeur vers la tête, il faut traverser toute la chaîne pour trouver le dernier nœud avant d’y attacher le nouveau. C’est exactement le coût qu’on paye à chaque appel : O(n). Si vous pensez en faire beaucoup, gardez en plus un pointeur vers la queue (variante doublement liée) ou utilisez collections.deque, qui est implémentée comme un tableau de blocs et offre O(1) aux deux extrémités.

    def push_back(self, data):
        """Insère en queue. O(n) sans pointeur de queue."""
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self._size += 1
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = new_node
        self._size += 1

Le test du head is None au début gère le cas spécial de la liste vide : on ne peut pas chaîner sur un nœud qui n’existe pas. Ensuite la boucle while current.next is not None s’arrête sur le dernier nœud existant, et on lui accroche le nouveau. Pour vérifier le coût en pratique, mesurez avec timeit le temps que met push_back sur une liste de 100, 1 000, et 10 000 éléments — vous verrez les durées croître linéairement, ce qui valide visuellement la complexité O(n).

Étape 6 — Recherche et suppression par valeur

Chercher une valeur dans une liste chaînée se fait par balayage linéaire — aucune optimisation possible sans structure auxiliaire. La méthode find ci-dessous renvoie l’index du premier nœud qui contient la valeur, ou -1 si elle n’apparaît pas. La méthode remove suit la même logique mais doit gérer un détail subtil : pour décrocher un nœud, il faut un pointeur sur le nœud précédent. On garde donc current sur le nœud précédent et on regarde current.next.data pour décider d’enlever le nœud suivant.

    def find(self, data):
        """Renvoie l'index de la première occurrence ou -1. O(n)."""
        current = self.head
        index = 0
        while current is not None:
            if current.data == data:
                return index
            current = current.next
            index += 1
        return -1

    def remove(self, data):
        """Retire la première occurrence. Renvoie True si trouvé. O(n)."""
        if self.head is None:
            return False
        if self.head.data == data:
            self.head = self.head.next
            self._size -= 1
            return True
        current = self.head
        while current.next is not None:
            if current.next.data == data:
                current.next = current.next.next
                self._size -= 1
                return True
            current = current.next
        return False

Notez le cas spécial pour la tête dans remove. Si la valeur cherchée est dans le premier nœud, on n’a pas de précédent à modifier — il suffit de réaffecter la tête. C’est un piège classique des listes chaînées : oublier ce cas conduit à une AttributeError ou, pire, à une suppression silencieuse incomplète. La règle générale est : chaque fois que vous parcourez une liste chaînée pour modifier les liens, demandez-vous si la tête est un cas particulier, et testez explicitement la liste vide.

Étape 7 — Inverser la liste sur place

L’inversion d’une liste chaînée est l’exercice de référence pour évaluer la maîtrise de la manipulation de pointeurs. L’idée est de remonter la chaîne en redirigeant chaque next vers le nœud précédent. On utilise trois variables : prev qui suit le nœud précédent, current sur le nœud courant, et next_node qui mémorise temporairement le suivant pour ne pas le perdre quand on retourne le pointeur.

    def reverse(self):
        """Inverse la liste sur place. O(n) en temps, O(1) en espace."""
        prev = None
        current = self.head
        while current is not None:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev

Le déroulé sur la liste 1 → 2 → 3 → None donne, étape par étape : (prev=None, cur=1) → on sauve next=2, on retourne 1.next=None, prev devient 1, cur passe à 2. Puis (prev=1, cur=2) → next=3, 2.next=1, prev=2, cur=3. Puis (prev=2, cur=3) → next=None, 3.next=2, prev=3, cur=None. La boucle s’arrête, on affecte head=3, et la liste devient 3 → 2 → 1 → None. Aucune allocation supplémentaire : on ne fait que retourner les pointeurs, ce qui donne O(1) en mémoire.

Étape 8 — Détecter un cycle avec l’algorithme de Floyd

Une liste chaînée mal gérée peut contenir un cycle : un nœud qui pointe vers un nœud précédent dans la chaîne. Si vous itérez naïvement, vous ne sortez jamais de la boucle. L’algorithme de Floyd (aussi appelé du lièvre et de la tortue) détecte les cycles en O(n) temps et O(1) mémoire. Il fait avancer deux pointeurs à des vitesses différentes : un pas à la fois pour la tortue, deux pas pour le lièvre. S’il y a un cycle, le lièvre rattrape forcément la tortue. Sinon, le lièvre tombe sur None.

    def has_cycle(self):
        """Détecte un cycle. O(n) en temps, O(1) en espace."""
        slow = self.head
        fast = self.head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

Pour tester, créez une liste de quelques éléments puis fabriquez un cycle artificiellement : ll.head.next.next.next = ll.head. La méthode renvoie True. La comparaison slow is fast utilise is et non ==, parce qu’on compare l’identité des nœuds (même objet en mémoire), pas l’égalité de leurs données. Cette distinction est cruciale : deux nœuds différents pourraient stocker la même valeur sans être le même objet.

Étape 9 — Vérification

Une fois toutes les méthodes en place, on enchaîne un scénario de test qui exerce chaque opération. Un test de bout en bout couvre les cas nominaux et plusieurs cas limites — liste vide, suppression de la tête, suppression d’un élément absent. Si une seule assertion échoue, vous avez un bug à isoler avant d’aller plus loin. Cette discipline du test après implémentation est plus rentable qu’on le croit : elle attrape les régressions au moment où on les introduit, pas trois jours plus tard.

if __name__ == "__main__":
    ll = LinkedList()
    assert ll.is_empty() and len(ll) == 0

    ll.push_front(3)
    ll.push_front(2)
    ll.push_front(1)
    assert list(ll) == [1, 2, 3]
    assert len(ll) == 3

    ll.push_back(4)
    assert list(ll) == [1, 2, 3, 4]

    assert ll.find(3) == 2
    assert ll.find(99) == -1

    assert ll.remove(2) is True
    assert list(ll) == [1, 3, 4]
    assert ll.remove(99) is False

    assert ll.pop_front() == 1
    assert list(ll) == [3, 4]

    ll.reverse()
    assert list(ll) == [4, 3]

    assert ll.has_cycle() is False
    print("Tous les tests passent.")

Si vous lancez ce fichier avec python liste_chainee.py, vous devez voir s’afficher Tous les tests passent. sans aucune AssertionError. Si une assertion échoue, le message indique précisément la ligne et l’expression fausse, ce qui suffit en général à localiser le bug. À ce stade, vous avez une liste chaînée fonctionnelle et testée. La suite naturelle est d’expérimenter : ajouter une méthode insert_at(index, data), comparer les performances avec collections.deque sur 100 000 insertions en tête, ou réimplémenter en doublement chaîné avec un pointeur vers la queue.

Erreurs fréquentes

Erreur	Cause	Solution
AttributeError: 'NoneType' object has no attribute 'next'	Parcours sans tester si on a atteint la fin	Toujours boucler sur while current is not None, pas sur while current.next is not None sans précaution
Suppression incomplète de la tête	Cas spécial oublié dans remove	Tester explicitement self.head.data == data avant la boucle
Liste qui paraît tronquée après reverse	Inversion sans mettre à jour self.head à la fin	Affecter self.head = prev après la boucle, pas self.head = current qui vaut None
Boucle infinie au parcours	Cycle introduit par erreur, ou current = current.next oublié	Garder un compteur de tour avec une borne supérieure pour le déboguer, ou lancer has_cycle
IndexError à pop_front sur une liste qu’on croyait non vide	Retraits successifs sans vérification	Toujours tester is_empty() avant pop_front, ou attraper l’exception

Quand préférer la liste chaînée à la liste Python

La réponse honnête : presque jamais en Python. La list standard, malgré sa nature de tableau dynamique, surclasse la liste chaînée maison sur quasiment tous les usages courants — elle bénéficie d’une implémentation en C et d’une localité de cache excellente. La liste chaînée garde un avantage théorique pour les insertions et suppressions au milieu quand vous avez déjà un pointeur sur le nœud, mais ce cas se présente rarement en pratique. Là où elle reste indispensable, c’est dans les langages bas-niveau (C, C++, Rust) pour construire des structures plus complexes : files de tâches d’un noyau, allocateurs mémoire, graphes éparses.

L’autre cas d’usage légitime est pédagogique. Une fois que vous avez écrit cette classe, vous comprenez les arbres (qui généralisent à plusieurs branches), les graphes (qui généralisent encore en autorisant les cycles), et les structures plus avancées comme les listes par sauts (skip lists). C’est cette familiarité qui rend ensuite plus rapides la lecture du code source de la stdlib Python ou des conteneurs C++ — vous reconnaissez les patterns au lieu de les redécouvrir.

Variantes utiles à connaître

La liste doublement chaînée ajoute à chaque nœud un pointeur prev qui référence le nœud précédent. Le coût mémoire double sur les pointeurs, mais on gagne deux capacités précieuses : retirer un nœud en O(1) quand on le tient déjà, et parcourir la chaîne dans les deux sens. C’est exactement la structure utilisée par collections.OrderedDict historiquement, et plus largement par les implémentations de cache LRU où il faut déplacer rapidement un nœud en tête sur chaque accès.

La liste circulaire fait pointer le dernier nœud vers la tête plutôt que vers None. Cette variante sert dans les systèmes à tour de rôle — ordonnanceurs, jeux de table, files d’attente cycliques pour des buffers de taille fixe. La détection d’arrêt change : on ne s’arrête plus sur None, mais quand on revient sur la tête. Ça oblige à mémoriser le point de départ, et c’est l’une des erreurs les plus fréquentes dans l’implémentation à la main.

Tutoriels suivants

• Coder une table de hachage en Python étape par étape — on passe de l’accès linéaire de la liste chaînée à l’accès en O(1) moyen par clé.
• Programmer le tri rapide (quicksort) en Python — on applique la stratégie diviser-pour-régner sur un tableau, avec partition de Hoare.
• Implémenter le parcours BFS sur un graphe en Python — on étend l’idée du parcours linéaire à une structure plus riche.

Pour aller plus loin

• Retour au guide principal : Algorithmes et structures de données : repères 2026 pour devs
• Documentation officielle Python — __slots__
• Documentation officielle Python — collections.deque
• Wikipedia — Linked list (sections sur les variantes doublement chaînée et circulaire)
• Wikipedia — Cycle detection (algorithme de Floyd, algorithme de Brent)
• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (chapitre 10)