Leçon 1 sur 5
Listes chaînées : principe, insertion et suppression
Je sais représenter une suite de données par une liste chaînée, y insérer et y supprimer un élément en ajustant les liens, et comparer son coût à celui d'un tableau.
- 1 h 20
- 5 exercices corrigés
- QCM de 6 questions
À la fin de la leçon, vous saurez :
- Expliquer la différence entre un tableau contigu et une liste chaînée
- Écrire en Python une classe Maillon et une classe ListeChainee
- Insérer en tête, en queue et après un maillon donné
- Supprimer un élément en traitant les cas particuliers (liste vide, tête, absent)
- Comparer la complexité des opérations sur une liste chaînée et sur un tableau
Avant de commencer : Algorithmique (L1) ; Programmation 1 (L1, Python : listes, fonctions, premières classes).
1Je découvre
Dans une pharmacie de Madina, à Conakry, le pharmacien tient le registre des ordonnances en attente sur un grand cahier. Chaque matin, des ordonnances urgentes arrivent et doivent être placées au début du registre. Avec un cahier, il faut tout recopier pour décaler les lignes : c'est long, et une erreur de recopie est vite arrivée.
Son neveu Mamadou, étudiant en L2 de génie informatique à Conakry, lui propose une autre méthode : chaque ordonnance est écrite sur une fiche, et au bas de chaque fiche on note simplement le numéro de la fiche suivante. Pour insérer une ordonnance urgente, il suffit de modifier un ou deux numéros : aucune fiche n'est recopiée. Mamadou vient de réinventer la liste chaînée.
Comment représenter une suite de données par des éléments reliés entre eux, et comment y insérer ou y supprimer un élément sans tout déplacer ?
2Je comprends
1. Tableau contigu et liste chaînée
Un tableau (la list de Python est en réalité un tableau dynamique) range ses éléments dans des cases contiguës de la mémoire. On accède à la case d'indice i en temps constant O(1), par un simple calcul d'adresse. En revanche, insérer ou supprimer au début oblige à décaler tous les éléments suivants : coût O(n).
Une liste chaînée est une suite de maillons (ou nœuds) dispersés en mémoire. Chaque maillon contient :
- une valeur (la donnée) ;
- un lien (une référence) vers le maillon suivant, ou
Nonepour le dernier.
La liste elle-même ne mémorise que la référence vers le premier maillon, appelé la tête.
tete
|
v
[ "Bah" | o-]--> [ "Camara" | o-]--> [ "Diallo" | None ]Pour atteindre le k-ième élément, il faut parcourir les k premiers liens : coût O(k). En contrepartie, une insertion ou une suppression à un endroit déjà atteint ne demande que de modifier quelques liens : coût O(1).
2. Implémentation en Python
On écrit deux classes : Maillon pour un nœud, ListeChainee pour la liste.
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
class ListeChainee:
def __init__(self):
self.tete = None
self.taille = 0
def __len__(self):
return self.taille
def __str__(self):
morceaux = []
courant = self.tete
while courant is not None:
morceaux.append(str(courant.valeur))
courant = courant.suivant
return " -> ".join(morceaux) + " -> None"Le parcours suit toujours le même schéma : une variable courant part de la tête et avance par courant = courant.suivant jusqu'à valoir None. On garde un attribut taille pour obtenir la longueur en O(1) au lieu de la recompter.
3. Insérer un élément
En tête : le nouveau maillon pointe vers l'ancienne tête, puis devient la tête. Coût O(1).
def inserer_tete(self, valeur):
self.tete = Maillon(valeur, self.tete)
self.taille += 1En queue : il faut d'abord trouver le dernier maillon. Coût O(n) (sauf si l'on mémorise aussi une référence queue).
def inserer_queue(self, valeur):
nouveau = Maillon(valeur)
if self.tete is None:
self.tete = nouveau
else:
courant = self.tete
while courant.suivant is not None:
courant = courant.suivant
courant.suivant = nouveau
self.taille += 1Après un maillon donné m : l'ordre des deux affectations est essentiel.
def inserer_apres(self, m, valeur):
m.suivant = Maillon(valeur, m.suivant)
self.taille += 1Exemple
On part de la liste Bah -> Diallo -> None et on veut insérer « Camara » après le maillon m qui contient « Bah ».
Étape 1 - On crée le nouveau maillon : sa valeur est « Camara », son suivant est m.suivant, c'est-à-dire le maillon « Diallo ».
Étape 2 - On raccroche m au nouveau maillon : m.suivant devient le maillon « Camara ».
Résultat : Bah -> Camara -> Diallo -> None. Aucun maillon n'a été déplacé, deux liens seulement ont été écrits.
Si l'on avait fait l'étape 2 avant l'étape 1, on aurait perdu la seule référence vers « Diallo » : la fin de la liste serait perdue.
4. Supprimer un élément
Pour supprimer la première occurrence d'une valeur v, il faut connaître le maillon précédent, car c'est son lien qu'on modifie : precedent.suivant = courant.suivant. Le maillon retiré n'est plus référencé ; le ramasse-miettes de Python libère sa mémoire.
def supprimer(self, v):
"""Supprime la première occurrence de v. Renvoie True si trouvée."""
precedent = None
courant = self.tete
while courant is not None and courant.valeur != v:
precedent = courant
courant = courant.suivant
if courant is None: # liste vide ou v absente
return False
if precedent is None: # v est en tête
self.tete = courant.suivant
else:
precedent.suivant = courant.suivant
self.taille -= 1
return TrueMéthode
Pour écrire sans erreur une opération sur une liste chaînée :
- Dessinez la liste avec des boîtes et des flèches, avant et après l'opération.
- Repérez les liens à modifier et l'ordre dans lequel les écrire (ne jamais perdre une référence).
- Traitez à part les cas limites : liste vide, opération sur la tête, élément absent, dernier maillon.
- Mettez à jour les attributs annexes (taille, queue).
- Testez chaque cas limite avec assert.
5. Variantes et comparaison des coûts
- Liste doublement chaînée : chaque maillon a aussi un lien
precedent. On peut supprimer un maillon connu en O(1) et parcourir dans les deux sens, au prix d'un lien de plus par maillon. - Liste avec référence de queue : l'insertion en queue devient O(1).
| Opération | Tableau (list Python) | Liste simplement chaînée |
|---|---|---|
| Accès au k-ième élément | O(1) | O(k) |
| Insertion en tête | O(n) | O(1) |
| Insertion en queue | O(1) amorti | O(n), ou O(1) avec queue |
| Insertion après un maillon connu | O(n) | O(1) |
| Recherche d'une valeur | O(n) | O(n) |
| Mémoire par élément | la valeur | la valeur et un lien |
On choisit donc une liste chaînée quand les insertions et suppressions en tête ou au milieu dominent, et un tableau quand on a besoin d'accès par indice.
3Je retiens
Je retiens
Une liste chaînée est une suite de maillons ; chaque maillon contient une valeur et un lien vers le suivant.
La liste ne mémorise que la tête ; le dernier maillon pointe vers None.
Parcours : courant part de la tête et avance par courant = courant.suivant.
Insérer en tête coûte O(1) ; accéder au k-ième élément coûte O(k).
Pour insérer après m : créer le maillon qui pointe vers m.suivant, puis raccrocher m.
Pour supprimer, il faut le maillon précédent ; la tête se traite à part.
Toujours tester : liste vide, tête, dernier maillon, élément absent.
4Erreurs fréquentes
- Écrire m.suivant = nouveau avant de raccrocher nouveau à l'ancien suivant : la fin de la liste est perdue.
- Oublier le cas de la liste vide : courant.suivant provoque AttributeError sur None.
- Supprimer la tête avec precedent.suivant alors que precedent vaut None.
- Avancer la tête elle-même pendant un parcours (self.tete = self.tete.suivant) : on détruit la liste.
- Oublier de mettre à jour la taille après une insertion ou une suppression.
5Je m’exerce
1Exercice 1
(Questions de cours) a) Que contient un maillon ? b) Pourquoi l'accès au k-ième élément d'une liste chaînée n'est-il pas en O(1) ? c) Citez une situation où une liste chaînée est préférable à un tableau.
Voir le corrigéCacher le corrigé
a) Une valeur et une référence vers le maillon suivant (ou None). b) Les maillons ne sont pas contigus en mémoire : on ne peut pas calculer l'adresse du k-ième, il faut suivre k liens depuis la tête. c) Quand on insère ou supprime souvent en tête ou au milieu, par exemple un registre où arrivent des ordonnances urgentes à placer en premier.
2Exercice 2
On exécute :
l = ListeChainee()
l.inserer_tete(3)
l.inserer_tete(7)
l.inserer_queue(5)
l.inserer_apres(l.tete, 9)
l.supprimer(3)
print(l, len(l))Dessinez la liste après chaque instruction et donnez l'affichage.
Voir le corrigéCacher le corrigé
Après inserer_tete(3) : 3 -> None. Après inserer_tete(7) : 7 -> 3 -> None. Après inserer_queue(5) : 7 -> 3 -> 5 -> None. Après inserer_apres(l.tete, 9) (après le maillon 7) : 7 -> 9 -> 3 -> 5 -> None. Après supprimer(3) : 7 -> 9 -> 5 -> None. Affichage :
7 -> 9 -> 5 -> None 33Exercice 3
Ajoutez une méthode inserer_position(k, v) qui insère v pour qu'il occupe la position k (0 = tête). Si k est négatif ou supérieur à la taille, la méthode lève IndexError.
Voir le corrigéCacher le corrigé
def inserer_position(self, k, v):
if k < 0 or k > self.taille:
raise IndexError("position invalide")
if k == 0:
self.inserer_tete(v)
return
precedent = self.tete
for _ in range(k - 1):
precedent = precedent.suivant
self.inserer_apres(precedent, v)On avance de k-1 liens pour atteindre le maillon qui précède la position k, puis on réutilise inserer_apres, qui met à jour la taille. Pour k == self.taille, on insère après le dernier maillon, c'est-à-dire en queue. Coût O(k).
4Exercice 4
Écrivez une méthode inverser() qui inverse la liste en place, en O(n), sans créer de nouveau maillon.
Voir le corrigéCacher le corrigé
def inverser(self):
precedent = None
courant = self.tete
while courant is not None:
suivant = courant.suivant # on sauvegarde la suite
courant.suivant = precedent # on retourne le lien
precedent = courant
courant = suivant
self.tete = precedentTest : sur 1 -> 2 -> 3 -> None, on obtient 3 -> 2 -> 1 -> None. Chaque maillon est visité une fois : O(n), et seules trois variables sont utilisées : mémoire O(1).
5Exercice 5
(Type examen) Un cybercafé de Kankan gère la file des clients en attente d'un poste. a) Expliquez pourquoi une liste chaînée avec une référence queue permet d'ajouter un client à la fin et de servir le premier en O(1). b) Écrivez la classe ListeAvecQueue avec les méthodes ajouter_fin(v) et retirer_tete() (qui renvoie la valeur retirée, ou lève IndexError si la liste est vide). c) Quel cas particulier faut-il traiter pour l'attribut queue quand on retire le dernier client ?
Voir le corrigéCacher le corrigé
a) Retirer le premier client, c'est supprimer la tête : O(1). Ajouter à la fin coûte O(n) s'il faut chercher le dernier maillon, mais O(1) si l'on garde une référence directe queue vers lui.
b)
class ListeAvecQueue:
def __init__(self):
self.tete = None
self.queue = None
def ajouter_fin(self, v):
nouveau = Maillon(v)
if self.queue is None: # liste vide
self.tete = nouveau
else:
self.queue.suivant = nouveau
self.queue = nouveau
def retirer_tete(self):
if self.tete is None:
raise IndexError("aucun client en attente")
v = self.tete.valeur
self.tete = self.tete.suivant
if self.tete is None: # on vient de retirer le dernier
self.queue = None
return v
f = ListeAvecQueue()
f.ajouter_fin("Kadiatou")
f.ajouter_fin("Sékou")
assert f.retirer_tete() == "Kadiatou"
assert f.retirer_tete() == "Sékou"
assert f.queue is Nonec) Quand on retire le dernier client, la tête devient None ; il faut aussi remettre queue à None, sinon queue pointerait encore vers un maillon retiré et le prochain ajouter_fin l'accrocherait à ce maillon fantôme au lieu de mettre à jour la tête.
Cherchez d’abord seul, sur votre cahier, puis ouvrez le corrigé pour comparer.
6Je vérifie
Choisissez une réponse pour chaque question : la correction s’affiche aussitôt.
Karamö, votre enseignant
Il a lu cette leçon. Posez-lui votre question : il vous répond ici.
Connectez-vous pour poser vos questions à Karamö.
Avec un compte Kharandi gratuit, vous cochez les leçons terminées et vous suivez votre progression, cours par cours.
Signaler une erreur dans cette leçon
Toutes les leçons de Algorithmique avancée et structures de données