Comment choisir la bonne structure de données pour un problème ?

Question

Accepted Answer

Choisissez la structure dont **les opérations les plus fréquentes sont les moins coûteuses** pour votre modèle d'accès. Commencez par lister les opérations que vous effectuerez, estimez leur fréquence, puis associez-les aux forces de la structure.

## Checklist de décision

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## Associer les opérations à la complexité

| Besoin | Meilleure structure | Coût de l'opération clé |
|---|---|---|
| Accès aléatoire par index | dynamic array | O(1) |
| Recherche par clé | hash map | O(1) avg |
| Trié + requêtes de plage | balanced BST | O(log n) |
| Min/max répétément | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Recherche par préfixe | trie | O(L) |

## Exemple de raisonnement

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## Pourquoi c'est important

Bien choisir fait souvent la différence entre une solution O(n) et une O(n²) — le levier unique le plus important sur la performance.

Les intervieweurs testent exactement ce raisonnement : ils veulent voir comment vous associez les exigences aux coûts des opérations, pas comment vous mémorisez les structures.

Besoin	Meilleure structure	Coût de l'opération clé
Accès aléatoire par index	dynamic array	O(1)
Recherche par clé	hash map	O(1) avg
Trié + requêtes de plage	balanced BST	O(log n)
Min/max répétément	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Recherche par préfixe	trie	O(L)