Supprimer un maillon, et faire disparaître le cas particulier

Version usuelle : on garde un pointeur vers le précédent.

/* Supprime la premiere occurrence de x. Renvoie la nouvelle tete.
   Precondition : tete est une chaine valide (eventuellement NULL). */
maillon* supprimer(maillon* tete, int x) {
    if (tete == NULL) { return NULL; }
    if (tete->valeur == x) {                 /* CAS PARTICULIER : la tete */
        maillon* s = tete->suivant;
        free(tete);
        return s;
    }
    maillon* prec = tete;
    while (prec->suivant != NULL && prec->suivant->valeur != x) {
        prec = prec->suivant;
    }
    if (prec->suivant != NULL) {
        maillon* mort = prec->suivant;
        prec->suivant = mort->suivant;       /* on court-circuite */
        free(mort);
    }
    return tete;
}

Le cas de la tête est traité à part, et c'est obligé : le lien qui pointe sur la tête n'est pas un champ suivant, c'est la variable de l'appelant. Ce n'est pas la même chose, donc on ne peut pas l'écrire de la même manière.

Version sans cas particulier : on manipule le lien, pas le maillon.

/* Meme specification. Aucun cas particulier, aucune duplication de code. */
maillon* supprimer(maillon* tete, int x) {
    maillon** p = &tete;                     /* p designe le LIEN a modifier */
    while (*p != NULL && (*p)->valeur != x) {
        p = &(*p)->suivant;
    }
    if (*p != NULL) {
        maillon* mort = *p;
        *p = mort->suivant;
        free(mort);
    }
    return tete;
}

Vérifié : les deux fonctions donnent le même résultat sur la liste $[1,2,3,4]$, qu'on supprime $1$ (la tête), $3$ (le milieu) ou $9$ (absent).

L'idée, et elle vaut d'être comprise une fois pour toutes. maillon** p ne pointe pas sur un maillon : il pointe sur l'endroit où est écrite l'adresse du maillon. Or cet endroit est de même nature partout — la variable tete au début, le champ suivant ensuite. En raisonnant sur les liens plutôt que sur les maillons, la tête cesse d'être une exception.

Terminaison : le variant est le nombre de maillons restant après *p. Complexité : $\Theta (k)$ où $k$ est la position de $x$, $\Theta (n)$ au pire. Aucune des deux versions ne fait mieux — la chaîne n'a pas d'accès direct.

L'autre parade, qu'emploie le premier problème de ce chapitre, est la sentinelle : un maillon bidon en tête, qui n'appartient pas à la liste, et devant lequel il y a toujours un suivant à modifier. Les deux techniques résolvent le même problème, et les deux méritent d'être connues.