Probleme – La liste doublement chaînée, et sa sentinelle

1. Le maillon, et les opérations naïves.

typedef struct noeud_s {
    int valeur;
    struct noeud_s* prec;
    struct noeud_s* suiv;
} noeud;

Écrite sans sentinelle, la suppression d'un nœud $m$ demande quatre tests : $m$ est-il le premier ? le dernier ? les deux ? aucun ? Chacun donne un code différent, et l'oubli d'un seul produit un pointeur pendant. C'est beaucoup de code pour une opération qui, en principe, se dit en deux affectations.

2. La sentinelle circulaire. On ajoute un maillon qui n'appartient pas à la liste et qui ne disparaît jamais. La liste vide, c'est la sentinelle bouclée sur elle-même.

/* Cree une liste vide : une sentinelle qui se pointe elle-meme.
   INVARIANT : la sentinelle est toujours presente ; en partant d'elle par
   suiv on revient sur elle ; m->suiv->prec == m pour TOUT maillon. */
noeud* creer(void) {
    noeud* s = malloc(sizeof(noeud));
    if (s == NULL) { return NULL; }
    s->prec = s; s->suiv = s;
    return s;
}

/* Insere x juste apres m. Precondition : m appartient a la liste. */
noeud* inserer_apres(noeud* m, int x) {
    noeud* n = malloc(sizeof(noeud));
    if (n == NULL) { return NULL; }
    n->valeur = x;
    n->prec = m;  n->suiv = m->suiv;      /* on relie le neuf aux voisins */
    m->suiv->prec = n;  m->suiv = n;      /* puis les voisins au neuf */
    return n;
}

/* Retire m de la liste. Precondition : m n'est PAS la sentinelle.
   AUCUN cas particulier, AUCUN parcours. */
void supprimer(noeud* m) {
    m->prec->suiv = m->suiv;
    m->suiv->prec = m->prec;
    free(m);
}

Mesuré, en parcourant dans les deux sens à chaque étape :

vide                          avant []         arriere []
apres 10, 20, 30              avant [10 20 30] arriere [30 20 10]
apres suppression de 20       avant [10 30]    arriere [30 10]
apres suppression de 10       avant [30]       arriere [30]        (c'etait le premier)
apres suppression de 30       avant []         arriere []

La suppression du premier élément n'a demandé aucun traitement particulier : son prec est la sentinelle, qui existe toujours et dont le champ suiv est modifiable comme n'importe quel autre.

L'ordre des quatre affectations de inserer_apres n'est pas libre. Il faut écrire les champs du maillon neuf avant de casser m->suiv : si l'on commence par m->suiv = n, l'ancien successeur est perdu et n->suiv = m->suiv range n dans son propre champ. C'est le même piège que le suiv retenu avant free du cours : on relie avant de délier.

3. Ce qui change de complexité.

La première ligne est celle qui compte, et il faut lire l'énoncé avec soin : supprimer un maillon dont on a l'adresse. En simple chaînage, il faut retrouver son prédécesseur, donc reparcourir depuis la tête. Le second lien évite ce parcours, et c'est tout ce qu'il fait. En revanche il ne donne aucun accès direct : chercher reste linéaire, et lire la position $i$ aussi.

4. Le prix. Un pointeur de plus par maillon — sur une machine à adresses de $64$ bits et pour des entiers de $32$, la structure passe de $16$ à $24$ octets, soit $50\%$ de mémoire en plus pour la même donnée. Il faut aussi maintenir deux invariants au lieu d'un, et un seul champ oublié rend la liste incohérente dans un sens et cohérente dans l'autre — c'est-à-dire d'un diagnostic très pénible.

Le critère est donc net : on double le chaînage quand on possède déjà l'adresse des maillons à retirer. C'est le cas dans un cache à éviction, dans une liste de tâches où chaque tâche connaît son maillon, et dans les listes d'adjacence de certains algorithmes de graphes (chapitre chap:graphes-avances). Ce n'est pas le cas quand on cherche avant de supprimer : le parcours domine, et le second lien ne sert à rien.