0 XP
?
Structures de données/Listes chaînées
Intermédiaire60 min40 XP

Objectifs de cette leçon

  • Comprendre la structure d'une liste chaînée
  • Implémenter l'ajout et la suppression de nœuds
  • Comparer listes chaînées et tableaux

Listes chaînées 🔗

Imagine une chasse au trésor : chaque indice te donne un morceau de la carte ET te dit où trouver le prochain indice. C'est exactement comme ça que marche une liste chaînée !

1. Pourquoi pas un tableau ? 🤔

Les tableaux (listes classiques) ont des défauts :

  • 🔴 Taille fixe (dans beaucoup de langages, on doit décider la taille à l'avance)
  • 🔴 Insérer au milieu = décaler tous les éléments → O(n)
  • 🔴 Supprimer au milieu = re-décaler → O(n)

Exemple : Dans un tableau de 1000 éléments, insérer au début force les 1000 éléments à se décaler de 1 case. C'est lent !

Une liste chaînée résout ces problèmes : chaque élément connaît son voisin, on peut insérer/supprimer sans tout décaler.

2. La structure : des nœuds et des pointeurs 🧱

Une liste chaînée est composée de nœuds reliés entre eux. Chaque nœud contient :

  1. Une valeur (la donnée)
  2. Un pointeur vers le prochain nœud (ou None si c'est le dernier)
Exécution pas à pas
pseudo
1/5
▶️
STRUCTURE Noeud
⚙️STRUCTURE NoeudLe programme exécute cette action, puis passe à la suivante.
Le programme exécute cette instruction, puis passe à la suivante.
class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur  # La donnée
        self.suivant = None   # Le pointeur vers le suivant (None = dernier)

💡 Visualisation : head → [10 | •] → [20 | •] → [30 | None]

  • head pointe vers le premier nœud (10)
  • Chaque nœud pointe vers le suivant
  • Le dernier pointe vers None (fin de la liste)

3. Opération : ajouter au début 🔝

C'est l'opération la plus rapide : on crée un nœud, on le branche devant, et on déplace la tête.

Exécution pas à pas
pseudo
1/6
🧩
FONCTION ajouter_debut(liste, valeur)
⚙️FONCTION ajouter_debut(liste, valeur)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "ajouter_debut(liste, valeur)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.
def ajouter_debut(self, valeur):
    noeud = Noeud(valeur)
    noeud.suivant = self.tete   # Le nouveau pointe vers l'ancien premier
    self.tete = noeud            # La tête devient le nouveau

Pas à pas : Liste = [10 → 20], on ajoute 5 au début :

  1. On crée un nœud (5)
  2. 5.suivant → 10
  3. tête → 5 → Résultat : [5 → 10 → 20] ✅

4. Opération : ajouter à la fin 🔚

On doit parcourir toute la liste pour trouver le dernier nœud, puis lui ajouter un suivant.

Exécution pas à pas
pseudo
1/12
🧩
FONCTION ajouter_fin(liste, valeur)
⚙️FONCTION ajouter_fin(liste, valeur)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "ajouter_fin(liste, valeur)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.
def ajouter_fin(self, valeur):
    if not self.tete:
        self.tete = Noeud(valeur)
        return
    courant = self.tete
    while courant.suivant:   # On avance jusqu'au dernier nœud
        courant = courant.suivant
    courant.suivant = Noeud(valeur)  # On accroche le nouveau à la fin

Pas à pas : Liste = [10 → 20], on ajoute 30 à la fin :

  1. courant = tête[10]
  2. 10.suivant existe → courant = [20]
  3. 20.suivant = None → on s'arrête
  4. 20.suivant → [30] → Résultat : [10 → 20 → 30] ✅

5. Opération : supprimer une valeur 🗑️

On cherche la valeur à supprimer, et on "saute" par-dessus le nœud.

Exécution pas à pas
pseudo
1/16
🧩
FONCTION supprimer(liste, valeur)
⚙️FONCTION supprimer(liste, valeur)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "supprimer(liste, valeur)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.
def supprimer(self, valeur):
    if not self.tete:
        return
    if self.tete.valeur == valeur:     # Si c'est le premier élément
        self.tete = self.tete.suivant  # On déplace la tête
        return
    courant = self.tete
    while courant.suivant:
        if courant.suivant.valeur == valeur:
            courant.suivant = courant.suivant.suivant  # On saute le nœud !
            return
        courant = courant.suivant

Visuellement : head → [10 | •] → [20 | •] → [30 | None] Si on supprime 20 : head → [10 | •] ─────────→ [30 | None] Le nœud 20 n'est plus dans la chaîne !

6. Utilisation complète 🎮

ma_liste = ListeChainee()
ma_liste.ajouter_fin(10)     # [10]
ma_liste.ajouter_fin(20)     # [10 → 20]
ma_liste.ajouter_debut(5)    # [5 → 10 → 20]
ma_liste.afficher()          # 5 → 10 → 20 → None
ma_liste.supprimer(10)       # [5 → 20]
ma_liste.afficher()          # 5 → 20 → None

7. Tableau vs Liste chaînée : que choisir ? ⚖️

OpérationTableauListe chaînée
Accès direct (tab[5])⚡ O(1)🐢 O(n) — faut parcourir
Ajout au début🐢 O(n) — tout décaler⚡ O(1)
Ajout à la fin⚡ O(1)🐢 O(n) — faut trouver la fin
Suppression🐢 O(n)🐢 O(n)
MémoireContinue (prévisible)Éparpillée (flexible)

💡 Quand utiliser une liste chaînée ?

  • Tu insères/supprimes souvent au début
  • Tu n'as pas besoin d'accès direct par index
  • Tu ne connais pas la taille à l'avance

Exercices pour toi 🎯

1. Détection de cycle (algorithme de Floyd) 🏃

Une liste chaînée peut avoir un cycle (le dernier nœud pointe vers un ancien, créant une boucle). Comment le détecter ?

L'astuce : deux tortues, une rapide et une lente. Si la rapide rattrape la lente → il y a un cycle.

Exécution pas à pas
pseudo
1/13
🧩
FONCTION a_cycle(tete)
⚙️FONCTION a_cycle(tete)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "a_cycle(tete)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.
def a_cycle(tete):
    lent = rapide = tete
    while rapide and rapide.suivant:
        lent = lent.suivant
        rapide = rapide.suivant.suivant
        if lent == rapide:
            return True
    return False

2. Inverser une liste chaînée 🔄

Exécution pas à pas
pseudo
1/12
🧩
FONCTION inverser(tete)
⚙️FONCTION inverser(tete)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "inverser(tete)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.
def inverser(tete):
    precedent = None
    courant = tete
    while courant:
        suivant = courant.suivant
        courant.suivant = precedent  # On inverse le sens du pointeur
        precedent = courant
        courant = suivant
    return precedent  # La nouvelle tête de la liste inversée

Teste dans la Sandbox :

ma_liste = ListeChainee()
ma_liste.ajouter_fin(1)
ma_liste.ajouter_fin(2)
ma_liste.ajouter_fin(3)
ma_liste.afficher()  # 1 → 2 → 3 → None
# Après inversion : 3 → 2 → 1 → None

⚡ Simulateur — Listes chaînées

Étape 1/20
📝 Pseudo-code
1# Liste chaînée : nœuds et pointeurs
2class Noeud:
3 def __init__(self, valeur):
4 self.valeur = valeur
5 self.suivant = None
6
7# Ajouter au début O(1)
8def ajouter_debut(tete, valeur):
9 noeud = Noeud(valeur)
10 noeud.suivant = tete
11 return noeud
12
13# Ajouter à la fin O(n)
14def ajouter_fin(tete, valeur):
15 if not tete: return Noeud(valeur)
16 courant = tete
17 while courant.suivant:
18 courant = courant.suivant
19 courant.suivant = Noeud(valeur)
20 return tete
21
22# Supprimer une valeur
23def supprimer(tete, valeur):
24 if not tete: return None
25 if tete.valeur == valeur: return tete.suivant
26 courant = tete
27 while courant.suivant:
28 if courant.suivant.valeur == valeur:
29 courant.suivant = courant.suivant.suivant
30 return tete
31 courant = courant.suivant
32 return tete
🔗 Visualisation de la liste0 nœud
Liste vide (null)

On commence avec une liste vide (head → null).