Une structure de données est une façon d'organiser et de stocker des informations en mémoire afin de les manipuler efficacement. Le choix de la bonne structure conditionne directement les performances d'un algorithme.
Les structures fondamentales
| Structure | Usage typique | Accès |
|---|---|---|
| Tableau (Array) | Liste ordonnée d'éléments | O(1) |
| Liste chaînée | Insertions/suppressions fréquentes | O(n) |
| Pile (Stack) | LIFO — historique, undo | O(1) |
| File (Queue) | FIFO — traitement de tâches | O(1) |
| Table de hachage | Recherche rapide par clé | O(1) moyen |
| Arbre binaire | Données hiérarchiques | O(log n) |
| Graphe | Relations complexes entre nœuds | Variable |
Exemple — Pile vs File
# Pile (Stack) — dernier entré, premier sorti
stack = []
stack.append("a") # push
stack.pop() # retire "a"
# File (Queue) — premier entré, premier sorti
from collections import deque
queue = deque()
queue.append("a") # enqueue
queue.popleft() # retire "a"À retenir
Chaque structure a ses forces et ses limites. Une table de hachage est rapide pour chercher, mais consomme plus de mémoire. Un arbre est efficace pour trier, mais plus complexe à maintenir. La complexité de ces choix est analysée via la Big O Notation.
Pour aller plus loin sur les structures complexes (arbres AVL, tas, files de priorité) : Structures de données avancées.
