03 — Le coût des structures de données

Ce que tu vas apprendre

• Pourquoi chaque structure de données est un compromis, pas un choix neutre
• Le coût en Big-O de l'accès, la recherche, l'insertion et la suppression
• Comment array, liste chaînée, hashmap, Set et arbre se comparent
• Le tableau récapitulatif à garder sous la main

Prérequis

• 02 — Compter les opérations

Quand tu écris const x = [] en JavaScript ou x = {} en Python, tu ne choisis pas juste un conteneur. Tu choisis un profil de coûts. Chaque structure de données est rapide pour certaines opérations et lente pour d'autres. Il n'existe aucune structure parfaite. Le métier consiste à connaître ces compromis et à prendre celle qui est rapide pour ce que ton code fait le plus souvent.

On va comparer les structures sur quatre opérations qui couvrent l'essentiel des besoins :

• Accès : lire l'élément à une position connue (l'index 5, par exemple)
• Recherche : trouver si une valeur est présente, sans connaître sa position
• Insertion : ajouter un élément
• Suppression : retirer un élément

Le tableau dynamique (array)

C'est Array en JavaScript, list en Python. Les éléments sont stockés côte à côte en mémoire, dans des cases contiguës.

typescriptconst items = [10, 20, 30, 40];
items[2];          // accès par index : O(1)
items.push(50);    // ajout en fin : O(1) amorti
items.includes(30); // recherche par valeur : O(n)
items.splice(1, 1); // suppression au milieu : O(n)

Accès par index : O(1). Comme les cases sont contiguës, l'adresse de l'élément i se calcule directement (adresse de départ + i × taille d'une case). Une seule opération, peu importe la taille. C'est la grande force du tableau.

Recherche par valeur : O(n). Pour savoir si 30 est présent, il faut parcourir les cases une par une. Pas de raccourci. C'est le talon d'Achille du tableau, et la source de la plupart des bugs de performance.

Insertion en fin : O(1) amorti. Ajouter à la fin est immédiat, sauf quand le tableau est plein et doit s'agrandir : il alloue alors un bloc plus grand et recopie tout. Cette recopie coûte O(n), mais elle est rare. Lissée sur de nombreux ajouts, le coût moyen reste O(1). C'est ce qu'on appelle « amorti ».

Insertion ou suppression au milieu : O(n). Insérer à l'index 0 oblige à décaler tous les éléments suivants d'une case vers la droite. Supprimer au milieu oblige à décaler vers la gauche pour combler le trou. Plus le tableau est grand, plus on décale.

Le tableau est imbattable quand tu lis par index et que tu ajoutes en fin. Il est mauvais quand tu cherches par valeur ou que tu modifies le début.

La liste chaînée (linked list)

Les éléments ne sont pas contigus. Chaque élément (un « nœud ») contient sa valeur et un pointeur vers le suivant. Ils peuvent être éparpillés en mémoire.

Accès par index : O(n). Pour atteindre le 5ᵉ élément, il faut suivre les pointeurs depuis le début, un par un. Pas de calcul d'adresse direct. C'est l'inverse du tableau.

Recherche par valeur : O(n). Comme le tableau, il faut tout parcourir.

Insertion ou suppression en tête : O(1). Si tu as déjà le nœud concerné, brancher ou débrancher un pointeur est immédiat, sans décaler quoi que ce soit. C'est la force de la liste chaînée.

En pratique, en TypeScript comme en Python, on utilise rarement une liste chaînée à la main. Le tableau dynamique est plus rapide dans la majorité des cas réels, parce que la contiguïté en mémoire le rend très efficace pour le processeur. La liste chaînée brille surtout quand on insère et supprime beaucoup en tête, ou comme brique interne d'autres structures (les files, par exemple).

La hashmap (objet, Map, dict)

C'est Map ou un objet {} en JavaScript, dict en Python. Elle associe des clés à des valeurs. En interne, une fonction de hachage transforme la clé en une position dans un tableau interne, ce qui permet d'aller directement au bon endroit.

pythonprix = {"pomme": 2, "poire": 3, "kiwi": 5}
prix["poire"]            # recherche par clé : O(1) en moyenne
prix["banane"] = 1       # insertion : O(1) en moyenne
del prix["kiwi"]         # suppression : O(1) en moyenne
"pomme" in prix          # test de présence : O(1) en moyenne

Recherche, insertion, suppression par clé : O(1) en moyenne. C'est la révolution. Là où le tableau cherchait en O(n), la hashmap retrouve une valeur en temps constant grâce au hachage. C'est pour ça que la version « Set » de mon exemple de déduplication écrasait la version « tableau ».

Le pire cas : O(n). Si beaucoup de clés tombent sur la même position (une « collision »), la structure dégénère vers une recherche linéaire. Avec une bonne fonction de hachage (celle des langages modernes en fournit une), ce pire cas est rarissime. On raisonne donc sur le cas moyen O(1), tout en sachant que la garantie absolue est O(n).

Ce qu'elle perd. Une hashmap n'a pas d'ordre fiable basé sur la valeur, et tu ne peux pas accéder « au 5ᵉ élément ». Elle répond à la question « cette clé existe-t-elle, et que vaut-elle ? », pas à « donne-moi les éléments dans l'ordre ».

Le Set

Un Set (en JavaScript comme en Python) est une hashmap qui ne stocke que des clés, sans valeurs associées. Il répond à une seule question : cet élément est-il présent ? Et il y répond en O(1) en moyenne.

typescriptconst vus = new Set<number>();
vus.add(42);     // O(1) en moyenne
vus.has(42);     // O(1) en moyenne
vus.delete(42);  // O(1) en moyenne

Dès que ton code fait des tests de présence répétés (« ai-je déjà vu cet identifiant ? », « cet élément est-il dans ma liste autorisée ? »), le Set est presque toujours la bonne réponse. Remplacer un array.includes() dans une boucle par un set.has() transforme un O(n²) en O(n). C'est l'optimisation la plus rentable et la plus courante.

L'arbre binaire de recherche équilibré

Un arbre équilibré (de type AVL ou rouge-noir) garde les éléments triés. En descendant l'arbre, chaque comparaison élimine la moitié des éléments restants.

Accès, recherche, insertion, suppression : O(log n). Plus lent que le O(1) d'une hashmap, mais avec un avantage que la hashmap n'a pas : les éléments restent triés. Tu peux parcourir dans l'ordre, trouver le plus petit élément supérieur à une valeur, lister une plage. C'est ce qu'utilisent les index de bases de données.

Ni JavaScript ni Python n'offrent d'arbre équilibré dans leur bibliothèque standard. On les rencontre surtout via des bibliothèques (sortedcontainers en Python) ou à l'intérieur des moteurs de bases de données. Mais le profil O(log n) avec ordre maintenu est important à connaître pour comprendre les choix d'indexation.

Le tableau récapitulatif

Voici le compromis de chaque structure sur les quatre opérations. C'est la table à garder en tête quand tu choisis.

La leçon à retenir

Aucune structure ne gagne partout. Le tableau gagne sur l'accès par index, la hashmap et le Set gagnent sur la recherche par valeur, l'arbre gagne quand il faut chercher vite tout en gardant l'ordre.

La vraie question n'est jamais « quelle est la meilleure structure ? ». Elle est « quelle opération mon code fait-il des milliers de fois ? ». Si tu cherches sans cesse des valeurs, un Set ou une hashmap. Si tu lis par position et ajoutes en fin, un tableau. Choisis selon l'opération chaude, pas selon l'habitude.

L'article suivant aborde l'autre dimension du coût, souvent oubliée : la mémoire. Parce qu'une hashmap qui répond en O(1) le paie en espace, et ce compromis temps/espace est partout.

Sources

• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitres 10 "Elementary Data Structures", 11 "Hash Tables" et 13 "Red-Black Trees". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Chapitre 3 "Searching". Addison-Wesley.
• Wengrow, J. (2020). A Common-Sense Guide to Data Structures and Algorithms (2nd ed.). Pragmatic Bookshelf.
• V8 Team. Elements kinds in V8. v8.dev/blog/elements-kinds (modèle interne des tableaux JavaScript).