Listes chaînées

Objectifs

À la fin de ce chapitre, vous serez capables de :

• Comprendre le concept de structure de données dynamique
• Manipuler les listes chaînées simples en C
• Implémenter les opérations de base sur les listes chaînées (insertion, suppression, recherche)
• Choisir entre tableaux et listes chaînées selon le contexte

1 Petit point sur les structures de données

The importance of learning DSA – The Tech Insider

Qu’est-ce qu’une structure de données ? C’est une façon d’organiser et de stocker des informations en mémoire pour pouvoir les utiliser efficacement. Une structure de données définit comment les éléments sont reliés entre eux (ou pas), comment on y accède et quelles opérations sont simples ou coûteuses.

Pourquoi c’est important ? Le même problème peut être beaucoup plus facile ou beaucoup plus lent à résoudre selon la structure choisie. Le choix d’une structure de données est donc une des décisions de conception les plus importantes que vous prendrez lors de l’écriture d’un programme.

Il existe de nombreuses structures de données, chacune adaptée à des besoins spécifiques : tableaux, listes chaînées, piles, files d’attente, arbres, graphes, etc. Chacune a ses avantages et inconvénients et est optimisée pour certains types d’opérations.

Exemples

Pensez par exemple à un moteur de recherche qui doit stocker des milliards de pages web et permettre des recherches rapides, ou à une application de messagerie qui doit gérer dynamiquement des conversations entre utilisateurs. Le choix des structures de données utilisées impacte directement les performances et la mise à l’échelle de ces systèmes.

Important

Choisir la bonne structure de données dépend des opérations que vous ferez le plus souvent. Le but ici est de vous donner les outils pour prendre ces décisions de manière éclairée.

2 Limites des tableaux

Jusqu’à présent, nous avons utilisé des tableaux pour stocker des collections d’éléments. Par exemple, pour stocker une liste de notes d’étudiants :

int notes[100];  // Peut stocker jusqu'à 100 notes

Les tableaux présentent cependant plusieurs limitations :

1. Taille fixe : La taille d’un tableau doit être définie à la compilation ou à l’allocation. Si on a besoin de plus d’espace, il faut allouer un nouveau tableau et copier tous les éléments.

2. Insertion/Suppression coûteuse : Pour insérer un élément au milieu d’un tableau, il faut décaler tous les éléments suivants. De même pour la suppression.

// Insertion d'un élément à l'indice 2 dans un tableau de taille 5
// [10, 20, 30, 40, 50] → [10, 20, 25, 30, 40, 50]
// Il faut décaler 30, 40, 50 vers la droite

3. Gaspillage de mémoire : Si on alloue un tableau de 100 éléments mais qu’on n’en utilise que 10, on gaspille 90 emplacements mémoire.

L’idée est d’utiliser une structure de données dynamique qui peut grandir et rétrécir selon les besoins.

Les listes chaînées sont une structure de données qui résout ces problèmes en permettant une allocation dynamique de la mémoire et des insertions/suppressions efficaces.

La notion d’efficacité ici fait référence à un coût en temps d’exécution et en utilisation mémoire faibles pour ces opérations.

3 Concept de liste chaînée

3.1 Définition

Une liste chaînée est une structure de données composée d’une séquence de cellules (ou de nœuds), où chaque cellule contient :

• Une donnée (valeur stockée)
• Un pointeur vers la cellule suivante (la position mémoire de la cellule suivante)

Stocker deux informations dans une seule variable

Comme nous allons donc stocker deux informations dans chaque cellule, une cellule sera donc représentée en mémoire par une structure contenant la donnée et le pointeur.

La première cellule de la liste est souvent appelée la tête (head) de liste, et la dernière cellule est celle qui pointe vers NULL pour indiquer la fin de la liste.

3.2 Visualisation

Voici une liste chaînée contenant les valeurs 10, 20 et 30 :

---
config:
    look: 'handDrawn'
---
graph LR
    A["[10 | @]"] --> B["[20 | @]"] --> C["[30 | NULL]"]

    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

Chaque boîte représente une cellule avec :

• La partie gauche contient la donnée (10, 20, 30)
• La partie droite (@) représente le pointeur vers la cellule suivante

Différence fondamentale avec un tableau :

• Dans un tableau, les éléments sont stockés de manière contiguë en mémoire (les uns à côté des autres)
• Dans une liste chaînée, les cellules peuvent être dispersées en mémoire, et c’est le pointeur qui permet de passer de l’une à l’autre

3.3 Représentation en C d’une cellule

En C, une cellule de liste chaînée est représentée par une structure contenant la donnée et un pointeur vers la cellule suivante. Pour ce cours, nous allons stocker des entiers dans les cellules.

// Définition d'une cellule
typedef struct s_cell {
    int value;           // Donnée stockée
    struct s_cell * next;  // Pointeur vers la cellule suivante
} t_cell;

Pourquoi struct s_cell * next et non pas t_cell * next ?

À l’intérieur de la définition de la structure, le type t_cell n’est pas encore complètement défini. On doit donc utiliser struct s_cell * next. Une fois la structure définie avec typedef, on peut utiliser t_cell * dans le reste du code.

3.4 Représentation en C d’une liste chaînée

Pour manipuler une liste, il est suffisant de retenir en mémoire la position mémoire de la première cellule (la tête). Ainsi, on peut définir le type structuré représentant une liste chaînée comme suit :

typedef struct s_list {
    t_cell * head;  // Pointeur vers la tête de la liste
} t_list;

Pourquoi une structure t_list ?

Cela permet de regrouper toutes les informations relatives à la liste (comme la tête) dans une seule structure. Cela facilite la gestion de la liste, surtout si on souhaite ajouter d’autres attributs à l’avenir (comme la taille de la liste).

4 Opérations de base

4.1 Création d’une cellule

La première opération fondamentale est de créer une nouvelle cellule. Voici une fonction qui alloue dynamiquement une cellule et initialise ses champs :

t_cell * create_cell(int value) {
    // Allouer de la mémoire pour une nouvelle cellule
    t_cell * new_cell = (t_cell *) malloc(sizeof(t_cell));
    
    if (new_cell == NULL) {
        printf("Erreur d'allocation mémoire\n");
        exit(1);
    }
    
    // Initialiser la cellule
    new_cell->value = value;
    new_cell->next = NULL;
    
    return new_cell;
}

Important

Gestion de la mémoire :

• On utilise malloc pour allouer dynamiquement la mémoire
• Il faut toujours vérifier que malloc a réussi (retour différent de NULL)
• La mémoire allouée doit être libérée avec free quand elle n’est plus utilisée. À chaque malloc doit correspondre un free.

4.2 Création d’une liste vide

Une liste vide est simplement une liste dont le champ head pointe vers NULL :

Visualisation :

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head[NULL]

    style head fill:#FFE6E6

Implémentation :

t_list create_empty_list() {
    t_list list;
    list.head = NULL;
    return list;
}

// Appel de la fonction
t_list my_list = create_empty_list();

4.3 Insertion en tête

L’insertion en tête d’une liste est l’opération la plus simple. On crée une nouvelle cellule et on la place au début de la liste.

Principe :

1. Créer une nouvelle cellule
2. Faire pointer la nouvelle cellule vers la tête actuelle
3. Mettre à jour la tête pour pointer vers la nouvelle cellule

Visualisation pas à pas : Insérer une cellule de valeur 5 à la tête d’une liste contenant des cellules de valeurs 10, 20, 30.

1. Avant

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head --> A["[10 | @]"] --> B["[20 | @]"] --> C["[30 | NULL]"] 

    style t_list fill:#ecf98f
    style head fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

On veut insérer la valeur 5 au début de la liste list.

2. Créer la nouvelle cellule de valeur 5

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head --> A["[10 | @]"] --> B["[20 | @]"] --> C["[30 | NULL]"] 
    N["[5 | NULL]"]

    style t_list fill:#ecf98f
    style head fill:#FFE6E6
    style N fill:#90EE90
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

On alloue une nouvelle cellule avec create_cell(5) qui est initialement isolée (puisque create_cell initialise next à NULL).

3. Chaîner la nouvelle cellule vers l’actuelle tête (la cellule de valeur 10)

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head --> A["[10 | @]"] --> B["[20 | @]"] --> C["[30 | NULL]"] 
    N["[5 | @]"] --> A

    style t_list fill:#ecf98f
    style head fill:#FFE6E6
    style N fill:#90EE90
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

On ne change pas encore head. Si la nouvelle cellule s’appelle new_cell, on fait new_cell->next = list->head.

4. Après :

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head --> N["[5 | @]"] --> A["[10 | @]"] --> B["[20 | @]"] --> C["[30 | NULL]"]

    style t_list fill:#ecf98f
    style head fill:#FFE6E6
    style N fill:#90EE90
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

On met à jour list->head pour qu’il pointe sur new_cell.

Implémentation :

void insert_at_head(t_list * list, int value) {
    // Créer une nouvelle cellule
    t_cell * new_cell = create_cell(value);
    
    // La nouvelle cellule pointe vers l'ancienne tête
    new_cell->next = list->head;
    
    // Mettre à jour la tête
    list->head = new_cell;
}

Pourquoi t_list * list ?

On passe un pointeur vers la structure t_list car elle contient le pointeur head que nous devons modifier.

Tip

Est-ce que cette fonction reste valide si la liste est initialement vide ?

Exemple d’utilisation :

int main() {
    t_list list = create_empty_list();
    
    insert_at_head(&list, 30);  // Liste : [30 | NULL]
    insert_at_head(&list, 20);  // Liste : [20 | @] -> [30 | NULL]
    insert_at_head(&list, 10);  // Liste : [10 | @] -> [20 | @] -> [30 | NULL]
    
    // On doit par la suite libérer toute la mémoire allouée

    return 0;
}

4.4 Affichage d’une liste

L’affichage d’une liste chaînée illustre le parcours d’une liste et l’application d’une opération à chaque cellule.

Question

Oui mais sans indice, comment on fait pour parcourir la liste ?

Principe :

1. Initialiser un pointeur de cellule cur à la tête de la liste
2. Tant qu’il y a une cellule sur laquelle opérer (cur != NULL) :
   • Traiter la cellule courante (par exemple, afficher sa valeur)
   • Avancer le pointeur : cur = cur->next

Implémentation :

void print_list(t_list * list) {
    t_cell * cur = list->head; // Initialiser le pointeur à la tête
    
    printf("Liste : ");
    while (cur != NULL) { // Tant que cur pointe sur une cellule
        printf("%d -> ", cur->value); // Traiter la cellule courante
        cur = cur->next; // Avancer le pointeur
    }
    printf("NULL\n");
}

Exemple de sortie :

Liste : 10 -> 20 -> 30 -> NULL

4.5 Insertion en fin

Pour insérer un élément en fin de liste, on doit parcourir toute la liste jusqu’à la dernière cellule.

Principe :

1. Si la liste est vide, insérer en tête
2. Sinon, parcourir jusqu’à la dernière cellule (positionner un curseur au niveau de la dernière cellule)
3. Faire pointer la dernière cellule vers la nouvelle cellule

Visualisation pas à pas : Insérer une cellule de valeur 40 à la fin d’une liste contenant des cellules de valeurs 10, 20, 30.

1. État initial

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head --> A["[10 | @]"] --> B["[20 | @]"] --> C["[30 | NULL]"]

    style t_list fill:#ecf98f
    style head fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

On veut insérer une cellule de valeur 40 à la fin de la liste list.

2. Créer la nouvelle cellule de valeur 40

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head --> A["[10 | @]"] --> B["[20 | @]"] --> C["[30 | NULL]"]
    N["[40 | NULL]"]

    style t_list fill:#ecf98f
    style head fill:#FFE6E6
    style N fill:#90EE90
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

On alloue une nouvelle cellule new_cell de valeur 40 avec la fonction create_cell(40). Elle est initialement isolée (puisque create_cell initialise next à NULL).

3. Positionner un pointeur cur à la dernière cellule

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head --> A["[10 | @]"] --> B["[20 | @]"] --> C["[30 | NULL]"]
    N["[40 | NULL]"]
    cur -.-> C

    style t_list fill:#ecf98f
    style head fill:#FFE6E6
    style cur fill:#FFE6E6
    style N fill:#90EE90
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

On parcourt la liste avec un pointeur cur jusqu’à la dernière cellule (celle qui pointe vers NULL).

4. Chaîner la dernière cellule vers la nouvelle cellule

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head --> A["[10 | @]"] --> B["[20 | @]"] --> C["[30 | @]"] --> N["[40 | NULL]"]

    style t_list fill:#ecf98f
    style head fill:#FFE6E6
    style N fill:#90EE90
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

On met à jour cur->next = new_cell afin de faire en sorte que désormais new_cell soit la cellule suivante de la dernière cellule.

Implémentation :

void insert_at_tail(t_list *list, int value) {
    t_cell * new_cell = create_cell(value);
    
    // Cas 1 : Liste vide
    if (list->head == NULL) {
        list->head = new_cell;
        return;
    }
    
    // Cas 2 : Parcourir jusqu'à la dernière cellule
    t_cell * cur = list->head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    
    // Lier la dernière cellule à la nouvelle cellule
    cur->next = new_cell;
}

4.6 Suppression d’un élément

La suppression est plus délicate car il faut gérer plusieurs cas et mettre à jour les pointeurs correctement.

Cas à considérer :

1. La liste est vide
2. L’élément à supprimer est en tête
3. L’élément à supprimer est au milieu ou en fin
4. L’élément n’existe pas

Visualisation pas à pas : Supprimer la cellule de valeur 20 d’une liste contenant des cellules de valeurs 10, 20, 30.

1. Avant

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head --> A["[10 | @]"] --> B["[20 | @]"] --> C["[30 | NULL]"]

    style t_list fill:#ecf98f
    style head fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#FFD1D1
    style C fill:#E6F3FF

On veut supprimer la valeur la cellule 20 de la liste list.

2. Positionner deux pointeurs prev et cur où cur pointe sur la cellule à supprimer et prev sur son prédécesseur.

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head --> A["[10 | @]"] --> B["[20 | @]"] --> C["[30 | NULL]"]
    prev -.-> A
    cur -.-> B

    style t_list fill:#ecf98f
    style head fill:#FFE6E6
    style prev fill:#FFE6E6
    style cur fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#FFD1D1
    style C fill:#E6F3FF

Dans la boucle de parcours, on positionne cur sur la cellule à supprimer (qui est ici de valeur 20) : une condition d’arrêt est cur->value == 20. De plus, on doit maintenir dans prev la cellule précédente : dans la boucle, on fait prev = cur; cur = cur->next;.

3. Mettre à jour le pointeur de prev pour sauter cur

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head --> A["[10 | @]"] --> C["[30 | NULL]"]
    cur -.-> B["[20 | @]"]
    B --> C
    prev -.-> A

    style t_list fill:#ecf98f
    style head fill:#FFE6E6
    style cur fill:#FFE6E6
    style prev fill:#FFE6E6
    style A fill:#E6F3FF
    style C fill:#E6F3FF

On met à jour prev->next = cur->next pour faire en sorte que la cellule précédente pointe vers la cellule suivante de cur, sautant ainsi cur.

4. Isoler cur pour la libérer

---
config:
    look: 'handDrawn'
---
graph LR
    subgraph t_list
        head[head]
    end
    head --> A["[10 | @]"] --> C["[30 | NULL]"]
    cur -.-> B["[20 | NULL]"]
    prev -.-> A

    style t_list fill:#ecf98f
    style head fill:#FFE6E6
    style cur fill:#FFE6E6
    style prev fill:#FFE6E6
    style A fill:#E6F3FF
    style C fill:#E6F3FF

Il reste ensuite à mettre à jour cur->next = NULL afin de l’isoler et à libérer la mémoire avec free(cur).

Implémentation :

void delete_cell(t_list *list, int value) {
    // Cas 1 : Liste vide
    if (list->head == NULL) {
        printf("Liste vide, rien à supprimer\n");
        return;
    }
    
    // Cas 2 : L'élément à supprimer est en tête
    if (list->head->value == value) {
        t_cell *temp = list->head;
        list->head = list->head->next;
        free(temp);
        return;
    }
    
    // Cas 3 : L'élément est au milieu ou en fin
    t_cell *cur = list->head;
    t_cell *prev = NULL;
    
    while (cur != NULL && cur->value != value) {
        prev = cur;
        cur = cur->next;
    }
    
    // Élément non trouvé
    if (cur == NULL) {
        printf("Élément %d non trouvé\n", value);
        return;
    }
    
    // Supprimer la cellule
    prev->next = cur->next;
    cur->next = NULL;
    free(cur);
}

Dans certains cas, on pourrait vouloir retirer un élément sans libérer la mémoire (par exemple, pour le réutiliser ailleurs). Dans ce cas, on omet simplement l’appel à free(cur) dans la fonction de suppression et à la place on retourne un pointeur vers la cellule supprimée.

Dans ce cas là que retourne-t-on si l’élément n’est pas trouvé ?

4.7 Libération de toute la liste

Quand on n’a plus besoin d’une liste, il faut libérer toutes les cellules :

void free_list(t_list *list) {
    t_cell *cur = list->head;
    t_cell *next;
    
    while (cur != NULL) {
        next = cur->next;  // Sauvegarder le pointeur suivant
        free(cur);         // Libérer la cellule courante
        cur = next;        // Avancer
    }
    
    list->head = NULL;  // Mettre la tête à NULL
}

Note

Pourquoi sauvegarder cur->next avant de libérer ?

Une fois qu’on a appelé free(cur), on ne peut plus accéder à cur->next. Il faut donc sauvegarder cette valeur avant de libérer la cellule.

5 Comparaison : Tableaux vs Listes chaînées

Opération	Tableau	Liste chaînée
Accès à un élément	Direct via l’indice	Nécessite un parcours
Insertion en tête	Décalage nécessaire (vers la droite)	Simple modification de pointeurs
Insertion en fin	Si espace disponible	Parcours jusqu’à la fin
Suppression	Décalage nécessaire	Recherche nécessaire
Taille	Fixe	Dynamique
Mémoire	Contigu, peut gaspiller	Virtuellement illimité

Important

Quand utiliser une liste chaînée ?

Les listes chaînées sont particulièrement adaptées quand :

• On fait beaucoup d’insertions/suppressions en début de liste
• La taille des données est imprévisible
• On n’a pas besoin d’accès direct par indice

Quand préférer un tableau ?

Les tableaux sont meilleurs quand :

• On accède fréquemment aux éléments par leur position
• La taille est connue à l’avance ou change peu
• On veut minimiser l’utilisation mémoire (pas de pointeurs)

6 Pièges courants et bonnes pratiques

6.1 Perte de la tête de liste

// ❌ ERREUR : Perte de la tête (si on passait une copie)
void wrong_function(t_list list) {
    t_cell * new_cell = create_cell(5);
    list.head = new_cell;  // Cette modification ne sera pas visible à l'extérieur !
}

// ✅ CORRECT : Passer un pointeur vers la structure
void correct_function(t_list * list) {
    t_cell *new_cell = create_cell(5);
    list->head = new_cell;  // Modification visible à l'extérieur
}

6.2 Oublier de libérer la mémoire

// ❌ ERREUR : Fuite mémoire
void delete_wrong(t_list * list) {
    list->head = list->head->next;  // On perd l'accès à la première cellule !
}

// ✅ CORRECT : Libérer la mémoire
void delete_correct(t_list * list) {
    t_cell *temp = list->head;
    list->head = list->head->next;
    free(temp);  // Libération de la mémoire
}

6.3 Accès à un pointeur NULL

// ❌ ERREUR : Segmentation fault si head est NULL
void unsafe_function(t_list * list) {
    printf("%d\n", list->head->value);  // Crash si head == NULL
}

// ✅ CORRECT : Vérifier avant d'accéder
void safe_function(t_list * list) {
    if (list->head != NULL) {
        printf("%d\n", list->head->value);
    }
}

Bonnes pratiques :

1. Toujours vérifier si un pointeur est NULL avant de le déréférencer
2. Toujours libérer la mémoire allouée avec malloc
3. Utiliser des noms explicites : head, cur, next, prev
4. Dessiner des schémas pour comprendre les modifications de pointeurs
5. Tester les cas limites : liste vide, un seul élément, suppression du dernier élément