Mille mesures entières sont conservées, au choix dans un tableau ou dans une liste chaînée.
Objectif
Comparer la place occupée par les deux représentations, sur deux machines.
La déclaration du nœud
struct Noeud {
int valeur;
struct Noeud *suivant;
};
Le surcoût, et ce qu'il achète
La liste paie un pointeur par valeur, donc au moins le double d'un tableau. Ce qu'elle achète est l'insertion et le retrait en deux affectations, sans jamais recopier ce qui existe déjà. Le calcul ne tranche pas à lui seul : c'est l'usage qui décide, et une moyenne à calculer ne justifie jamais ce surcoût.