Une structure de données est une façon d'organiser et de stocker des données en mémoire pour qu'elles puissent être accédées et modifiées efficacement. Un type de données abstrait (ADT) est le modèle logique — les opérations et leur comportement — indépendamment de la façon dont il est implémenté.
L'ADT décrit opérations existent ; la structure de données décide elles sont stockées et à quelle vitesse elles s'exécutent.
ADT: Stack → push, pop, peek (LIFO behavior)
Implementations: → array-backed OR linked-list-backed
ADT: List → get(i), insert, remove
Implementations: → dynamic array OR linked list
# Both satisfy the "Stack" ADT, but have different cost profiles
stack = [] # list-backed stack
stack.append(10) # push -> amortized O(1)
top = stack[-1] # peek -> O(1)
stack.pop() # pop -> O(1)
| Concern | Question to ask |
|---|---|
| Access pattern | Random access or sequential? |
| Mutations | Frequent insert/delete in the middle? |
| Ordering | Sorted, FIFO, LIFO, or none? |
| Lookups | By index or by key? |
Le bon choix est celui dont les opérations courantes sont peu coûteuses pour votre charge de travail.
Choisir la mauvaise structure transforme une opération O(1) en O(n), ce qui peut rendre le code des milliers de fois plus lent à l'échelle.
Penser en termes d'ADTs vous permet de raisonner sur le comportement en premier, puis d'échanger les implémentations plus tard sans réécrire les appelants.