Cet article est destiné aux listes chainées (linked list en anglais). Une liste chaînée est une suite de maillons contenant les données à sauvegarder ainsi qu’une ou deux références (liens) vers le maillon suivant et/ou précédent. Voici un exemple (image provenant du site Wikipédia) :
Sur l’image ci-dessus les données sont les nombres 19, 99 et 37. Chaque nombre est couplé avec la référence sur le nombre suivant. Le couple (nombre, référence) constitue un maillon et l’ensemble des maillons forment une chaîne.
Le comportement en mémoire des listes est différents des tableaux. Contrairement à ces derniers, la liste n’occupe pas une suite consécutives de cases mémoires. C’est pourquoi les éléments de la liste ne sont pas accessible par des indexes. L’accès aux éléments se font par parcours séquentiel, c’est à dire qu’il faut parcourir toute la liste jusqu’à trouver l’élément voulu.
Pour insérer un objet dans la liste, il suffit de modifier le “chainage” des maillons.
Il est également possible de créer des listes doublement chainées. Pour cela, la donnée du maillon est couplée avec deux références : une vers le maillon suivant et l’autre vers le maillon précédents, comme le montre l’image suivante (image provenant du site Wikipédia) :
Enfin, il est possible de rendre la liste cyclique en faisant pointer la référence du dernier maillon vers le premier maillon afin de former une liste bouclée.
