Listes chaînées

XTI102 - Structures de Données Avancées

Rado Rakotonarivo – EFREI Paris

Objectifs du chapitre

  • 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
  • Choisir entre tableaux et listes chaînées selon le contexte

Introduction

Pourquoi les structures de données ?

  • Organiser et stocker efficacement les informations en mémoire
  • Impact direct sur la performance et la scalabilité
  • Exemples : moteurs de recherche, messagerie, etc.

Exemple

  • Les moteurs de recherche doivent indexer et rechercher rapidement des milliards de pages web.
  • Les applications de messagerie gèrent des listes dynamiques de contacts et de messages.

Pourquoi les structures de données ?

  • Organiser et stocker efficacement les informations en mémoire
  • Impact direct sur la performance et la scalabilité
  • Exemples : moteurs de recherche, messagerie, etc.

Note

Le choix d’une structure de données dépend des opérations les plus fréquentes.

Limites des tableaux

  • Taille fixe : définie à l’allocation
  • Redimensionnement coûteux : nécessite copie
  • Insertion/suppression coûteuse : décalage nécessaire
  • Gaspillage de mémoire : espace non utilisé

Tip

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

Concept de liste chaînée

De la cellule à la liste

  • Séquence de cellules (nœuds)
  • Chaque cellule contient la donnée (la valeur stockée) et pointeur vers la suivante (la position en mémoire)
  • La liste est identifiée par un pointeur vers la première cellule (la tête)

Comment stocker deux informations dans une même variable ?

Afin de stocker à la fois une donnée et un pointeur vers la cellule suivante, on utilise une structure en C.

Visualisation

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

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

En quoi est-ce différent d’un tableau ?

Dans un tableau, les éléments sont contigus. Dans une liste, les cellules sont dispersées en mémoire.

Implémentation en C

Cellule

typedef struct s_cell {
    int value;
    struct s_cell * next;
} t_cell;

Liste

typedef struct s_list {
    t_cell * head;
} t_list;

Remarques

  • On utilise explicitement struct s_cell * next car le type t_cell n’est pas encore complètement défini.
  • On choisit délibérément de définir un type structuré pour la liste même si elle ne contient qu’un seul champ car plus tard on pourrait vouloir ajouter des informations supplémentaires.

Opérations de base

Création d’une cellule

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));
    
    // Initialiser la cellule
    new_cell->value = value;
    new_cell->next = NULL;
    
    return new_cell;
}

Création d’une liste vide

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

    style head fill:#FFE6E6


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

Insertion en tête

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 qu’elle pointe vers la nouvelle cellule

Visualisation

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


t_list l;
// Initialisation de la liste avec les valeurs 10, 20, 30

Visualisation

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


// Création de la nouvelle cellule avec la valeur 5
t_cell * new_cell = create_cell(5);

Visualisation

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


t_list l;
// Faire pointer la nouvelle cellule vers l'ancienne tête
new_cell->next = l.head;

Visualisation

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


// Mettre à jour la tête de la liste
l.head = new_cell;

Fonction complète

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.

Fonction complète

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;
}

Question

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]
    
    // Suite du programme...

    return 0;
}

Parcours d’une liste

Comment parcourrir une liste chaînées si on n’a pas de système d’indice comme dans un tableau ?

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

Visualisation

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

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


t_cell * cur = list.head;
// puis opérations sur cur

Visualisation

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

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


cur = cur->next;
// puis opérations sur cur

Visualisation

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

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


cur = cur->next;
// puis opérations sur cur

Visualisation

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

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


cur = cur->next;
// plus d'opérations car cur == NULL

Fonction complète pour un affichage

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");
}

Cette fonction affichera :

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

Insertion en fin

Principe

  1. Créer une nouvelle cellule
  2. Parcourir la liste jusqu’à la dernière cellule
  3. Faire pointer la dernière cellule vers la nouvelle cellule
  4. Si la liste est vide, mettre à jour la tête pour qu’elle pointe vers la nouvelle cellule

Visualisation

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


t_list l;
// Liste initiale avec les valeurs 10, 20, 30

Visualisation

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


// Création de la nouvelle cellule avec la valeur 40
t_cell * new_cell = create_cell(40);

Visualisation

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


// Parcourir jusqu'à la dernière cellule
t_cell * cur = l.head;
while (cur->next != NULL) cur = cur->next;

Visualisation

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


// Chaîner la nouvelle cellule à la fin
cur->next = new_cell;

Fonction complète

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;
}

Suppression d’un élément

Principe

Il existe plusieurs cas à gérer lors de la suppression d’une cellule contenant une valeur donnée :

  1. La liste est vide : rien à faire
  2. La cellule à supprimer est la tête : mettre à jour la tête
  3. La cellule à supprimer est au milieu ou à la fin : parcourir la liste pour trouver la cellule précédente et mettre à jour son pointeur next
  4. La cellule n’est pas trouvée : rien à faire

Visualisation

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


t_list l;
// Supprimer la cellule contenant 20

Visualisation

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


// Parcourir jusqu'à trouver la valeur
t_cell *cur = l.head, *prev = NULL;
while (cur != NULL && cur->value != 20) {
    prev = cur; 
    cur = cur->next;
}

Visualisation

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


// Retirer cur de la chaîne
prev->next = cur->next;

Visualisation

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


// Isoler et libérer la cellule
cur->next = NULL;
free(cur);

Fonction complète

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);
}

Retirer une cellule au lieu de la supprimer

  • Selon le contexte, on peut vouloir retirer une cellule d’une liste sans la supprimer de la mémoire.
  • Cela permet de réutiliser la cellule ailleurs ou de la conserver pour un usage futur.

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

On peut retourner NULL pour indiquer que l’élément n’a pas été trouvé dans la liste.

Libération de la mémoire

Principe

  1. Initialiser un pointeur cur à la tête de la liste
  2. Tant que cur n’est pas NULL :
    • Stocker la cellule courante dans un pointeur temporaire temp
    • Avancer cur vers la cellule suivante
    • Libérer la mémoire de la cellule pointée par temp
  • Enfin, mettre la tête de la liste à NULL pour indiquer qu’elle est vide

Fonction complète

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
}

Conclusion

Points clés

  • Listes chaînées = structure dynamique
  • Insertion/suppression efficaces en tête
  • Insertion en fin nécessite un parcours
  • Toujours libérer la mémoire allouée

Comparaison tableaux vs listes

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é

Pièges courants et bonnes pratiques

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
}

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
}

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

Questions ?

Merci pour votre attention !