Les listes chaînées sont très utiles pour la représentation d’éléments disposant de quantités variables. Leur conception permet de modéliser de nombreuses situations impliquant une gestion ordonnée de l’information. Ainsi, les piles, les files, les arbres sont des candidats idéaux à l’utilisation de listes chaînées. Elles pourront être « simplement chaînées » ou « doublement chaînées » pour permettre un parcours en sens unique ou bien dans les deux sens.
En pratique, une liste chaînée repose sur l’usage des structures du langage C, chaque structure disposant du moyen d’atteindre au minimum son successeur (liste simplement chaînée), au mieux son prédécesseur et son successeur (liste doublement chaînée). Ce chaînage est réalisé au moyen de pointeurs, éléments essentiels à connaître pour une bonne pratique du langage c.
Un pointeur est une variable représentant l’emplacement mémoire d’une autre variable. Au lieu de contenir une valeur directement exploitable, le pointeur référence un autre emplacement qui, lui, va contenir notre information. Grâce à un pointeur nous créons une indirection dans l’accès aux données. C’est une notion extrêmement importante et elle prendra tout son sens dans les lignes qui vont suivre.
Une pile est une structure qui consiste à traiter les éléments dans le sens (dernier entré, premier sorti). Dans la littérature, cela s’appelle LIFO (Last In, First Out). Imaginez-vous simplement une pile d’assiettes. Si vous aviez besoin de prendre une assiette, enlèveriez-vous celle se trouvant tout en bas de la pile ? Non... La première au-dessus de la pile vous conviendrait parfaitement... En informatique, la notion de pile est exactement la même : on empile les éléments d’un côté et les dépile du même, d’où le terme LIFO.
Le haut de la pile est repéré par un pointeur. Chaque nouvelle valeur vient s’intercaler entre le pointeur de haut de pile et le premier véritable élément de la pile. Le schéma ci-contre détaille l’aspect que prend une structure empilée complète.
Les opérations possibles avec une pile sont les suivantes :
Pour l’implémentation informatique de l’algorithme relatif à la gestion d’une pile, une structure à base de tableau pourrait être mise en place, plus simple que les listes chaînées, mais également plus restrictive car il est beaucoup plus compliqué de modifier le nombre d'éléments d'un tableau que d'une liste dynamique.
