Listes chaînées avancées

XTI102 - Structures de Données Avancées

Rado Rakotonarivo – EFREI Paris

Objectifs du chapitre

  • Maîtriser la variante head-tail des listes chaînées
  • Comprendre les principes des listes circulaires
  • Comprendre la structure et les usages des listes doublement chaînées
  • Choisir la variante adaptée selon les opérations dominantes

Introduction

Variantes de listes chaînées

  • Head-tail : deux pointeurs (tête et queue)
  • Circulaire : dernière cellule pointe vers la tête
  • Doublement chaînée : pointeurs bidirectionnels

Tip

Chaque variante optimise certaines opérations en échange d’une complexité accrue.

Liste head-tail

Concept

  • Deux pointeurs : head (tête) et tail (queue)
  • Avantage : insertion en fin en temps constant

Note

Permet d’insérer en fin 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
    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

Structure en C

typedef struct s_ht_list {
    t_cell * head;
    t_cell * tail;
} t_ht_list;

Tip

Seule la structure change, les cellules restent identiques.

Insertion en tête

Visualisation

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


t_ht_list l;
// Liste initiale avec head et tail

Visualisation

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


// Créer nouvelle cellule
t_cell *n = create_cell(5);

Visualisation

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


// Chaîner vers l'ancienne tête
n->next = l.head;

Visualisation

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


// Mettre à jour head
l.head = n;

Code

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

Insertion en fin

Visualisation

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


t_ht_list l;
// Liste avec head et tail

Visualisation

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


// Créer nouvelle cellule
t_cell *n = create_cell(40);

Visualisation

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


// Chaîner depuis tail
l.tail->next = n;

Visualisation

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


// Mettre à jour tail
l.tail = n;

Code

void ht_insert_tail(t_ht_list *list, int value) {
    t_cell *n = create_cell(value);
    if (list->tail == NULL) {
        list->head = n;
        list->tail = n;
        return;
    }
    list->tail->next = n;
    list->tail = n;
}

Suppression en tête

Visualisation

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


t_ht_list l;
// Supprimer la tête

Visualisation

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


// Marquer la cellule à supprimer
t_cell *tmp = l.head;

Visualisation

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


// Mettre à jour head
l.head = l.head->next;

Visualisation

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


// Libérer tmp
free(tmp);

Code

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;
    }
    free(tmp);
}

Suppression en fin

Limite de la variante

  • Nécessite de parcourir jusqu’à l’avant-dernière cellule
  • Pas d’optimisation par rapport à la liste simple

Visualisation

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


t_ht_list l;
// Supprimer la fin

Visualisation

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


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

Visualisation

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


// Libérer tail et couper le lien
free(l.tail);
cur->next = NULL;

Visualisation

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


// Mettre à jour tail
l.tail = cur;

Code

void ht_delete_tail(t_ht_list *list) {
    if (list->head == list->tail) {
        free(list->tail);
        list->head = list->tail = NULL;
    } else {
        t_cell * cur = list->head;
        while (cur->next != list->tail) 
            cur = cur->next;
        free(list->tail);
        cur->next = NULL;
        list->tail = cur;
    }
}

Liste circulaire

Concept

  • Dernière cellule pointe vers la tête
  • Parcours infini possible
  • Utile pour : buffers circulaires, ordonnancement

Visualisation

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

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

Parcours

  • Condition d’arrêt différente : cur != head après le premier tour
  • Pas de NULL pour marquer la fin

Liste doublement chaînée

Concept

  • Chaque cellule : deux pointeurs (next et prev)
  • Parcours dans les deux sens
  • Suppression en fin optimisée

Question

À votre avis, pourquoi la suppression en fin est-elle optimisée ?

Visualisation

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

Structure en C

typedef struct s_dcell {
    int value;
    struct s_dcell * next;
    struct s_dcell * prev;
} t_dcell;

typedef struct s_dlist {
    t_dcell * head;
} t_dlist;

Comparaison à une liste simple

Caractéristiques Liste simplement chaînée Liste doublement chaînée
Cellules 1 pointeur (next) 2 pointeurs (next, prev)
Première cellule Stockée dans head Stockée dans head + champ prev == NULL
Dernière cellule champ next == NULL champ next == NULL
Parcours Dans un sens Dans les deux sens
Suppression (sauf en tête) Nécessite deux curseurs Un seul curseur car la cellule précédente est accessible via prev

Conclusion

Comparaison des variantes

Opération Simple Head-tail Circulaire Doublement chaînée
Insertion en tête ✅ ✅ ✅ ✅
Insertion en fin ⚠️ ✅ ✅ ⚠️
Suppression en tête ✅ ✅ ✅ ✅
Suppression en fin ⚠️ ⚠️ ⚠️ ⚠️ (mais un seul curseur)

Performance des opérations

  • ✅ : Opération ne nécessitant pas de parcours (efficace)
  • ⚠️ : Opération nécessitant un parcours (lent si longue liste)

Choix de la variante

Tip

  • Head-tail : insertions fréquentes en fin
  • Circulaire : parcours répétés, buffers
  • Doublement chaînée : suppressions en fin, navigation bidirectionnelle

Questions ?

Merci pour votre attention !