PARTIE 2 (Suite) : SUPPRESSION

TP 7 : Supprimer un Nœud

La suppression est plus délicate car il faut “recoudre” la chaîne avant de supprimer l’élément pour ne pas perdre la suite de la liste.

Algorithme Général (Suppression par valeur)

1. Si la liste est vide, on ne fait rien.
2. Cas spécial : Si l’élément à supprimer est la tête (head).
   • Sauvegarder head dans un pointeur temporaire toDelete.
   • Avancer head vers head->next.
   • Libérer toDelete.
3. Cas général :
   • Parcourir la liste avec deux pointeurs : current et prev (précédent).
   • Chercher le nœud.
   • Si trouvé : Faire pointer prev->next vers current->next (on saute le nœud courant).
   • Libérer current.

Schéma Suppression (Milieu) :

Code (Extrait)

void deleteNode(Node** head, int key) {
    Node *temp = *head, *prev;

    // Si la tête contient la clé
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp); // Libération mémoire cruciale !
        return;
    }

    // Recherche de la clé
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // Si pas trouvé
    if (temp == NULL) return;

    // Déliement
    prev->next = temp->next;
    free(temp);
}

Gestion de la Mémoire (free)

En C, il n’y a pas de Garbage Collector. Si vous supprimez un lien vers un nœud sans appeler free(), ce bloc mémoire reste occupé jusqu’à la fin du programme. C’est une fuite de mémoire (memory leak).

TP 7 : Exercice

Implémentez deleteNode et deleteAtPosition (qui supprime le n-ième élément). Testez la suppression du premier, dernier, et d’un élément central.