Pourquoi un programme qui traite quelques milliers de lignes devient-il soudain lent dès qu'on passe à quelques millions ? La réponse tient rarement à la puissance de la machine. Elle tient le plus souvent au choix de la structure de données, c'est-à-dire à la manière dont l'information est organisée en mémoire. Choisir la mauvaise structure revient à chercher une aiguille dans une botte de foin sans savoir où regarder.
Le tableau : un accès direct mais des insertions coûteuses
Le tableau est la structure la plus intuitive. Les éléments y sont rangés côte à côte, et chacun occupe une position repérable par un indice. Lire le dixième élément coûte donc le même effort que lire le premier : l'accès est direct.
Cette simplicité a un revers. Insérer un élément au milieu d'un tableau oblige à décaler tout ce qui suit pour libérer la place. Sur une collection de quelques dizaines d'éléments, l'opération est invisible. Sur plusieurs millions, elle devient mesurable, voire pénalisante. Le tableau convient donc bien aux données de taille connue que l'on parcourt souvent et que l'on modifie peu.
La liste chaînée et la table de hachage : deux compromis opposés
La liste chaînée répond au problème de l'insertion. Chaque élément contient l'adresse du suivant, si bien qu'ajouter ou retirer un maillon ne demande que de modifier quelques liens. En revanche, atteindre le millième élément impose de traverser les 999 précédents : l'accès devient progressif, et non plus direct.
La table de hachage attaque un autre problème : retrouver une information précise parmi beaucoup d'autres. Une fonction de calcul transforme la clé en un indice, ce qui permet de retrouver une valeur sans parcourir toute la collection. Le mécanisme est rapide en moyenne, mais il connaît des limites. Deux clés peuvent produire le même indice, et ce conflit ralentit la recherche. La structure consomme aussi de la mémoire supplémentaire pour maintenir son organisation. Elle n'est donc pas adaptée aux traitements qui exigent de parcourir les données dans un ordre précis.
Arbres et files : quand l'ordre ou la priorité comptent
Certains usages exigent de conserver les données triées tout en acceptant des ajouts fréquents. Les arbres équilibrés répondent à ce besoin : les éléments y sont rangés selon une hiérarchie qui garantit que la recherche, l'insertion et la suppression restent rapides. Le prix à payer est une mise en œuvre plus délicate, car l'arbre doit rester équilibré pour tenir ses promesses.
D'autres situations relèvent de l'ordre d'arrivée. Une file traite les éléments dans l'ordre où ils se présentent, comme une succession de tâches à exécuter. Une pile fait l'inverse : le dernier arrivé repart le premier, ce qui correspond au comportement du bouton « annuler » dans un logiciel. Une file de priorité, enfin, sert lorsque certains éléments doivent passer avant d'autres, par exemple dans la gestion d'événements urgents.
Aucune de ces structures n'est meilleure en soi. Le tableau excelle en lecture, la liste chaînée en modification locale, la table de hachage en recherche par clé, l'arbre en maintien d'un ordre. Le choix dépend de l'opération la plus fréquente dans le programme concerné. Une structure adaptée à un usage peut se révéler inutilement complexe dans un autre, et la simplicité reste souvent un critère décisif tant que les volumes traités restent modestes.
