Liste chaînée - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d'éléments de même type.
L'accès aux éléments d'une liste se fait de manière séquentielle : chaque élément permet l'accès au suivant (contrairement au cas du tableau dans lequel l'accès se fait de manière absolue, par adressage direct de chaque cellule dudit tableau).
Principe
Le principe de la liste chaînée est que chaque élément possède, en plus de la donnée, des pointeurs vers les éléments qui lui sont logiquement adjacents dans la liste. De ce fait, l'usage d'une liste est préconisé pour des raisons de rapidité de traitement, lorsque les insertions et suppressions d'élément en tout point sont relativement plus fréquentes que les accès simples.
En effet, une insertion ou une suppression se font en temps constant car elles ne demandent au maximum que deux accès en écriture. En revanche, l'accès à un élément aléatoirement positionné nécessite le parcours de chaque élément qui sépare l'index de l'élément choisi. Il est donc préférable d'accéder aux éléments séquentiellement.
Types de listes chaînées
Il existe plusieurs types de listes chaînées, caractérisés principalement par deux attributs :
- le chaînage,
- le cycle.
Chaînage
Liste simplement chaînée
Comme on le voit sur le schéma ci-contre, deux informations composent chaque élément de la liste chaînée :
- la valeur associée à l'élément (ou donnée d'exploitation),
- un pointeur vers l'élément suivant (ou successeur).
Comme un seul élément de la liste est pointé, l'accès se fait uniquement dans un sens.
Liste doublement chaînée
La différence avec une liste simplement chaînée est que, cette fois-ci, un pointeur vers l'élément précédent (ou prédécesseur) est ajouté. Ainsi l'accès peut se faire indifféremment dans les deux sens : de successeur en successeur, ou de prédécesseur en prédécesseur.
Cette structure est plus coûteuse en mémoire (d'un pointeur par élément de la liste) et en nombre d'instructions pour la mise à jour : une insertion coûte quatre copies de pointeurs contre deux dans le cas d'une liste simplement chaînée.
Par contre, cela permet d'opérer une insertion avant ou après un élément, sans devoir disposer d'un pointeur sur un voisin, là ou une liste simplement chaînée n'autorise une insertion qu'à une seule position par rapport à un élément : en successeur ou (exclusivement) en prédécesseur.
Il est également possible de contrôler l'intégrité d'une liste doublement chaînée en vérifiant le chaînage double.
Cycle
Le cycle est la propriété que présente une liste chaînée de former une boucle (ou chaîne fermée). La notion de début de chaîne ou de fin de chaîne disparaît.
Une liste cyclique (ou circulaire) est créée lorsque le dernier élément possède une référence vers le premier élément (si la liste est doublement chaînée, alors le premier élément possède aussi une référence vers le dernier).
L'utilisation de ce type de liste requiert des précautions pour éviter des parcours indéfinis, par exemple lors d'une recherche vaine d'élément.
