Manipulation des listes chaînées : ajout et suppression d'éléments

1. Préparer le terrain : terminologie et opérations de base

Avant de modifier une liste, assurons-nous d'utiliser un vocabulaire commun. Comme dans la leçon précédente, un élément de la liste est un nœud (ou Cellule). Il contient :

• une donnée (valeur ou info)
• un pointeur vers le nœud suivant (suivant)

La liste elle-même est identifiée par un pointeur vers sa tête (le premier nœud). Le pointeur suivant du dernier nœud pointe vers une valeur spéciale, Nil, pour marquer la fin.

Pour ajouter un nœud, il faut le créer. Pour le supprimer, il faut libérer la mémoire qu'il occupe. En algorithmique, nous utilisons des commandes abstraites pour cela :

• nouvelle Cellule : Réserve un espace en mémoire pour un nouveau nœud et nous donne une référence (un pointeur) vers cet espace.
• libérer(cel) : Rend à nouveau disponible l'espace mémoire occupé par le nœud cel.

Ces concepts sont la base pour manipuler dynamiquement la structure de la liste.

2. L'opération d'ajout (Insertion)

L'ajout d'un élément est l'opération phare des listes chaînées. Selon l'endroit où l'on veut insérer, la procédure varie légèrement. Nous allons étudier trois cas : l'ajout en début, après un élément donné, et en fin de liste.

Le document suivant sera notre guide principal pour les algorithmes d'aujourd'hui.

Analysons maintenant chaque cas en détail.

a. Ajout en tête de liste (ajouter_debut)

C'est le cas le plus simple et le plus rapide. Pour ajouter un nouvel élément au début :

1. On crée un nouveau nœud.
2. On fait pointer le champ suivant de ce nouveau nœud vers l'actuelle tête de la liste.
3. On met à jour la tête de la liste pour qu'elle pointe vers notre nouveau nœud.

Attention : L'ordre est primordial. Si l'on faisait l'étape 3 avant la 2, on perdrait la référence à l'ancienne tête et donc... tout le reste de la liste !

Pseudo-code (ajouter_debut(S, x) où S est la liste et x la valeur à ajouter) :

1. cel ← nouvelle Cellule
2. cel.valeur ← x
3. cel.suivant ← S.tête
4. S.tête ← cel

b. Ajout après un élément existant (ajouter_après)

C'est l'opération qui illustre le mieux la flexibilité des listes chaînées. Pour insérer un élément après un nœud connu, que nous appellerons pred (prédécesseur) :

1. On crée un nouveau nœud.
2. On fait pointer le champ suivant du nouveau nœud vers le nœud qui suit pred (pred.suivant).
3. On met à jour le champ suivant de pred pour qu'il pointe vers le nouveau nœud.

Pseudo-code (ajouter_après(S, x, pred) où pred est le nœud après lequel on insère) :

1. cel ← nouvelle Cellule
2. cel.valeur ← x
3. cel.suivant ← pred.suivant
4. pred.suivant ← cel

c. Ajout en fin de liste (ajouter_fin)

Pour ajouter un élément à la fin, il faut d'abord trouver le dernier nœud.

1. On parcourt la liste depuis la tête jusqu'à trouver le nœud dont le suivant est Nil. C'est la queue de la liste.
2. Une fois ce nœud trouvé, on effectue une opération ajouter_après lui.
3. Un cas particulier doit être géré : si la liste est vide (S.tête est Nil), l'ajout en fin de liste est en fait un ajout en début de liste.

L'algorithme ajouter_fin que vous avez lu dans le document LINK est très élégant car il réutilise les fonctions que nous venons de voir, ce qui est une excellente pratique pour un "code clean" :

• Si la liste est vide, il appelle ajouter_debut.
• Sinon, il parcourt la liste pour trouver la queue, puis appelle ajouter_après.

3. L'opération de suppression (Retrait)

Supprimer un nœud implique de "recâbler" les pointeurs pour l'exclure de la chaîne, puis de libérer sa mémoire.

Le principal défi de la suppression dans une liste simplement chaînée est qu'un nœud ne connaît que son successeur, pas son prédécesseur. Or, pour supprimer un nœud, il faut modifier le pointeur suivant de son prédécesseur.

Voyons comment cela fonctionne.

a. La clé : trouver le nœud ET son prédécesseur

La solution élégante est de créer une fonction de recherche qui, tout en parcourant la liste, garde une trace du nœud précédent.
La fonction recherche(S, x) du document retourne deux valeurs :

• cel : le nœud contenant la valeur x (ou Nil si non trouvé).
• pred : le nœud qui précède cel (ou Nil si cel est la tête).

b. L'algorithme de suppression (supprimer)

Armé de cette fonction de recherche, l'algorithme de suppression devient beaucoup plus clair :

1. On appelle recherche(S, x) pour trouver le nœud à supprimer (cel) et son prédécesseur (pred).
2. Si l'élément n'est pas trouvé (cel est Nil), on ne fait rien (ou on signale une erreur).
3. Sinon, on gère deux cas :
   • Cas 1 : Suppression de la tête (pred est Nil). Il suffit de faire pointer la tête de la liste vers l'élément suivant (S.tête ← cel.suivant).
   • Cas 2 : Suppression au milieu ou en fin (pred n'est pas Nil). On "saute" par-dessus cel en faisant pointer le suivant du prédécesseur vers le suivant de cel (pred.suivant ← cel.suivant).
4. Finalement, on libère la mémoire du nœud supprimé : libérer(cel).

Le document suivant propose une autre vision des algorithmes de suppression, qui peut vous aider à consolider votre compréhension en présentant les cas légèrement différemment.

Conclusion

Aujourd'hui, nous sommes allés au cœur de la mécanique des listes chaînées. Votre objectif est de pouvoir décrire ces opérations, ce qui signifie être capable d'expliquer la logique des manipulations de pointeurs pour chaque cas.

Points clés à retenir :

• Ajouter en tête est l'opération la plus rapide : on crée un nœud, on le fait pointer vers l'ancienne tête, et on met à jour la tête.
• Ajouter au milieu se fait en "recâblant" les pointeurs du nœud précédent et du nouveau nœud pour l'insérer dans la chaîne.
• Ajouter en fin nécessite de parcourir toute la liste pour trouver le dernier élément avant de l'ajouter.
• Supprimer un nœud requiert une référence à son prédécesseur pour pouvoir "court-circuiter" le nœud à retirer de la chaîne.
• La gestion des cas particuliers est essentielle : liste vide, suppression en tête, etc. C'est un aspect fondamental de l'écriture d'algorithmes robustes.

Et après ?

Maintenant que vous savez comment fonctionnent les opérations fondamentales sur les tableaux et les listes chaînées, la prochaine étape logique est de savoir quand les utiliser. Dans la prochaine leçon, nous nous concentrerons sur la prise de décision : face à un problème donné, comment choisir la structure de données la plus appropriée entre un tableau et une liste chaînée en analysant les contraintes et les opérations requises.