Listes chaînées avancées

Variantes de listes chaînées : head-tail, circulaires, doublement chaînées.

Objectifs

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

  • Maîtriser la variante head-tail des listes chaînées et ses opérations de base
  • Comprendre les principes des listes circulaires (parcours et insertion en tête)
  • Comprendre la structure et les usages des listes doublement chaînées
  • Choisir la variante adaptée selon les opérations dominantes

1 Introduction

Au-delà de la liste simplement chaînée avec un seul pointeur head, certaines variantes optimisent des opérations spécifiques. Nous nous concentrons ici sur trois variantes utiles en pratique :

  • liste head-tail (vue détaillée)
  • liste circulaire (aperçu)
  • liste doublement chaînée (aperçu).

Chaque variante apporte des gains ciblés (temps constant, parcours, simplicité) en échange d’un coût (pointeurs supplémentaires, code plus délicat). Le bon choix dépend des opérations les plus fréquentes.

2 Liste head-tail

2.1 Concept

La variante head-tail maintient deux pointeurs :

  • head vers la première cellule
  • tail vers la dernière cellule
Pourquoi un pointeur tail ?

Permettre l’insertion en fin de liste sans parcourir toute la liste.

Visualisation :

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

    style t_ht_list fill:#ecf98f
    style tail fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

2.2 Représentation en C

Seule la structure de la liste change, les cellules restent identiques. Toutes les fonctions manipulant des cellules restent valides.

// Définition d'une liste head-tail
typedef struct s_ht_list {
    t_cell * head;            // Pointeur vers la tête
    t_cell * tail;            // Pointeur vers la queue
} t_ht_list;

3 Opérations de base pour une liste head-tail

3.1 Insertion en tête

On souhaite par exemple une nouvelle cellule avec la valeur 5 en tête de la liste.

  1. Avant

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

    style t_ht_list fill:#ecf98f
    style head fill:#FFE6E6
    style tail fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

On suppose qu’on ait une t_ht_list list dans l’état ci-contre dans laquel on veut insérer la valeur 5 en tête.

  1. Étape 1 : création de la nouvelle cellule de valeur 5

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

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

La première étape est de créer la nouvelle cellule N contenant la valeur 5 avec la fonction create_cell().

  1. Étape 2 : chaîner la nouvelle cellule avec l’actuelle tête de liste

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

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

Ensuite, on fait en sorte que cette nouvelle cellule ait comme next la tête actuelle.

  1. Après : Mettre à jour la tête de liste pour pointer sur la nouvelle cellule

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

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

On met à jour le pointeur head pour qu’il pointe sur la nouvelle cellule N.

Il faudrait également vérifier si la liste était initialement vide. Dans ce cas, il faut aussi mettre à jour tail pour qu’il pointe sur la nouvelle cellule.

Code complet :

// Insertion en tête 
void ht_insert_head(t_ht_list *list, int value) {
    t_cell *n = create_cell(value);
    n->next = list->head;
    list->head = n;
    if (list->tail == NULL) {
        list->tail = n;  // Cas liste initialement vide
    }
}

3.2 Insertion en fin

On souhaite désormais insérer une nouvelle cellule avec la valeur 40 en fin d’une liste head-tail.

  1. Avant

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

    style t_ht_list fill:#ecf98f
    style head fill:#FFE6E6
    style tail fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

On suppose qu’on ait une t_ht_list list dans l’état ci-contre dans laquel on veut insérer la valeur 40 en fin.

  1. Étape 1 : création de la nouvelle cellule N=40 (isolée)

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

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

La première étape est de créer la nouvelle cellule N contenant la valeur 40 avec la fonction create_cell().

  1. Étape 2 : chaîner la dernière cellule avec la nouvelle cellule

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

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

Ensuite, on fait en sorte que l’actuelle tail pointe vers cette nouvelle cellule.

  1. Après : Mettre à jour la queue de liste pour pointer sur la nouvelle cellule

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

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

On met à jour le pointeur tail pour qu’il pointe sur la nouvelle cellule N.

Il faudrait également vérifier si la liste était initialement vide. Dans ce cas, il faut aussi mettre à jour head pour qu’il pointe sur la nouvelle cellule.

Code complet :

// Insertion en fin 
void ht_insert_tail(t_ht_list *list, int value) {
    t_cell *n = create_cell(value);
    if (list->tail == NULL) {
        // Liste vide : head et tail pointent vers n
        list->head = n;
        list->tail = n;
        return;
    }
    list->tail->next = n;
    list->tail = n;
}

3.3 Suppression en tête

Voyons par la suite comment supprimer la tête d’une liste head-tail.

  1. Avant

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

    style t_ht_list fill:#ecf98f
    style head fill:#FFE6E6
    style tail fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

On suppose qu’on ait une t_ht_list list dans l’état ci-contre dans laquel on veut supprimer la tête.

  1. Étape 1 : Marquer la cellule à supprimer (ici c’est celle pointée par head)

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

    style t_ht_list fill:#ecf98f
    style head fill:#FFE6E6
    style tail fill:#FFE6E6
    style A fill:#FFD1D1
    style B fill:#E6F3FF
    style C fill:#E6F3FF
    style tmp fill:#FFE6E6

La première étape est de sauvegarder la tête actuelle dans un pointeur temporaire tmp pour pouvoir la libérer plus tard.

  1. Étape 2 : Mettre à jour le pointeur head

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

    style t_ht_list fill:#ecf98f
    style head fill:#FFE6E6
    style tail fill:#FFE6E6
    style A fill:#FFD1D1
    style B fill:#E6F3FF
    style C fill:#E6F3FF
    style tmp fill:#FFE6E6

On met à jour head pour qu’il pointe sur la cellule suivante de l’ancienne tête.

  1. Après : Libérer la cellule

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

    style t_ht_list fill:#ecf98f
    style head fill:#FFE6E6
    style tail fill:#FFE6E6
    style B fill:#E6F3FF
    style C fill:#E6F3FF

Enfin, on libère la mémoire de l’ancienne tête stockée dans tmp.

Il faudrait également vérifier si la liste devient vide après la suppression. Dans ce cas, il faut aussi mettre à jour tail pour qu’il soit NULL.

Il est tout à fait possible de retourner l’élément retiré au lieu de le libérer directement.

Code complet :

// Suppression en tête 
void ht_delete_head(t_ht_list *list) {
    if (list->head == NULL) return;
    t_cell *tmp = list->head;
    list->head = list->head->next;
    if (list->head == NULL) {
        list->tail = NULL; // Liste devenue vide
    }
    free(tmp);
}

3.4 Suppression en fin — limite de la variante

On souhaite supprimer la dernière cellule d’une liste head-tail. Cette opération est moins efficace que l’insertion en fin car elle nécessite de parcourir la liste pour trouver l’avant-dernière cellule.

  1. Avant

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

    style t_ht_list fill:#ecf98f
    style head fill:#FFE6E6
    style tail fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

On suppose qu’on ait une t_ht_list list dans l’état ci-contre dans laquel on veut supprimer la queue.

  1. Étape 1 : parcourir jusqu’à l’avant-dernière cellule (cur)

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

    style t_ht_list fill:#ecf98f
    style head fill:#FFE6E6
    style tail fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#FFD1D1
    style cur fill:#FFE6E6

On parcourt la liste pour trouver l’avant-dernière cellule, que l’on stocke dans cur.

  1. Étape 2 : libérer tail et couper le lien entre cur et l’ancienne queue

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

    style t_ht_list fill:#ecf98f
    style head fill:#FFE6E6
    style tail fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style cur fill:#FFE6E6

On libère la mémoire de l’ancienne queue et on coupe le lien en mettant cur->next = NULL.

  1. Après : Mettre à jour la queue de liste pour pointer sur cur

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

    style t_ht_list fill:#ecf98f
    style head fill:#FFE6E6
    style tail fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style cur fill:#FFE6E6

On met à jour tail pour qu’il pointe sur cur.

Pour savoir si la liste devient vide après la suppression, il faut vérifier si head == tail avant la suppression. Dans ce cas, il faut mettre à jour head et tail à NULL.

Code complet :

// Suppression en fin 
void ht_delete_tail(t_ht_list *list) {
    if (list->tail == NULL) return;          // Liste vide
    if (list->head == list->tail) {          // Un seul élément
        free(list->head);
        list->head = NULL;
        list->tail = NULL;
        return;
    }
    t_cell *cur = list->head;
    while (cur->next != list->tail) {
        cur = cur->next;
    }
    // cur est l'avant-dernier
    free(list->tail);
    cur->next = NULL;
    list->tail = cur;
}
Note

Head-tail optimise l’insertion en fin, mais pas la suppression en fin. Si vous supprimez souvent en fin, une liste doublement chaînée sera plus adaptée.

4 Liste circulaire

4.1 Concept et représentation

On peut représenter une liste circulaire en utilisant une liste t_ht_list où la dernière cellule pointe vers la première au lieu de NULL.

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

    style t_circ_list fill:#ecf98f
    style head fill:#FFE6E6
    style tail fill:#FFE6E6
    style A fill:#E6F3FF
    style B fill:#E6F3FF
    style C fill:#E6F3FF

Il suffit dans ce cas de redéfinir le type de liste afin d’indiquer qu’il s’agit d’une liste circulaire.

// On réutilise le type t_ht_list
typedef t_ht_list t_circ_list;
Tip

Lors du parcours d’une liste circulaire list que l’on suppose non vide, la condition d’arrêt cur == NULL devient pour la plupart des cas cur->next == list->head.

5 Liste doublement chaînée

5.1 Représentation et visuel

// Définition d'une cellule doublement chaînée
typedef struct s_dcell {
    int value;
    struct s_dcell * next;
    struct s_dcell * prev;
} t_dcell;

// Définition d'une liste doublement chaînée
typedef struct s_dlist {
    t_dcell * head;
} t_dlist;

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

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

5.2 Points clés

  • Parcours dans les deux sens grâce à prev
  • Suppression locale plus simple si on connaît la cellule
  • Coût mémoire plus élevé (deux pointeurs par cellule)
// Insertion en tête d'une liste doublement chaînée
void dlist_insert_head(t_dlist *list, int value) {
    t_dcell *n = (t_dcell*) malloc(sizeof(t_dcell));
    if (n == NULL) {
        printf("Erreur d'allocation mémoire\n");
        exit(1);
    }
    n->value = value;
    n->prev = NULL;
    n->next = list->head;
    if (list->head != NULL) {
        list->head->prev = n;
    }
    list->head = n;
}

6 En résumé

Le choix de la variante de liste chaînée dépend des opérations dominantes :

Opérations dominantes Variante recommandée
Beaucoup d’insertions en fin uniquement head-tail
Parcours cycliques circulaire
Suppressions locales fréquentes, parcours bi-directionnel doublement chaînée