La liste doublement chaînée (doubly linked list) est une structure de données linéaire où chaque élément, appelé nœud, contient des références vers son successeur et son prédécesseur. Contrairement à une liste simple, la variante la plus robuste et la plus utilisée en pratique est la liste doublement chaînée circulaire avec nœud sentinelle.

1. Structure et Concept

Dans une liste doublement chaînée circulaire, le "dernier" nœud pointe vers le "premier" (la sentinelle) et vice versa. La sentinelle est un nœud spécial qui ne contient pas de données utiles mais sert de point d'ancrage constant, simplifiant ainsi les opérations d'insertion et de suppression en évitant de traiter les cas particuliers des listes vides.

typedef int DataVal;

typedef struct NodeDL {
    DataVal value;
    struct NodeDL* prev;
    struct NodeDL* next;
} NodeDL;

2. Initialisasion et Création de Nœuds

Pour démarrer une liste, nous devons allouer un nœud sentinelle. À l'état initial (liste vide), les pointeurs next et prev de la sentinelle pointent sur elle-même.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// Allocation d'un nouveau nœud
NodeDL* createNode(DataVal x) {
    NodeDL* newNode = (NodeDL*)malloc(sizeof(NodeDL));
    if (!newNode) {
        perror("Échec malloc");
        exit(-1);
    }
    newNode->value = x;
    newNode->next = newNode;
    newNode->prev = newNode;
    return newNode;
}

// Initialisation de la liste avec sentinelle
NodeDL* initList() {
    // La valeur de la sentinelle est arbitraire
    NodeDL* sentinel = createNode(-1);
    return sentinel;
}

3. Opérations d'Insertion

L'avantage majeur de cette structure est que l'insertion en tête ou en queue s'effectue avec la même logique grâce à la circularité.

Insertion en Queue (Append)

Ajouter un élément à la fin revient à l'insérer juste avant la sentinelle (sentinel->prev).

void appendNode(NodeDL* sentinel, DataVal x) {
    assert(sentinel);
    NodeDL* newNode = createNode(x);
    NodeDL* last = sentinel->prev;

    // Liaison du nouveau nœud avec l'ancien dernier et la sentinelle
    newNode->prev = last;
    newNode->next = sentinel;

    last->next = newNode;
    sentinel->prev = newNode;
}

Insertion en Tête (Prepend)

L'insertion en tête place le nouveau nœud entre la sentinelle et l'ancien premier nœud.

void prependNode(NodeDL* sentinel, DataVal x) {
    assert(sentinel);
    NodeDL* newNode = createNode(x);
    NodeDL* first = sentinel->next;

    newNode->next = first;
    newNode->prev = sentinel;

    first->prev = newNode;
    sentinel->next = newNode;
}

4. Suppression et Recherche

La suppression nécessite de vérifier que la liste n'est pas vide (c'est-à-dire qu'il reste plus que la sentinelle).

Suppression en Queue

void removeTail(NodeDL* sentinel) {
    assert(sentinel && sentinel->next != sentinel);
    
    NodeDL* target = sentinel->prev;
    NodeDL* newLast = target->prev;

    newLast->next = sentinel;
    sentinel->prev = newLast;

    free(target);
}

Recherche d'un Élément

On parcourt la liste en partant de sentinel->next jusqu'à revenir à la sentinel.

NodeDL* searchData(NodeDL* sentinel, DataVal x) {
    NodeDL* cursor = sentinel->next;
    while (cursor != sentinel) {
        if (cursor->value == x)
            return cursor;
        cursor = cursor->next;
    }
    return NULL;
}

5. Gestion de la Mémoire

Il est crucial de libérer chaque nœud individuellement avant de supprimer la sentinelle elle-même pour éviter les fuites de mémoire.

void clearList(NodeDL* sentinel) {
    NodeDL* cursor = sentinel->next;
    while (cursor != sentinel) {
        NodeDL* tmp = cursor->next;
        free(cursor);
        cursor = tmp;
    }
    free(sentinel);
}

6. Analyse Comparative : Simple vs Double Chaînage

Le choix entre une liste simple et une liste double dépend des contraintes du projet :

• Navigation : La liste simple est unidirectionnelle. La liste double permet un parcours bidirectionnel, facilitant les algorithmes nécessitant de revenir en arrière.
• Complexité des opérations : L'insertion ou la suppression avant un nœud donné est en O(1) pour une liste double (car le lien prev est accessible), contre O(n) pour une liste simple (nécessité de reparcourir depuis le début pour trouver le prédécesseur).
• Consommation mémoire : La liste double consomme plus de mémoire (un pointeur supplémentaire par nœud).
• Implémentation : La liste double avec sentinelle est souvent plus simple à coder car elle élimine les tests de pointeurs nuls (NULL) fréquents dans les listes simples.