Deux façons de ranger des éléments en ligne : une rangée de cases, ou une chaîne de maillons.
⏱️ Durée : environ 75 minutes · 🎓 Niveau : débutant · 🏅 Badge : Maillon fort
🎬 L'histoire
Kodi doit gérer la liste d'attente d'une formation : on y ajoute des membres en fin de liste, parfois au milieu pour les prioritaires, et on retire ceux qui abandonnent.
Il utilise une liste Python. Tout marche, jusqu'à 200 000 inscrits : insérer au début devient très lent.
« Il faut savoir ce qu'il y a derrière cette liste », dit Sam.
Tu découvres les deux grandes familles de structures linéaires.
🎯 Ta mission
À la fin, je serai capable de :
- expliquer comment un tableau stocke ses éléments
- expliquer le principe d'une liste chaînée
- comparer accès, insertion et suppression des deux
- implémenter une liste chaînée simple
- choisir l'une ou l'autre selon l'usage
🧩 Défi d'échauffement (5 XP)
Imagine deux façons d'organiser 10 personnes :
- A : elles sont assises sur un banc numéroté de 0 à 9 ;
- B : elles forment une chaîne, chacune tient la main de la suivante, et tu ne connais que la première.
Pour trouver la personne n°7, laquelle des deux est la plus rapide ? Et pour insérer quelqu'un au milieu ?
💡 Le concept
Le tableau
Un tableau range ses éléments dans des cases contiguës en mémoire, numérotées à partir de 0.
indice : 0 1 2 3 4
valeur : [ 12 ][ 7 ][ 25 ][ 3 ][ 18 ]
- Accès par indice : immédiat. L'ordinateur calcule l'adresse directement.
- Insertion/suppression au milieu : il faut décaler tous les éléments suivants.
- Ajout à la fin : rapide en général.
La list de Python est un tableau dynamique (elle s'agrandit quand il le faut).
La liste chaînée
Une liste chaînée est une suite de maillons. Chaque maillon contient une valeur et une référence vers le suivant.
tête → [12 | •]→ [7 | •]→ [25 | •]→ [3 | None]
- Accès au n-ième : il faut suivre les maillons un par un.
- Insertion/suppression (si on est déjà au bon endroit) : on modifie juste des références, sans décaler.
- Mémoire : chaque maillon coûte un peu plus (valeur + référence).
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
class ListeChainee:
def __init__(self):
self.tete = None
def ajouter_debut(self, valeur):
self.tete = Maillon(valeur, self.tete)
def vers_liste(self):
resultat, courant = [], self.tete
while courant is not None:
resultat.append(courant.valeur)
courant = courant.suivant
return resultat
Comparaison
| Opération | Tableau | Liste chaînée |
|---|---|---|
| Lire le n-ième | rapide | lent (il faut parcourir) |
| Ajouter au début | lent (décalage) | rapide |
| Ajouter à la fin | rapide | rapide si on garde la fin, sinon lent |
| Insérer au milieu | lent (décalage) | rapide une fois la position atteinte |
| Mémoire | compacte | plus gourmande |
🧠 Astuce : en pratique, un tableau est le bon choix par défaut. La liste chaînée est utile pour ses insertions/suppressions locales rapides.
🔍 Exemple pas à pas
Problème : insérer un membre prioritaire en 2e position dans ["Ada", "Bob", "Cléo"].
Avec un tableau (liste Python) : liste.insert(1, "Prio"). Les éléments suivants sont décalés d'une case.
Avec une liste chaînée : on se place sur le maillon de "Ada", puis :
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
def inserer_apres(maillon, valeur):
maillon.suivant = Maillon(valeur, maillon.suivant)
def vers_liste(tete):
r, c = [], tete
while c is not None:
r.append(c.valeur)
c = c.suivant
return r
tete = Maillon("Ada", Maillon("Bob", Maillon("Cléo")))
inserer_apres(tete, "Prio")
print(vers_liste(tete)) # ['Ada', 'Prio', 'Bob', 'Cléo']
Étapes : (1) créer le nouveau maillon qui pointe vers "Bob", (2) faire pointer "Ada" vers le nouveau maillon. Aucun décalage. L'ordre des deux étapes compte : si on change d'abord "Ada", on perd "Bob".
✍️ À toi, avec aide (10 XP)
Complète la méthode ajouter_fin d'une liste chaînée (avec tete). Si la liste est vide, le nouveau maillon devient la tête. Sinon, on parcourt jusqu'au dernier maillon (celui dont suivant est None).
Teste : ajouter 1, 2, 3 donne [1, 2, 3].
💡 Indice 1
Cas particulier : self.tete is None.
💡 Indice 2
Parcours avec courant = self.tete tant que courant.suivant is not None.
💡 Indice 3
À la sortie de la boucle, courant est le dernier maillon : courant.suivant = Maillon(valeur).
✅ Réponse
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
class ListeChainee:
def __init__(self):
self.tete = None
def ajouter_fin(self, valeur):
nouveau = Maillon(valeur)
if self.tete is None:
self.tete = nouveau
return
courant = self.tete
while courant.suivant is not None:
courant = courant.suivant
courant.suivant = nouveau
def vers_liste(self):
r, c = [], self.tete
while c is not None:
r.append(c.valeur)
c = c.suivant
return r
l = ListeChainee()
for x in (1, 2, 3):
l.ajouter_fin(x)
(l.vers_liste())
🚀 À toi, en solo (20 XP)
Ajoute à ListeChainee :
supprimer(valeur): retire le premier maillon contenant la valeur (ne fait rien si absente) ;longueur();inverser(): retourne la liste sur place, en changeant les références.
Teste sur des listes vides, à un élément et à plusieurs éléments. Cas piège : supprimer la tête.
✅ Pistes de correction
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
class ListeChainee:
def __init__(self):
self.tete = None
def ajouter_debut(self, v):
self.tete = Maillon(v, self.tete)
def vers_liste(self):
r, c = [], self.tete
while c is not None:
r.append(c.valeur)
c = c.suivant
return r
def supprimer(self, valeur):
if self.tete is None:
return
if self.tete.valeur == valeur:
self.tete = self.tete.suivant
return
c = self.tete
c.suivant c.suivant.valeur != valeur:
c = c.suivant
c.suivant :
c.suivant = c.suivant.suivant
():
n, c = , .tete
c :
n +=
c = c.suivant
n
():
precedent, courant = , .tete
courant :
suivant = courant.suivant
courant.suivant = precedent
precedent, courant = courant, suivant
.tete = precedent
l = ListeChainee()
x (, , ):
l.ajouter_debut(x)
l.supprimer()
l.inverser()
(l.vers_liste(), l.longueur())
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Perdre le reste de la chaîne | On écrase une référence avant de la sauvegarder | Sauvegarder suivant avant de modifier |
| Oublier la tête vide | AttributeError sur None | Traiter le cas liste vide en premier |
| Utiliser une liste chaînée pour lire par indice | Chaque lecture parcourt la chaîne | Choisir un tableau si on lit par position |
| Confondre indice et valeur | Mauvais élément modifié | Nommer clairement i et valeur |
🐉 Mini-boss (40 XP)
Compare concrètement tableau et liste chaînée.
- Implémente
ListeChaineeavecajouter_debut,ajouter_fin,lire(i),supprimer_debut. - Mesure avec
time.perf_counter(): (a) 20 000 insertions au début, (b) 20 000 lectures de la position 10 000, pour unelistPython et pour ta liste chaînée. - Remplis un tableau des temps.
- Conclus : pour quel usage chaque structure gagne-t-elle ?
✅ Pistes de correction
Les insertions au début : list.insert(0, x) est lente (décalage de tout), la liste chaînée est rapide. Les lectures par indice : la list est immédiate, la liste chaînée est lente (parcours). Conclusion attendue : tableau pour lire par position et parcourir ; liste chaînée pour insertions/suppressions fréquentes en tête.
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. Dans un tableau, lire l'élément d'indice 5 est :
- A. proportionnel à la taille
- B. impossible
- C. immédiat
2. Dans une liste chaînée, atteindre le 5e élément :
- A. demande de suivre les maillons
- B. est immédiat
- C. est impossible
3. Insérer au début d'un grand tableau est :
- A. gratuit
- B. coûteux (décalage)
- C. impossible
4. 🔁 Révision mission 01 : Un ADT décrit :
- A. son code interne
- B. sa couleur
- C. ses opérations
5. 🔁 Révision HEF-010, mission 03 : Une précondition :
- A. ce que l'appelant doit fournir
- B. la valeur de retour
- C. un test
✅ Réponses
- C.
- A.
- B.
- C.
- A.
🪞 Je réfléchis (10 XP)
- Dans quelles situations de ta vie préfères-tu un accès direct, et dans lesquelles une chaîne ?
- Quel est le piège le plus facile à oublier dans les listes chaînées ?
🎒 À retenir
- Tableau : cases contiguës, accès direct, décalage à l'insertion.
- Liste chaînée : maillons reliés, insertion locale rapide, accès lent.
- Les cas particuliers : liste vide, tête, fin.
- Le tableau est le choix par défaut.
- On choisit selon les opérations les plus fréquentes.
flowchart LR
T(["Tableaux et listes chaînées"])
T --> R1["1. Tableau : cases contiguës, accès direct, décalage à l'insertion."]
T --> R2["2. Liste chaînée : maillons reliés, insertion locale rapide, accès lent."]
T --> R3["3. Les cas particuliers : liste vide, tête, fin."]
T --> R4["4. Le tableau est le choix par défaut."]
T --> R5["5. On choisit selon les opérations les plus fréquentes."]
Description du schéma : la mission au centre, reliée aux cinq idées à retenir.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Maillon fort
← Mission 01 — Ranger l'information : le modèle abstrait · Mission 03 — Piles et files →
HEF-020 — Structures de données

