Les listes chaînées
Ce que ce chapitre apporte 5 points
- Déclarer un nœud, c'est-à-dire une structure qui pointe vers elle-même.
- Construire une liste, la parcourir, et la libérer entièrement.
- Insérer et retirer un élément en tête, puis au milieu.
- Comparer une liste et un tableau sur l'accès, l'insertion et la place occupée.
- Reconnaître les deux fautes propres aux listes : le maillon perdu et le nœud libéré trop tôt.
Un tableau a une taille décidée avant de savoir combien de valeurs arriveront, et insérer au milieu suppose de décaler tout ce qui suit. Le chapitre d'algorithmique sur les listes chaînées chiffre cet arbitrage sans pointeurs, avec deux tableaux parallèles, et c'est la même structure : ce que le C appelle un pointeur y est une position. Le chapitre sur la mémoire dynamique a montré la première parade, celle du tableau qui double sa capacité ; ce chapitre montre la seconde, qui ne recopie jamais rien.
Une liste chaînée est une suite de petits blocs, chacun portant une valeur et l'adresse du suivant. Elle grandit d'un bloc à la fois, s'insère en changeant deux pointeurs, et ne connaît aucune limite de capacité autre que la mémoire elle-même. Le prix est immédiat et se paie à chaque accès : pour atteindre le dixième élément, il faut passer par les neuf premiers.
Un nœud qui désigne le suivant
Trois choses tiennent la liste entière.
Le champ suivant est un pointeur vers la même structure. C'est permis parce qu'un pointeur a une
taille connue, quatre ou huit octets, alors qu'un champ struct Noeud suivant; donnerait une
structure de taille infinie, ce que l'interpréteur refuse en le disant.
NULL marque la fin de la liste. Sans cette marque, le parcours continuerait dans une adresse
quelconque.
La boucle de parcours est toujours la même : partir de la tête, s'arrêter à NULL, avancer par
p = p->suivant.
La tête suffit à désigner la liste. Une liste n'a pas de nom propre : elle est désignée par un seul pointeur, celui de son premier nœud. Une liste vide est donc un pointeur qui vaut NULL, et non un objet particulier.
C'est ce qui rend les fonctions sur les listes si dépouillées, et c'est aussi ce qui oblige à passer l'adresse de ce pointeur quand une fonction doit changer la tête.
1.Pourquoi un nœud contient-il un pointeur vers sa structure, et non la structure elle-même ?
2.Comment reconnaît-on la fin d'une liste ?
Construire en ajoutant en tête
Créer les nœuds à la main ne passe pas l'échelle. Une boucle suffit, et l'insertion en tête est l'opération la moins chère de toutes.
La liste s'affiche à l'envers de l'ordre d'insertion, et c'est normal : chaque nouveau nœud passe devant. Une liste construite ainsi est d'ailleurs une pile, au sens du chapitre sur les fonctions.
libere_tout et relancer : le programme affiche exactement la même chose, et le relevé sous la sortie annonce cinq blocs encore actifs, avec la ligne du malloc fautif. Une fuite ne change rien à ce que le lecteur voit, et c'est ce qui la rend durable.Porter ensuite la boucle à 20000 valeurs, toujours sans libération, et compter les éléments obtenus : la liste s'arrête de grandir vers 7600. Le tas de ces pages est alors plein,
malloc rend NULL, et la fonction d'ajout rend la liste inchangée plutôt que d'écrire dans le vide. C'est le test contre NULL qui transforme une panne de mémoire en liste plus courte.
L'ordre de libération, qui ne pardonne pas
Deux lignes dans le mauvais ordre suffisent. Hors de ces pages, cette lecture rend le plus souvent la bonne adresse, parce que les octets libérés n'ont pas encore été réemployés : le programme marche, puis cesse de marcher le jour où une autre allocation vient s'installer là.
La forme correcte retient le suivant avant de libérer, comme le fait libere_tout plus haut.
Insérer et retirer au milieu
L'ordre des deux affectations de insere_apres n'est pas négociable. Écrire d'abord
p->suivant = neuf perdrait l'adresse de la suite, et tous les nœuds qui suivent deviendraient
inaccessibles : ils occuperaient toujours la mémoire, sans qu'aucun pointeur ne permette de les
retrouver ni de les libérer.
Le retrait en tête change la tête, donc la fonction doit la rendre et l'appelant doit la réaffecter. C'est la conséquence directe du fait qu'une liste est désignée par un simple pointeur.
La règle qui l'évite tient en une phrase : brancher le nouveau maillon sur la suite avant de brancher le précédent sur lui. Et pour un retrait, refermer la chaîne avant de libérer.
1.Dans quel ordre insérer un nœud au milieu ?
2.Que faut-il faire avant de libérer un nœud pendant un parcours ?
Liste ou tableau
| Tableau | Liste chaînée | |
|---|---|---|
Accès à l'élément i | immédiat, un calcul d'adresse | il faut traverser i nœuds |
| Insertion en tête | décale tout le reste | deux affectations |
| Insertion au milieu | décale tout ce qui suit | deux affectations, une fois le nœud trouvé |
| Ajout à la fin | immédiat s'il reste de la place | il faut traverser toute la liste |
| Place pour 1000 entiers | 4000 octets | 8000 octets avec un pointeur de 4 octets |
| Voisinage en mémoire | contigu, donc lu par blocs | dispersé, un saut par nœud |
La dernière ligne est celle qu'on oublie, et c'est souvent la plus décisive. Un tableau se lit par paquets d'octets consécutifs, ce que la machine fait très vite ; une liste envoie le processeur à une adresse différente à chaque nœud. Pour un parcours complet, un tableau bat une liste de plusieurs fois, alors même que les deux font le même nombre d'opérations.
Quand la liste gagne vraiment. Quand les insertions et les retraits sont fréquents et qu'on tient déjà le nœud concerné, par exemple une file d'attente, une liste de tâches, ou une chaîne de blocs libres dans un allocateur.
Dès que l'accès par indice compte, ou que le parcours complet est l'opération principale, le tableau dynamique du chapitre précédent est le meilleur choix, et de loin.
Quel est le seul avantage décisif d'un tableau sur une liste ?
Mettre en pratique
Une liste se dimensionne comme le reste : en octets et en nombre d'étapes.
Ce que coûte un maillon
- 1.
Un nœud fait d'un int et d'un pointeur de 4 octets occupe combien d'octets ?
- 2.
Le même nœud sur une machine où un pointeur occupe 8 octets ?
- 3.
Une liste de 1000 entiers occupe combien d'octets, avec un pointeur de 4 octets ?
- 4.
Un tableau de 1000 entiers occupe combien d'octets ?
- 5.
Combien de nœuds faut-il traverser pour atteindre le 500e élément d'une liste ?
- 6.
Combien d'étapes pour atteindre le 500e élément d'un tableau ?
- 7.
Combien d'affectations de pointeurs demande une insertion au milieu d'une liste, le nœud précédent étant connu ?
- 8.
Combien d'éléments faut-il décaler pour insérer au début d'un tableau de 1000 cases ?
Les quatre dernières réponses résument le choix : la liste gagne sur l'insertion, le tableau gagne sur l'accès, et rien ne gagne sur les deux.
Pourquoi une fonction qui ajoute en tête doit-elle rendre la nouvelle tête ?
Parce que la liste est désignée par un simple pointeur, et que ce pointeur appartient à l'appelant.
Une fonction qui reçoit struct Noeud *tete en reçoit une copie : elle peut modifier les nœuds,
puisqu'elle en a les adresses, mais elle ne peut pas changer le pointeur de l'appelant.
Deux solutions existent, et les deux se rencontrent dans la vraie vie. Rendre la nouvelle tête, et
obliger l'appelant à écrire liste = ajoute_en_tete(liste, v);. Ou recevoir l'adresse du pointeur,
struct Noeud **tete, et écrire *tete = neuf;, ce qui évite l'oubli de la réaffectation au prix
d'une étoile de plus.
Comment inverser une liste sans allouer un seul nœud ?
En reprenant les pointeurs un par un, avec trois variables : le nœud courant, le précédent, et le suivant retenu avant de couper.
struct Noeud *inverse(struct Noeud *tete) {
struct Noeud *precedent = NULL;
while (tete != NULL) {
struct Noeud *suivant = tete->suivant;
tete->suivant = precedent;
precedent = tete;
tete = suivant;
}
return precedent;
}
Aucun malloc, aucun free, aucune recopie de valeur : seuls les liens changent. C'est l'exercice
qui distingue le mieux ceux qui ont compris qu'une liste n'est faite que de pointeurs.
Une application garde 100 000 mesures et doit surtout calculer leur moyenne. Liste ou tableau ?
Tableau, sans hésitation, et pour deux raisons qui se cumulent.
La place d'abord : 400 000 octets contre 800 000, puisque chaque nœud paie son pointeur.
Le parcours ensuite, et c'est le plus important. Les cases d'un tableau se suivent, donc la machine les lit par blocs et anticipe la suite ; les nœuds d'une liste sont dispersés, et chaque saut coûte. À nombre d'opérations identique, l'écart mesuré se compte en facteur, pas en pourcentage.
La liste redeviendrait le bon choix si l'application passait son temps à insérer et retirer des mesures au milieu, ce qui n'est pas le cas d'un calcul de moyenne.
Chapitre révisé en octobre 2026 · Une erreur dans ce chapitre ?
Dans la bibliothèque d'exercices
Le nœud qui désigne le suivant, l'ordre des deux affectations, et ce que coûte un accès par rapport à un tableau.
- Ce que coûte un maillonNiveau 2
- Accès et insertion, liste contre tableauNiveau 2
- L'ordre des pointeursNiveau 3