Linked list in C: insert, delete and free without leaks

Your linked list prints the right numbers in the right order. Then Valgrind reports blocks "definitely lost", or the program crashes on the very last line, while it frees everything. A linked list has three places where you can lose a pointer. Here they are one by one, in a complete program that ends without a single leak.

The node: a struct that points to itself

Each element of the list is a struct that holds a value and the address of the next element.

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

A struct cannot contain a member of its own type (it would be infinite), but it can contain a pointer to its own type: a pointer has a fixed size, 8 bytes on a 64-bit machine, whatever it points to. On those machines, a struct node takes 16 bytes: 4 for the int, 4 bytes of padding to align the pointer, 8 for next. Valgrind confirms it further down when it talks about 16-byte blocks.

The list itself is nothing more than a pointer to the first node, head. An empty list is head == NULL. No size, no indices: to reach the third element, you follow two arrows.

The complete program, checked with Valgrind

Here is the whole list: creating a node, inserting at the head and at the tail, printing, deleting a value, freeing. The sections that follow take each function in turn and show what happens in memory.

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 list.c -o list$ ./list1 -> 2 -> 3 -> 4 -> NULL1 -> 2 -> 4 -> NULL2 -> 4 -> NULL$ valgrind ./list==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: ./list==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)

Two lines matter: All heap blocks were freed -- no leaks are possible and ERROR SUMMARY: 0 errors. You need both. Further down you will see a program that gets the first one without the second.

You may be wondering why there are 5 allocations for 4 nodes. The fifth comes from the C library: the output buffer it sets up on the first printf. The 4 nodes take 64 bytes, and the buffer takes 1,024 when the output is a terminal. Redirect the output to a file and the total changes, which proves that this block depends on stdout and not on your list:

$ valgrind ./list > out.txt 2> report.txt; grep "total heap" report.txt==17==   total heap usage: 5 allocs, 5 frees, 4,160 bytes allocated

Notice also that main never checks what push_front and push_back return. If malloc failed, the function would return -1 without changing anything: the list would be shorter, but nothing would leak and nothing would crash. In a real program, you would check that return value.

Insert at the head: why push_front takes a struct node **

Inserting at the head takes two assignments: the new node points to the old head, then the head becomes the new node. The order matters. The other way round, you would overwrite head before saving the address of the old first node, and the rest of the list would be lost.

Here is memory during the second call, push_front(&head, 1), right after n->next = *head; (line 26) and before *head = n;:

The next line, *head = n;, writes into the head variable of main, because the head of push_front holds its address. That is the whole point of the double pointer. If push_front received head by value, it would modify a copy, exactly like the broken swap in the article on pointers in 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 head.c -o head$ ./headhead = (nil)$ valgrind --leak-check=full ./head==16== Memcheck, a memory error detector==16== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.==16== Using Valgrind-3.24.0 and LibVEX; rerun with -h for copyright info==16== Command: ./head==16== head = (nil)==16== ==16== HEAP SUMMARY:==16==     in use at exit: 16 bytes in 1 blocks==16==   total heap usage: 2 allocs, 1 frees, 1,040 bytes allocated==16== ==16== 16 bytes in 1 blocks are definitely lost in loss record 1 of 1==16==    at 0x488545C: malloc (vg_replace_malloc.c:446)==16==    by 0x40069B: push_front (head.c:11)==16==    by 0x4006E3: main (head.c:22)==16== ==16== LEAK SUMMARY:==16==    definitely lost: 16 bytes in 1 blocks==16==    indirectly lost: 0 bytes in 0 blocks==16==      possibly lost: 0 bytes in 0 blocks==16==    still reachable: 0 bytes in 0 blocks==16==         suppressed: 0 bytes in 0 blocks==16== ==16== For lists of detected and suppressed errors, rerun with: -s==16== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

No warning, no crash, and yet head is still NULL after the call. Once push_front returns, nothing points to the node allocated on line 11 anymore: Valgrind classifies it as "definitely lost", 16 bytes, the size of a struct node.

Insert at the tail: walk to the last node

To append at the end, you have to find the node whose next is NULL, then hook the new node onto it. There is one special case: the empty list, which has no last node, and where head itself must change (lines 38 to 41). Hence the struct node ** here too.

1. 1

   Allocate the node, with next set to NULL since it will be the last one.

2. 2

   If the list is empty, make it the head, and you're done.

3. 3

   Otherwise, move cur forward as long as cur->next is not NULL.

4. 4

   Write the address of the new node into cur->next.

After the four insertions in main, the list is complete:

Inserting at the tail walks the entire list on every call. For thousands of insertions, you would also keep a pointer to the last node; for learning, the simple version is enough.

Traverse a linked list

Traversal is always the same loop: start at the head, process the node, move to next, stop at NULL. print_list writes it as a for:

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

The const says the function does not modify the nodes, and the loop only touches its own variable cur, a copy: the caller's head does not move. Counting, searching, summing, applying a function to every value: all of it starts from this skeleton.

list_node_count

Count the nodes of a list when all you receive is its head: it is the print_list loop with a counter in place of the printf. The node in this exercise is called ListNode and carries a void *data, and the tests also pass an empty list (NULL) and a list with a single node.

Open the exercise

Delete a node without losing a pointer

Deleting a node means making its predecessor point to its successor, then freeing it. So remove_value moves forward with two pointers, prev one step behind cur, to keep the node that needs relinking within reach. Here is remove_value(&head, 3) right after the relinking (line 70), before the free:

At this point, cur is the only pointer that still leads to n3. If the function returns without free(cur), that address disappears along with the local variable, and the block is lost for good. This is the classic lost pointer: the list prints perfectly, and only the memory knows. Comment out the free(cur); in list.c (as /* free(cur); */, to keep the same line numbers), save the result as leak.c and run Valgrind again:

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

Two blocks lost, and Valgrind tells you which ones through the call stack that created them: the one from the push_front on line 89 (the value 1) and the one from the push_back on line 90 (the value 3). Those are exactly the two deleted nodes.

The head deserves a word. When the value you are looking for is in the first node, there is no predecessor (prev is NULL), and it is *head that must move forward: one more reason to receive a struct node **. You can even get rid of this special case by walking the list with a pointer to the link you will modify, instead of with 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 first designates head, then the next field of the current node. Deleting always comes down to rewriting *link, whether that is the head or a next. Dropped into list.c, this version produces the same output and passes Valgrind with no errors. Pick whichever one you find easier to read.

list_filter

Delete and free every node whose value matches a reference, receiving ListNode **begin so you can change the head. It is remove_value in a loop, with a comparison function passed as a parameter; the tests cover a matching head, several matches in a row, and a list that ends up completely empty.

Open the exercise

Free a linked list without reading after free

To free a list, you free each node, and this is where you write the most tempting bug of the whole article:

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

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

After free(head), the block no longer belongs to the program: reading head->next is undefined behavior. Here is memory at the faulty moment:

Replace the correct loop in list.c with the buggy one and you get after_free.c. This time GCC catches the bug at compile time (-Wuse-after-free is part of -Wall) and the program crashes at the end. But read the Valgrind output carefully:

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

Read the report from top to bottom. Invalid read of size 8: a read of 8 bytes, the size of the next pointer, on line 78. 8 bytes inside a block of size 16 free'd: 8 bytes from the start of a 16-byte block that was already freed, which is exactly the next field of a struct node. Then Valgrind tells you where the block was freed (line 77) and where it had been allocated.

And at the bottom: All heap blocks were freed -- no leaks are possible. Every block was indeed given back and there is no leak, but the program read freed memory along the way. Hence the rule: always look at ERROR SUMMARY, not just the leak summary. Under Valgrind, the program did not even crash; without it, on another machine or with another glibc version, it could also have finished without a word. Each message is explained in detail in How to read a Valgrind report.

Linked lists in the C path

Linked lists pack in everything that makes pointers hard: allocation, double indirection, the order of assignments, freeing. The module of the C path dedicated to them goes through it all in order, from a simple traversal to relinking nodes, with tests that actually run your code.

Frequently asked questions