Parmi les champs d'une structure peut figurer un pointeur.

Dans une liste chaînée (concurrente du tableau de structures), une variable de type structuré contient, outre des informations diverses, l'adresse d'une autre variable du même type structuré sous la forme d'un pointeur. Le passage d'un élément à l'autre de la liste s'effectue donc à l'aide de ce pointeur. Au lieu de balayer les éléments d’un tableau en incrémentant un indice, on se sert du « pointeur sur l’élément suivant » d’un élement de la liste.

Cette méthode, plus lourde à mettre en oeuvre, permet d’ajuster en temps réel la taille de la liste, alors qu’elle est figée dans le cas d’un tableau.

Figure 16 ‐‐10 : Liste chaînée 

Mettons en évidence les adresses pour illustrer le fonctionnement des pointeurs :

Dans cet exemple, la présence d'un seul pointeur (sur l'élément suivant) ne permet de parcourir la liste que dans un seul sens. Il suffit de rajouter un deuxième pointeur (sur l'élément précédent) pour pouvoir la parcourir dans les deux sens.

La liste chaînée est une application typique de l'allocation dynamique : la réservation des variables de la liste est réalisée au fur et à mesure des besoins. Les éléments de la liste ne sont pas consécutifs en mémoire.

Voici un modèle de structure qui permet de définir une liste chaînée du type "arbre généalogique" (remarquez l'auto‐imbrication du type structuré : on dit que la structure est récursive) :

Télécharger le fichier .c

On remarque que le type structuré est repéré par deux noms différents :

– le nom T_ENFANT sera utilisé dans toute la suite du programme (notamment pour définir les variables) ;

– le nom struct t_enfant (synonyme de T_ENFANT) est créé seulement pour permettre la récursivité : on ne peut pas définir les champs Pere et Mere à partir du type T_ENFANT, car celui-ci ne sera connu du compilateur que quelques lignes plus loin ...

Cet exemple s'écarte du mécanisme de liste chaînée illustré par le schéma ci‐dessus, dans la mesure où un élément de la liste permet d'obtenir deux autres éléments (ses parents). Il s'agit d'un arbre binaire.