Comment implémenter une liste chaînée en C en 2026

Introduction

En 2026, le langage C reste incontournable pour les systèmes embarqués, les kernels et les applications performantes où la gestion manuelle de la mémoire est primordiale. Contrairement aux langages modernes comme Rust ou Go, C n'offre pas de collections intégrées : vous devez implémenter vos propres structures de données. La liste chaînée (singly linked list) est un pilier intermédiaire, permettant des insertions et suppressions en O(1) à la tête, idéale pour les files d'attente ou les piles dynamiques.

Ce tutoriel vous guide pas-à-pas pour créer une liste chaînée stockant des entiers : définition de la structure Node, allocation dynamique avec malloc, insertions (tête/queue), parcours, suppression et libération complète. Chaque étape inclut un programme complet et fonctionnel, compilable avec gcc. Vous apprendrez à éviter les fuites mémoire, un piège classique en C. À la fin, vous maîtriserez une implémentation robuste, bookmarquée par tout pro C. Prêt à coder ? (142 mots)

Prérequis

Connaissances de base en C : variables, boucles for/while, conditions if.
Maîtrise des pointeurs et structures (struct).
Outils : GCC installé (gcc --version), éditeur comme VS Code ou Vim.
Compilation : gcc fichier.c -o exe && ./exe.
Temps estimé : 20 minutes.

Étape 1 : Structure Node et création d'un nœud

liste_creation.c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* create_node(int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (new_node == NULL) {
        fprintf(stderr, "Erreur allocation mémoire\n");
        return NULL;
    }
    new_node->data = value;
    new_node->next = NULL;
    return new_node;
}

int main() {
    Node* head = create_node(42);
    if (head != NULL) {
        printf("Nœud créé : %d\n", head->data);
        free(head);
    }
    return 0;
}

Ce programme définit la structure Node avec une donnée int et un pointeur next. La fonction create_node alloue dynamiquement via malloc, initialise et vérifie l'échec d'allocation. Dans main, on crée un nœud isolé, l'affiche et le libère immédiatement. Compilez avec gcc liste_creation.c -o creation && ./creation pour tester. Piège : toujours vérifier malloc != NULL.

Comprendre les bases : Pointeurs et allocation

Imaginez un nœud comme un wagon de train : data est la marchandise, next le crochet vers le suivant. malloc réserve l'espace heap (pas stack), retourné par pointeur. Sans free, fuite mémoire ! Cette étape pose les fondations : une liste vide est head = NULL. Prochaine : insertion en tête, comme ajouter un wagon devant.

Étape 2 : Insertion en tête de liste

liste_insert_tete.c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* create_node(int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (new_node == NULL) {
        return NULL;
    }
    new_node->data = value;
    new_node->next = NULL;
    return new_node;
}

Node* insert_head(Node* head, int value) {
    Node* new_node = create_node(value);
    if (new_node == NULL) return head;
    new_node->next = head;
    return new_node;
}

void print_list(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void free_list(Node* head) {
    Node* current = head;
    while (current != NULL) {
        Node* next = current->next;
        free(current);
        current = next;
    }
}

int main() {
    Node* head = NULL;
    head = insert_head(head, 10);
    head = insert_head(head, 20);
    head = insert_head(head, 30);
    print_list(head);
    free_list(head);
    return 0;
}

On ajoute insert_head : crée un nouveau nœud, lie son next à l'ancien head, et retourne le nouveau tête. print_list parcourt via while jusqu'à NULL. free_list libère récursivement sans recursion stack. Exécutez : affiche "30 -> 20 -> 10 -> NULL". Efficace O(1), parfait pour stacks.

Insertion en tête : Pourquoi O(1) ?

L'insertion tête est triviale car on n'a pas besoin de traverser la liste. Analogie : ajouter une page au début d'un cahier. On introduit aussi print_list pour visualiser (flèche -> simule liens) et free_list pour éviter leaks. Note : head est passé par valeur, on retourne le nouveau pour assigner.

Étape 3 : Insertion en queue (fin de liste)

liste_insert_queue.c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* create_node(int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (new_node == NULL) return NULL;
    new_node->data = value;
    new_node->next = NULL;
    return new_node;
}

Node* insert_head(Node* head, int value) {
    Node* new_node = create_node(value);
    if (new_node == NULL) return head;
    new_node->next = head;
    return new_node;
}

Node* insert_tail(Node* head, int value) {
    Node* new_node = create_node(value);
    if (new_node == NULL || head == NULL) return head;
    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = new_node;
    return head;
}

void print_list(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void free_list(Node* head) {
    Node* current = head;
    while (current != NULL) {
        Node* next = current->next;
        free(current);
        current = next;
    }
}

int main() {
    Node* head = NULL;
    head = insert_tail(head, 10);
    head = insert_tail(head, 20);
    head = insert_tail(head, 30);
    print_list(head);
    free_list(head);
    return 0;
}

insert_tail parcourt jusqu'au dernier nœud (O(n)), puis lie. Gère liste vide. Test : "10 -> 20 -> 30 -> NULL". Utile pour queues FIFO. Piège : si head NULL, ne pas crasher ; ici on return head inchangé.

Insertion queue vs tête

Tête : O(1), idéal stacks LIFO.
Queue : O(n), mais simple sans double lien.

Pour O(1) queue, ajoutez un tail pointer (avancé).

Étape 4 : Suppression d'un nœud par valeur

liste_suppression.c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* create_node(int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (new_node == NULL) return NULL;
    new_node->data = value;
    new_node->next = NULL;
    return new_node;
}

Node* insert_head(Node* head, int value) {
    Node* new_node = create_node(value);
    if (new_node == NULL) return head;
    new_node->next = head;
    return new_node;
}

Node* delete_by_value(Node* head, int value) {
    if (head == NULL) return NULL;
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    Node* current = head;
    while (current->next != NULL && current->next->data != value) {
        current = current->next;
    }
    if (current->next != NULL) {
        Node* temp = current->next;
        current->next = temp->next;
        free(temp);
    }
    return head;
}

void print_list(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void free_list(Node* head) {
    Node* current = head;
    while (current != NULL) {
        Node* next = current->next;
        free(current);
        current = next;
    }
}

int main() {
    Node* head = NULL;
    head = insert_head(head, 30);
    head = insert_head(head, 20);
    head = insert_head(head, 10);
    printf("Avant : "); print_list(head);
    head = delete_by_value(head, 20);
    printf("Après suppression 20 : "); print_list(head);
    free_list(head);
    return 0;
}

delete_by_value gère cas tête et milieu/fin : sauvegarde next avant free pour éviter dangling pointer. O(n) parcours. Test supprime 20 : "30 -> 10 -> NULL". Crucial : free le nœud supprimé !

Étape 5 : Programme complet avec menu interactif

liste_complete.c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* create_node(int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (new_node == NULL) return NULL;
    new_node->data = value;
    new_node->next = NULL;
    return new_node;
}

Node* insert_head(Node* head, int value) {
    Node* new_node = create_node(value);
    if (new_node == NULL) return head;
    new_node->next = head;
    return new_node;
}

Node* insert_tail(Node* head, int value) {
    Node* new_node = create_node(value);
    if (new_node == NULL || head == NULL) return insert_head(head, value);
    Node* current = head;
    while (current->next != NULL) current = current->next;
    current->next = new_node;
    return head;
}

Node* delete_by_value(Node* head, int value) {
    if (head == NULL) return NULL;
    if (head->data == value) {
        Node* temp = head; head = head->next; free(temp); return head;
    }
    Node* current = head;
    while (current->next && current->next->data != value) current = current->next;
    if (current->next) {
        Node* temp = current->next; current->next = temp->next; free(temp);
    }
    return head;
}

void print_list(Node* head) {
    if (head == NULL) { printf("Liste vide\n"); return; }
    Node* current = head;
    while (current) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void free_list(Node* head) {
    while (head) {
        Node* temp = head; head = head->next; free(temp);
    }
}

int main() {
    Node* head = NULL;
    int choice, value;
    do {
        printf("\n1. Insert tête | 2. Insert queue | 3. Supprimer | 4. Afficher | 0. Quitter\nChoix: ");
        scanf("%d", &choice);
        switch(choice) {
            case 1: printf("Valeur: "); scanf("%d", &value); head = insert_head(head, value); break;
            case 2: printf("Valeur: "); scanf("%d", &value); head = insert_tail(head, value); break;
            case 3: printf("Valeur à supp: "); scanf("%d", &value); head = delete_by_value(head, value); break;
            case 4: print_list(head); break;
        }
    } while (choice != 0);
    free_list(head);
    return 0;
}

Programme interactif avec switch menu : teste toutes ops. insert_tail fallback sur head si vide. Boucle do-while jusqu'à 0. Robuste pour tests. Exécutez et jouez : insérez 1,2,3, supprimez 2.

Bonnes pratiques

Toujours vérifier malloc : if (!ptr) return NULL; évite segfault.
Libérer systématiquement : utilisez free_list à la fin de main.
Sauvegarder next avant free : temp = current->next; free(current);.
Gérer liste vide : if (head == NULL) return; partout.
Compiler avec warnings : gcc -Wall -Wextra -std=c11 fichier.c -o exe pour détecter issues.

Erreurs courantes à éviter

Fuites mémoire : Oublier free → Valgrind (valgrind ./exe) pour détecter.
Dangling pointers : Accéder après free → segfault.
NULL dereference : head->data sans check → crash.
Boucle infinie : while (current->next) sans != NULL.
scanf sans flush : Ajoutez fflush(stdin); si inputs foireux (rare en C moderne).

Pour aller plus loin

Implémentez liste doublement chaînée ou circulaire.
Optimisez avec tail pointer pour O(1) insert_tail.
Utilisez dans un projet : parseur JSON minimal ou simulateur file d'attente.
Ressources : K&R C (2e éd.), Beej's Guide to C.
Découvrez nos formations Learni sur C embarqué et systèmes.