Les listes chaînées

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 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.

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.

À manipuler

Supprimer l'appel à 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.

Le maillon perdu

Une seule affectation dans le mauvais ordre coupe la liste en deux, et la moitié qui suit n'est plus désignée par personne. Ce n'est pas une erreur d'exécution : le programme continue avec une liste plus courte, et la mémoire des nœuds perdus ne sera rendue qu'à la fin du programme.
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.

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.

À calculer soi-même

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.

Vérification

Vérification rapideon peut se reprendre

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 ?

3.Dans quel ordre insérer un nœud au milieu ?

4.Que faut-il faire avant de libérer un nœud pendant un parcours ?

5.Quel est le seul avantage décisif d'un tableau sur une liste ?

Exercices type

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.

La méthode

Déclarer le nœud avec un pointeur vers lui-même, jamais avec la structure elle-même.
Poser NULL à la création : le dernier nœud doit marquer la fin.
Retenir le suivant avant de libérer, dans toute boucle qui détruit.
Brancher le nouveau maillon sur la suite d'abord, le précédent sur lui ensuite.
Rendre la nouvelle tête, ou recevoir l'adresse du pointeur de tête, dès qu'une fonction peut la changer.

Synthèse

Un nœud est une structure qui porte une valeur et l'adresse du suivant ; la liste est désignée par le seul pointeur de tête, et une liste vide vaut NULL.
Le parcours est toujours le même : partir de la tête, s'arrêter à NULL, avancer par p = p->suivant.
Une insertion ou un retrait coûte deux affectations, une fois le bon nœud atteint ; l'atteindre est ce qui coûte.
Libérer une liste demande de retenir le suivant avant le free, et refermer la chaîne avant de libérer un nœud retiré.
Un tableau garde l'avantage sur l'accès par indice et sur le parcours complet, parce que ses cases sont contiguës. La liste garde l'avantage sur les insertions et les retraits fréquents.

Et ensuite

Ce parcours s'arrête ici pour le langage, et ce qu'il a montré suffit à lire la plupart des programmes C. Ce qu'il reste à voir demande un vrai compilateur : les fichiers, la compilation séparée en plusieurs unités, et les bibliothèques.

Pour la suite du raisonnement plutôt que du langage, Algorithmique reprend ces mêmes structures sous l'angle du coût, et Architecture des ordinateurs montre ce que la machine fait réellement de ces adresses.