Sommaire

Listes chaînées dynamiques

1. Qu’est-ce qu’une liste chaînée ?

a. Une chaîne constituée de maillons

Une liste chaînée est simplement une liste d’objets de même type dans laquelle chaque élément contient :

  • des informations relatives au fonctionnement de l’application. Par exemple des noms et prénoms de personnes avec adresses et numéros de téléphone pour un carnet d’adresses,

  • l’adresse de l’élément suivant ou une marque de fin s’il n’y a pas de suivant. C’est ce lien via l’adresse de l’élément suivant contenue dans l’élément précédent qui fait la "chaîne" et permet de retrouver chaque élément de la liste.

L’adresse de l’objet suivant peut être :

  • une adresse mémoire récupérée avec un pointeur (chaînage dynamique),

  • un indice de tableau récupéré avec un entier,

  • une position dans un fichier. C’est le numéro d’ordre de l’objet dans le fichier multiplié par la taille en octet du type de l’objet. Elle est récupérée avec un entier.

Que la liste chaînée soit bâtie avec des pointeurs ou des entiers, c’est toujours le terme de pointeur qui est utilisé : chaque élément "pointe" sur l’élément suivant, c’est-à-dire ...