Liste chaînée en C : insérer, supprimer, libérer sans fuite

Ta liste chaînée affiche les bons nombres, dans le bon ordre. Puis Valgrind annonce des blocs « definitely lost », ou le programme plante à la toute dernière ligne, au moment de tout libérer. Les listes chaînées ont trois endroits où l'on perd un pointeur, et on va les traverser un par un, sur un programme complet qui finit sans la moindre fuite.

Le maillon : une structure qui pointe sur elle-même

Chaque élément de la liste est une structure qui contient une valeur et l'adresse de l'élément suivant.

struct node {    int value;    struct node *next;};

Une structure ne peut pas contenir un membre de son propre type (elle serait infinie), mais elle peut contenir un pointeur vers son propre type : un pointeur a une taille fixe, 8 octets sur une machine 64 bits, quoi qu'il désigne. Sur ces machines, un struct node occupe 16 octets : 4 pour l'int, 4 octets de remplissage pour aligner le pointeur, 8 pour next. Valgrind le confirmera plus bas en parlant de blocs de 16 octets.

La liste elle-même n'est rien d'autre qu'un pointeur vers le premier maillon, head. Une liste vide, c'est head == NULL. Pas de taille, pas d'indices : pour atteindre le troisième élément, il faut suivre deux flèches.

Le programme complet, vérifié par Valgrind

Voici la liste entière : création d'un maillon, insertion en tête et en queue, affichage, suppression d'une valeur, libération. Les sections suivantes reprennent chaque fonction avec ce qui se passe en mémoire.

1#include <stdio.h>2#include <stdlib.h>3
4struct node {5    int value;6    struct node *next;7};8
9struct node *new_node(int value)10{11    struct node *n = malloc(sizeof *n);12
13    if (n == NULL)14        return NULL;15    n->value = value;16    n->next = NULL;17    return n;18}19
20int push_front(struct node **head, int value)21{22    struct node *n = new_node(value);23
24    if (n == NULL)25        return -1;26    n->next = *head;27    *head = n;28    return 0;29}30
31int push_back(struct node **head, int value)32{33    struct node *n = new_node(value);34    struct node *cur;35
36    if (n == NULL)37        return -1;38    if (*head == NULL) {39        *head = n;40        return 0;41    }42    cur = *head;43    while (cur->next != NULL)44        cur = cur->next;45    cur->next = n;46    return 0;47}48
49void print_list(const struct node *head)50{51    for (const struct node *cur = head; cur != NULL; cur = cur->next)52        printf("%d -> ", cur->value);53    printf("NULL\n");54}55
56void remove_value(struct node **head, int value)57{58    struct node *prev = NULL;59    struct node *cur = *head;60
61    while (cur != NULL && cur->value != value) {62        prev = cur;63        cur = cur->next;64    }65    if (cur == NULL)66        return;67    if (prev == NULL)68        *head = cur->next;69    else70        prev->next = cur->next;71    free(cur);72}73
74void free_list(struct node *head)75{76    while (head != NULL) {77        struct node *next = head->next;78
79        free(head);80        head = next;81    }82}83
84int main(void)85{86    struct node *head = NULL;87
88    push_front(&head, 2);89    push_front(&head, 1);90    push_back(&head, 3);91    push_back(&head, 4);92    print_list(head);93    remove_value(&head, 3);94    print_list(head);95    remove_value(&head, 1);96    print_list(head);97    free_list(head);98    return 0;99}

$ gcc -Wall -Wextra -g liste.c -o liste$ ./liste1 -> 2 -> 3 -> 4 -> NULL1 -> 2 -> 4 -> NULL2 -> 4 -> NULL$ valgrind ./liste==15== Memcheck, a memory error detector==15== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.==15== Using Valgrind-3.24.0 and LibVEX; rerun with -h for copyright info==15== Command: ./liste==15== 1 -> 2 -> 3 -> 4 -> NULL1 -> 2 -> 4 -> NULL2 -> 4 -> NULL==15== ==15== HEAP SUMMARY:==15==     in use at exit: 0 bytes in 0 blocks==15==   total heap usage: 5 allocs, 5 frees, 1,088 bytes allocated==15== ==15== All heap blocks were freed -- no leaks are possible==15== ==15== For lists of detected and suppressed errors, rerun with: -s==15== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Les deux lignes à regarder : All heap blocks were freed -- no leaks are possible et ERROR SUMMARY: 0 errors. Il faut les deux, on verra plus bas un programme qui obtient la première sans la seconde.

Tu te demandes peut-être pourquoi 5 allocations pour 4 maillons. La cinquième vient de la bibliothèque C : le tampon de sortie qu'elle réserve au premier printf. Les 4 maillons font 64 octets, le tampon en fait 1 024 quand la sortie est un terminal. Redirige la sortie vers un fichier et le total change, preuve que ce bloc dépend de stdout et pas de ta liste :

$ valgrind ./liste > sortie.txt 2> rapport.txt; grep "total heap" rapport.txt==15==   total heap usage: 5 allocs, 5 frees, 4,160 bytes allocated

Remarque aussi que main ne teste pas le retour de push_front et push_back. Si malloc échouait, la fonction renverrait -1 sans rien modifier : la liste serait plus courte, mais rien ne fuirait et rien ne planterait. Dans un vrai programme, on testerait ce retour.

Insérer en tête : pourquoi push_front prend un struct node **

Insérer en tête, c'est deux affectations : le nouveau maillon pointe sur l'ancienne tête, puis la tête devient le nouveau maillon. L'ordre compte. Dans l'autre sens, on écraserait head avant d'avoir sauvé l'adresse de l'ancien premier maillon, et le reste de la liste serait perdu.

Voici la mémoire pendant le deuxième appel, push_front(&head, 1), juste après n->next = *head; (ligne 26) et avant *head = n; :

La ligne suivante, *head = n;, écrit dans la variable head de main, parce que le head de push_front contient son adresse. C'est tout l'intérêt du double pointeur. Si push_front recevait head par valeur, elle modifierait une copie, exactement comme le swap raté de l'article sur les pointeurs en C :

#include <stdio.h>#include <stdlib.h>
struct node {    int value;    struct node *next;};
void push_front(struct node *head, int value){    struct node *n = malloc(sizeof *n);
    n->value = value;    n->next = head;    head = n;}
int main(void){    struct node *head = NULL;
    push_front(head, 1);    printf("head = %p\n", (void *)head);    return 0;}

$ gcc -Wall -Wextra -g tete.c -o tete$ ./tetehead = (nil)$ valgrind --leak-check=full ./tete==25== Memcheck, a memory error detector==25== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.==25== Using Valgrind-3.24.0 and LibVEX; rerun with -h for copyright info==25== Command: ./tete==25== head = (nil)==25== ==25== HEAP SUMMARY:==25==     in use at exit: 16 bytes in 1 blocks==25==   total heap usage: 2 allocs, 1 frees, 1,040 bytes allocated==25== ==25== 16 bytes in 1 blocks are definitely lost in loss record 1 of 1==25==    at 0x488545C: malloc (vg_replace_malloc.c:446)==25==    by 0x40069B: push_front (tete.c:11)==25==    by 0x4006E3: main (tete.c:22)==25== ==25== LEAK SUMMARY:==25==    definitely lost: 16 bytes in 1 blocks==25==    indirectly lost: 0 bytes in 0 blocks==25==      possibly lost: 0 bytes in 0 blocks==25==    still reachable: 0 bytes in 0 blocks==25==         suppressed: 0 bytes in 0 blocks==25== ==25== For lists of detected and suppressed errors, rerun with: -s==25== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Aucun warning, aucun crash, et pourtant head vaut toujours NULL après l'appel. Le maillon alloué ligne 11 n'est plus désigné par personne quand push_front se termine : Valgrind le classe « definitely lost », 16 octets, la taille d'un struct node.

Insérer en queue : parcourir jusqu'au dernier maillon

Pour ajouter à la fin, il faut trouver le maillon dont next vaut NULL, puis y accrocher le nouveau. Il y a un cas particulier : la liste vide, où il n'existe aucun dernier maillon et où c'est head lui-même qu'il faut modifier (lignes 38 à 41). D'où le struct node ** ici aussi.

1. 1

   Allouer le maillon, avec next à NULL puisqu'il sera le dernier.

2. 2

   Si la liste est vide, faire de lui la tête, et c'est fini.

3. 3

   Sinon, avancer cur tant que cur->next n'est pas NULL.

4. 4

   Écrire l'adresse du nouveau maillon dans cur->next.

Après les quatre insertions de main, la liste est complète :

L'insertion en queue parcourt toute la liste à chaque appel. Pour des milliers d'insertions, on garde en plus un pointeur vers le dernier maillon ; pour apprendre, la version simple suffit.

Parcourir une liste chaînée

Le parcours est toujours la même boucle : partir de la tête, traiter le maillon, passer à next, s'arrêter sur NULL. print_list l'écrit sous forme de for :

for (const struct node *cur = head; cur != NULL; cur = cur->next)    printf("%d -> ", cur->value);

Le const dit que la fonction ne modifie pas les maillons, et la boucle ne touche qu'à sa variable cur, une copie : le head de l'appelant ne bouge pas. Compter, chercher, additionner, appliquer une fonction à chaque valeur, tout part de ce squelette.

list_node_count

Compte les maillons d'une liste dont tu ne reçois que la tête : c'est la boucle de print_list, avec un compteur à la place du printf. Le maillon de l'exercice s'appelle ListNode et porte un void *data, et les tests passent aussi une liste vide (NULL) et une liste d'un seul maillon.

Ouvrir l'exercice

Supprimer un élément sans perdre de pointeur

Supprimer un maillon, c'est faire pointer son prédécesseur sur son successeur, puis le libérer. remove_value avance donc avec deux pointeurs, prev un cran derrière cur, pour avoir sous la main le maillon à raccrocher. Voici remove_value(&head, 3) juste après le raccrochage (ligne 70), avant le free :

À cet instant, cur est le seul pointeur qui mène encore à n3. Si la fonction se termine sans free(cur), cette adresse disparaît avec la variable locale, et le bloc est perdu pour de bon. C'est le pointeur perdu classique : la liste s'affiche parfaitement, seule la mémoire sait. Mets le free(cur); de liste.c en commentaire (/* free(cur); */, pour garder les mêmes numéros de ligne), enregistre le résultat sous oubli.c et relance Valgrind :

$ gcc -Wall -Wextra -g oubli.c -o oubli$ ./oubli1 -> 2 -> 3 -> 4 -> NULL1 -> 2 -> 4 -> NULL2 -> 4 -> NULL$ valgrind --leak-check=full ./oubli==35== Memcheck, a memory error detector==35== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.==35== Using Valgrind-3.24.0 and LibVEX; rerun with -h for copyright info==35== Command: ./oubli==35== 1 -> 2 -> 3 -> 4 -> NULL1 -> 2 -> 4 -> NULL2 -> 4 -> NULL==35== ==35== HEAP SUMMARY:==35==     in use at exit: 32 bytes in 2 blocks==35==   total heap usage: 5 allocs, 3 frees, 1,088 bytes allocated==35== ==35== 16 bytes in 1 blocks are definitely lost in loss record 1 of 2==35==    at 0x488545C: malloc (vg_replace_malloc.c:446)==35==    by 0x400717: new_node (oubli.c:11)==35==    by 0x400767: push_front (oubli.c:22)==35==    by 0x4009AB: main (oubli.c:89)==35== ==35== 16 bytes in 1 blocks are definitely lost in loss record 2 of 2==35==    at 0x488545C: malloc (vg_replace_malloc.c:446)==35==    by 0x400717: new_node (oubli.c:11)==35==    by 0x4007BF: push_back (oubli.c:33)==35==    by 0x4009B7: main (oubli.c:90)==35== ==35== LEAK SUMMARY:==35==    definitely lost: 32 bytes in 2 blocks==35==    indirectly lost: 0 bytes in 0 blocks==35==      possibly lost: 0 bytes in 0 blocks==35==    still reachable: 0 bytes in 0 blocks==35==         suppressed: 0 bytes in 0 blocks==35== ==35== For lists of detected and suppressed errors, rerun with: -s==35== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

Deux blocs perdus, et Valgrind dit lesquels par la pile d'appels qui les a créés : celui du push_front de la ligne 89 (la valeur 1) et celui du push_back de la ligne 90 (la valeur 3). Ce sont exactement les deux maillons supprimés.

Le cas de la tête mérite un mot. Quand la valeur cherchée est dans le premier maillon, il n'y a pas de prédécesseur (prev vaut NULL) et c'est *head qu'il faut faire avancer : encore une raison de recevoir struct node **. On peut d'ailleurs supprimer ce cas particulier en parcourant la liste avec un pointeur vers le lien à modifier plutôt qu'avec prev :

void remove_value(struct node **head, int value){    struct node **link = head;
    while (*link != NULL && (*link)->value != value)        link = &(*link)->next;    if (*link != NULL) {        struct node *victim = *link;
        *link = victim->next;        free(victim);    }}

link désigne d'abord head, puis le champ next du maillon courant. Supprimer revient toujours à réécrire *link, que ce soit la tête ou un next. Cette version, substituée dans liste.c, donne la même sortie et passe Valgrind sans erreur. Choisis celle que tu relis le plus facilement.

list_filter

Supprime et libère tous les maillons dont la valeur correspond à une référence, en recevant ListNode **begin pour pouvoir changer la tête. C'est remove_value en boucle, avec une fonction de comparaison passée en paramètre ; les tests couvrent une tête qui correspond, plusieurs correspondances d'affilée et une liste entièrement vidée.

Ouvrir l'exercice

Libérer une liste chaînée sans lire après free

Pour libérer une liste, il faut libérer chaque maillon, et c'est là qu'on écrit le bug le plus tentant de tout l'article :

while (head != NULL) {    free(head);    head = head->next;}

while (head != NULL) {    struct node *next = head->next;
    free(head);    head = next;}

Après free(head), le bloc n'appartient plus au programme : lire head->next est un comportement indéfini. La mémoire au moment fautif :

Remplace la bonne boucle de liste.c par la mauvaise, et tu obtiens apres_free.c. Ici, GCC repère le bug dès la compilation (-Wuse-after-free fait partie de -Wall) et le programme plante à la fin. Mais lis bien la sortie de Valgrind :

$ gcc -Wall -Wextra -g apres_free.c -o apres_freeapres_free.c: In function 'free_list':apres_free.c:78:14: warning: pointer 'head' used after 'free' [-Wuse-after-free]   78 |         head = head->next;      |         ~~~~~^~~~~~~~~~~~apres_free.c:77:9: note: call to 'free' here   77 |         free(head);      |         ^~~~~~~~~~$ ./apres_free1 -> 2 -> 3 -> 4 -> NULL1 -> 2 -> 4 -> NULL2 -> 4 -> NULLSegmentation fault$ valgrind ./apres_free==45== Memcheck, a memory error detector==45== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.==45== Using Valgrind-3.24.0 and LibVEX; rerun with -h for copyright info==45== Command: ./apres_free==45== 1 -> 2 -> 3 -> 4 -> NULL1 -> 2 -> 4 -> NULL2 -> 4 -> NULL==45== Invalid read of size 8==45==    at 0x400968: free_list (apres_free.c:78)==45==    by 0x4009FF: main (apres_free.c:95)==45==  Address 0x4a7f048 is 8 bytes inside a block of size 16 free'd==45==    at 0x48884F8: free (vg_replace_malloc.c:989)==45==    by 0x400963: free_list (apres_free.c:77)==45==    by 0x4009FF: main (apres_free.c:95)==45==  Block was alloc'd at==45==    at 0x488545C: malloc (vg_replace_malloc.c:446)==45==    by 0x400717: new_node (apres_free.c:11)==45==    by 0x400767: push_front (apres_free.c:22)==45==    by 0x4009A3: main (apres_free.c:86)==45== ==45== ==45== HEAP SUMMARY:==45==     in use at exit: 0 bytes in 0 blocks==45==   total heap usage: 5 allocs, 5 frees, 1,088 bytes allocated==45== ==45== All heap blocks were freed -- no leaks are possible==45== ==45== For lists of detected and suppressed errors, rerun with: -s==45== ERROR SUMMARY: 2 errors from 1 contexts (suppressed: 0 from 0)

Le rapport se lit de haut en bas. Invalid read of size 8 : une lecture de 8 octets, la taille du pointeur next, ligne 78. 8 bytes inside a block of size 16 free'd : à 8 octets du début d'un bloc de 16 octets déjà libéré, soit exactement le champ next d'un struct node. Puis Valgrind dit où le bloc a été libéré (ligne 77) et où il avait été alloué.

Et en bas, All heap blocks were freed -- no leaks are possible. Tous les blocs ont bien été rendus, il n'y a pas de fuite, mais le programme a lu de la mémoire libérée en chemin. D'où la règle : regarde toujours ERROR SUMMARY, pas seulement le résumé des fuites. Sous Valgrind, le programme n'a même pas planté ; sans lui, sur une autre machine ou avec une autre version de la glibc, il aurait aussi pu terminer sans rien dire. Le détail de chaque message est dans Lire un rapport Valgrind.

Le parcours C sur les listes

Les listes chaînées concentrent tout ce qui rend les pointeurs difficiles : allocation, double indirection, ordre des affectations, libération. Le module du parcours C qui leur est consacré les reprend dans l'ordre, du simple parcours au raccrochage de maillons, avec des tests qui exécutent vraiment ton code.

Questions fréquentes