Insérer en fin sans pointeur de queue

/* Ajoute x en fin. Renvoie la tete. Cout : Theta(n) -- on RETRAVERSE tout. */
maillon* inserer_fin(maillon* tete, int x) {
    maillon* neuf = malloc(sizeof(maillon));
    neuf->valeur = x; neuf->suivant = NULL;
    if (tete == NULL) { return neuf; }
    maillon* m = tete;
    while (m->suivant != NULL) { m = m->suivant; }
    m->suivant = neuf;
    return tete;
}

Le $k$-ième appel traverse $k-1$ maillons, donc le total vaut

$$\sum _{k=1}^n(k-1)=\frac{n(n-1)}{2}=\Theta (n^2).$$

Mesuré :

n =  5000 : 0,013 s        n = 20000 : 0,218 s        n = 80000 : 3,545 s
n = 10000 : 0,052 s        n = 40000 : 0,890 s

Le temps est multiplié par $4$ chaque fois que $n$ double : la signature du quadratique, comme l'annonçait le calcul.

Les deux corrections, et il faut savoir choisir entre elles.

• Garder un pointeur de queue. La structure devient un couple (tête, queue), l'insertion en fin passe en $\Theta (1)$ et le total en $\Theta (n)$. C'est exactement la structure de file du cours. Le prix est un champ de plus, et un invariant de plus à maintenir : queue est le dernier maillon, ou NULL si la liste est vide — et il faut y penser dans toutes les opérations, y compris la suppression du dernier élément.
• Construire en tête, puis renverser une fois. Coût $\Theta (n)+\Theta (n)=\Theta (n)$, sans champ supplémentaire ni invariant nouveau. C'est le choix naturel en OCaml, où l'on écrit List.rev après un List.fold_left qui empile.

Le défaut à nommer, parce qu'il revient sous mille formes : on a placé dans une boucle une opération dont le coût dépend de la taille déjà construite. C'est le même défaut que strlen dans la condition d'une boucle au chapitre chap:langage-c, et que la concaténation répétée de chaînes. Chaque appel semble innocent ; c'est leur somme qui est quadratique, et aucun profil d'exécution ne le dira tant que $n$ reste petit.