#Structures de données
On ne “collectionne” pas des structures pour elles‑mêmes: on les choisit parce qu’elles rendent un usage précis efficace et simple à raisonner. Ce cours raconte à quoi servent les grandes familles, quels coûts elles impliquent, et comment décider en fonction de votre contexte.
#Deux modèles pour commencer: séquentiel et hiérarchique
Imaginez une bibliothèque. Un “tableau dynamique” est une rangée de cases contiguës: on saute directement à la case 42 (accès indexé O(1)), mais si on veut insérer un livre au milieu, il faut décaler ceux à droite (O(n)). Une “liste chaînée” ressemble à une chasse au trésor: chaque livre indique où est le suivant. On peut glisser un nouveau livre juste en changeant deux flèches (insertion locale O(1)), mais trouver le 42ᵉ prend du temps (O(n)) et la promenade n’exploite pas bien le cache.
Plus haut, les “arbres” imposent un ordre et gardent les opérations en O(log n). Les arbres équilibrés servent d’ensembles/dictionnaires triés (itérations triées, planification, index). Les “tas” (heap) se concentrent sur « quel est le plus petit/grand tout de suite ? », utiles pour des files de priorité (ordonnancement, Dijkstra).
Enfin, les “tables de hachage” offrent un accès clé→valeur ultra‑rapide en moyenne (≈ O(1) amorti) au prix d’une absence d’ordre. Elles s’appuient sur une fonction de hachage et un redimensionnement qui maintient un bon facteur de charge.
#Décider sans se tromper (et sans dogme)
Commencez par mesurer ce que fait votre programme le plus souvent: lit‑on par index ? insère‑t‑on en tête ? exige‑t‑on un ordre trié ? Privilégiez la structure qui optimise le chemin critique. Souvenez‑vous que la localité mémoire compte tout autant que les notations de complexité: un tableau simple bat souvent une liste chaînée dans la vraie vie.
Immuable ou mutable ? Les structures persistantes simplifient l’historique et la concurrence (partage structurel) mais créent plus d’objets. À privilégier pour des pipelines fonctionnels et des UIs réactives; à doser pour des boucles très chaudes.
#Mise en pratique rapide
Écrivez une fonction qui maintient un top‑K des éléments les plus grands vus jusqu’ici. Essayez d’abord avec un tableau trié naïf, puis remplacez la structure de support par un “min‑heap” de taille K. Comparez la simplicité et les coûts.