Structures de données, IMA S6 - Listes chaînées

Ce cours aborde les listes chaînées, une structure de données fondamentale en informatique, dans le cadre d'un enseignement de structures de données. Il s'inscrit dans la continuité de l'étude des tableaux contigus et présente les avantages, la structure, les opérations et les erreurs courantes liées aux listes chaînées.

Introduction aux listes chaînées

Les listes chaînées sont une alternative aux listes contiguës (tableaux) pour représenter des séquences d'éléments. Contrairement aux tableaux, les listes chaînées permettent une gestion dynamique de la mémoire, allouée cellule par cellule, sans nécessiter une zone mémoire contiguë.

Dans un tableau contigu, l'insertion ou la recherche peut être coûteuse, surtout lorsque le tableau est plein et nécessite une réallocation. La liste chaînée offre une solution en allouant dynamiquement chaque élément, ce qui facilite les insertions et suppressions sans déplacement massif des données.

Les notations algorithmiques utilisées dans ce cours incluent les pointeurs (p), la valeur pointée (p ↑), ainsi que les fonctions d'allocation et de libération mémoire : allouer() pour obtenir une nouvelle cellule et liberer(P) pour libérer la mémoire pointée par P.

Structure des listes simplement chaînées

Une liste est une séquence ordonnée d'éléments du même type, où l'ordre et la multiplicité des éléments comptent. Par exemple, la liste d'entiers (12, 43, 27, 9) est différente de (12, 27, 43, 9) ou de (12, 43, 27, 9, 9).

La liste simplement chaînée est représentée par des cellules où chaque cellule contient une valeur et un pointeur vers la cellule suivante. La dernière cellule pointe vers NULL, indiquant la fin de la liste.

En C, une cellule de liste d'entiers peut être définie ainsi :

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

La liste est représentée par un pointeur head vers la première cellule. Si la liste est vide, head vaut NULL.

Opérations fondamentales sur les listes chaînées

Calcul de la longueur d'une liste

Pour calculer la longueur d'une liste, on parcourt les cellules en suivant les pointeurs next jusqu'à rencontrer NULL, en comptant le nombre de cellules rencontrées.

Recherche d'un élément

La recherche consiste à parcourir la liste jusqu'à trouver un élément égal à la valeur recherchée ou jusqu'à la fin de la liste. La fonction renvoie true si l'élément est trouvé, false sinon.

Gestion de la mémoire dynamique

Les cellules sont allouées dynamiquement avec malloc et libérées avec free. Par exemple, pour allouer un tableau de 50 entiers :

int* tab = (int*) malloc(50 * sizeof(int));

Création d'une liste

Une méthode peu pratique consiste à allouer manuellement chaque cellule et à les chaîner. Par exemple, pour créer la liste (12, 43, 27, 9) :

Cell* head;
head = (Cell*) malloc(sizeof(Cell));
head->data = 12;
head->next = malloc(sizeof(Cell));
head->next->data = 43;
head->next->next = malloc(sizeof(Cell));
head->next->next->data = 27;
head->next->next->next = malloc(sizeof(Cell));
head->next->next->next->data = 9;
head->next->next->next->next = NULL;

On préfère construire une liste par insertions successives, plus modulaires et sûres.

Insertion en tête de liste

L'insertion en tête consiste à créer une nouvelle cellule et à la faire pointer vers l'ancienne tête. Par exemple :

Cell* head = NULL;
head = insere(head, 9);
head = insere(head, 27);
head = insere(head, 43);
head = insere(head, 12);

La liste résultante est dans l'ordre inverse des insertions : (12, 43, 27, 9).

Remarques :

• L'insertion en tête est possible sur une liste vide ou non vide.
• La tête de liste est modifiée à chaque insertion.
• Le coût d'une insertion en tête est constant, O(1).

Insertion en queue de liste

Deux cas se présentent :

• Si la liste est vide, la tête pointe vers la nouvelle cellule.
• Si la liste est non vide, on fait pointer le champ next de la dernière cellule vers la nouvelle cellule.

Exemple d'insertion en queue :

Cell* head = NULL;
head = insere(head, 12);
head = insere(head, 43);
head = insere(head, 27);
head = insere(head, 9);

La liste est dans le même ordre que les insertions : (12, 43, 27, 9).

Remarques :

• La tête de liste n'est modifiée que lors de la première insertion.
• Le coût d'une insertion en queue est linéaire, O(n), car il faut parcourir la liste pour atteindre la dernière cellule.

Coût de construction d'une liste

Pour construire une liste de n éléments :

• Par ajout en tête : coût O(n), mais la liste est dans l'ordre inverse des insertions.
• Par ajout en queue : coût O(n²) à cause de la recherche répétée de la fin de liste.

Insertion après un élément donné

On peut insérer un élément après une cellule donnée, en utilisant un pointeur vers cette cellule (appelée pred). L'insertion est alors de coût constant, hors le calcul de pred qui peut être obtenu par une recherche.

On suppose que l'insertion ne se fait pas en première position (la liste n'est pas vide).

L'insertion avant une cellule donnée est plus complexe à réaliser.

Suppression d'un élément

La suppression d'une cellule se fait à l'aide d'un pointeur vers la cellule précédente (pred), en modifiant le pointeur next de pred pour sauter la cellule à supprimer.

Remarques :

• Le coût est constant, hors recherche de pred.
• On suppose que la suppression ne concerne pas la première cellule.
• On suppose que pred a un suivant (la cellule à supprimer).

Une version complète supprime le premier élément égal à une valeur donnée, gère les cas limites (liste vide, un seul élément, suppression en tête ou en fin), et peut modifier la tête de liste. Le coût est linéaire dans le pire cas, à cause de la recherche.

Concaténation de listes

La concaténation consiste à joindre deux listes en faisant pointer la dernière cellule de la première liste vers la tête de la seconde. Cette opération est étudiée en travaux dirigés.

Destruction totale d'une liste

La destruction libère toutes les cellules de la liste en parcourant la liste et en appelant free sur chaque cellule :

void detruit(Cell* head) {
    Cell* c;
    while (head) {
        c = head->next;
        free(head);
        head = c;
    }
}

Le coût est linéaire en fonction du nombre d'éléments.

Divers sur les listes chaînées

Erreurs courantes

• Déréférencer un pointeur NULL.
• Utiliser un bloc mémoire après l'avoir libéré.
• Libérer deux fois le même bloc.
• Oublier de libérer un bloc, causant des fuites mémoire.
• Introduction de cycles dans la liste, provoquant des boucles infinies lors des parcours et des fuites mémoire.
• Partage de cellules entre plusieurs listes, entraînant des effets de bord et des libérations multiples.
• Oublier de gérer les cas limites : liste vide, liste à un seul élément, insertion ou suppression en première ou dernière position.

Comparaison entre listes chaînées et tableaux

Opération	Liste chaînée	Tableau contigu
Recherche d'une valeur	O(n)	O(n)
Accès par indice	O(n)	O(1)
Insertion en tête	O(1)	O(n)
Insertion en queue	O(n)	O(n)
Insertion au milieu	O(1) si cellule précédente connue, sinon O(n)	O(n)
Recherche si trié	O(n)	O(log n)
Insertion à un indice p si trié	O(n)	O(n) (décalages)

Les listes chaînées sont particulièrement efficaces pour l'insertion et la suppression en tête et au milieu de liste, lorsque la cellule précédente est connue.

Points clés

• Les listes chaînées permettent une gestion dynamique de la mémoire, cellule par cellule, sans zone contiguë.
• Chaque cellule contient une valeur et un pointeur vers la cellule suivante, la fin étant indiquée par NULL.
• Les opérations principales sont le calcul de longueur, la recherche, l'insertion (en tête, en queue, après un élément), la suppression, la concaténation et la destruction.
• L'insertion en tête est rapide (coût constant), tandis que l'insertion en queue est plus coûteuse (coût linéaire).
• La suppression et l'insertion après un élément donné sont efficaces si le pointeur vers la cellule précédente est connu.
• Les erreurs fréquentes incluent la mauvaise gestion des pointeurs, la mémoire dynamique, les cycles et les cas limites.
• Comparées aux tableaux, les listes chaînées sont plus adaptées aux insertions et suppressions fréquentes, mais moins efficaces pour l'accès direct par indice.