PARTIE 2 (Fin) : LISTES DOUBLEMENT CHAÎNÉES

TP 10 : Concepts

Une liste doublement chaînée permet de parcourir la liste dans les deux sens (avant et arrière). Chaque nœud possède deux pointeurs.

typedef struct DoubleNode {
    int data;
    struct DoubleNode *prev; // Vers l'élément précédent
    struct DoubleNode *next; // Vers l'élément suivant
} DoubleNode;

Schéma :

Avantages et Inconvénients

• + On peut supprimer un nœud connaissant seulement son pointeur (car on a accès à prev, pas besoin de parcourir depuis le début).
• + Parcours inverse facile.
• - Prend plus de mémoire (2 pointeurs par nœud).
• - Gestion plus complexe des mises à jour (il faut maintenir 2 liens à chaque insertion/suppression).

Insertion

Lors de l’insertion, il faut connecter 4 liens :

1. newNode->next
2. newNode->prev
3. prevNode->next
4. nextNode->prev

// Exemple : Insertion en tête
void insertAtHead(DoubleNode** head, int value) {
    DoubleNode* newNode = createDoubleNode(value);

    newNode->next = *head;
    newNode->prev = NULL;

    if (*head != NULL) {
        (*head)->prev = newNode;
    }

    *head = newNode;
}

TP 10 : Exercice

Implémentez une liste double avec printForward() et printBackward() pour vérifier que les liens sont corrects dans les deux sens.