Les Listes Chaînées

Plutôt qu'utiliser une structure proche des tableaux pour implémenter une liste, on préfère utiliser une liste chaînée. Cette implémentation permet de conserver une insertion (et une suppression) d'éléments en temps (quasi-)constant.

Définition

Une liste chaînée est une implémentation en machine du T.A.D. « liste ».
Contrairement au tableau, les éléments d'une liste chaînée ne sont pas contigus en mémoire. Chaque élément (généralement nommé « maillon » ou « cellule ») contient plusieurs informations :

• la « valeur » contenue ;
• un lien vers l'élément suivant de la liste.

Le lien qui pointe vers le premier élément est stocké à part.

Il existe plusieurs sortes de listes chaînées. En particulier :

• la liste simplement chaînée ;
• la liste simplement chaînée circulaire ;
• la liste doublement chaînée ;
• la liste doublement chaînée circulaire.

Cette année, nous étudierons les listes simplement chaînées (non circulaires).

Remarque

Un approfondissement sur les listes doublement chaînées (non circulaires) pourra être envisagé selon l'état d'avancement du programme.

Une liste simplement chaînée ressemble donc à :