La liste chaînée
Motivation et fonction
L'utilisation de tableaux pour enregistrer des données se révèle pénalisante lorsque la quantité de données ne peut être évaluée justement pendant l'élaboration du programme.
L'allocation dynamique est un outil offert pour répondre à ce problème en permettant la réservation de place en cours d'exécution de programme. Toutefois, certains défauts demeurent :
Une variation de la taille nécessaire nécessite un changement d'allocation avec une recopie coûteuse,
Une grande quantité d'information nécessitera une allocation importante qui peut par la suite devenir inutile, si le programme procède à l'élimination d'une grande proportion de données,
L'allocation dynamique par tableau souffre des défauts de cette structure de données, c'est-à-dire que le retrait, ou l'insertion, d'une donnée est réalisé très efficacement en « queue » de tableau (après le dernier élément), mais ce n'est pas le cas, si la position d'insertion se situe ailleurs. Il faut alors décaler une plage d'éléments pour réaliser l'opération. La position de tête du tableau est le cas extrême.
La liste chaînée est une utilisation de l'allocation dynamique pour lever ces défauts, au prix d'une gestion parfois plus lourde.
Attention : Contrainte de l'allocation dynamique
Dans une liste chaînée, chaque donnée est stockée dans une zone mémoire dynamique allouée spécifiquement.
L'allocation de mémoire étant un service rendu par le système d'exploitation, le programme ne le contrôle pas. Il n'y a pas une contiguïté des zones allouées successivement.
Cette dispersion des données nécessite d'enregistrer l'adresse restituée pour toute allocation réalisée.
Définition : Le principe du chaînage
La gestion repose sur une organisation de la donnée manipulée simple : à chaque donnée de la liste est associée l'adresse de la donnée suivante.
L'adresse associée constitue le lien avec la donnée suivante et, par là, à toutes les données qui suivent.
Le terme liste chaînée fait référence à cette association entre allocation dispersée et liaison inter-donnée. Par analogie, l'élément de base de la liste est parfois appelé « maillon ».
L'élément de base de la liste contenant une adresse sur une structure identique : on le qualifie de structure récursive.
En C, le type de l'élément de base d'une liste chaînée d'entiers sera de la forme :
struct ChLint {
int val ;
struct ChLint *lien ;
}
Gestion d'une liste
Outre les règles d'utilisation des pointeurs, la gestion de listes intègre les règles suivantes :
Chaque élément de la liste contient un lien sur l'élément suivant,
À la dernière donnée est associée une adresse spécifique indiquant la fin de liste. C'est l'adresse nulle (0 ou NULL),
L'accès à la liste entière se fera par le 1er élément. En principe, nous utilisons un pointeur pour cet élément,
À chaque manipulation de la liste, il faut veiller à conserver les adresses,
La destruction d'un maillon est faite après extraction de la liste.