Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Choisir la bonne structure de données

Choisir la bonne structure de données

Raisonner sur la complexitédebutant

Choisir la bonne structure résout la moitié d'un exercice. Quatre questions suffisent.

1. Ai-je besoin d'un accès par clé ? → HashMap 2. Ai-je besoin de savoir si j'ai déjà vu un élément ? → HashSet 3. Ai-je besoin d'un ordre ? → TreeMap/TreeSet (ordre des clés) ou LinkedHashMap (ordre d'insertion) 4. Ai-je besoin du plus petit ou du plus grand, en continu ? → PriorityQueue

// Compter : la ligne la plus utile de tous les entretiens
Map<String, Integer> freq = new HashMap<>();
for (String mot : mots) freq.merge(mot, 1, Integer::sum);

// Détecter un doublon : add renvoie false si déjà présent
Set<Integer> vus = new HashSet<>();
for (int x : t) if (!vus.add(x)) return x;

// Pile et file : la même classe
Deque<Integer> pile = new ArrayDeque<>();   pile.push(1); pile.pop();
Deque<Integer> file = new ArrayDeque<>();   file.offer(1); file.poll();

// Les K plus grands : un tas des K meilleurs
PriorityQueue<Integer> tas = new PriorityQueue<>();  // min-heap par défaut

Deux structures à ne pas utiliser : Stack (obsolète, synchronisée) et LinkedList (accès en O(n), allocations inutiles). ArrayDeque remplace les deux.

Les termes à connaître

ArrayList

Un tableau redimensionnable. Accès par index en O(1), ajout en fin en O(1) amorti, mais insertion ou suppression au début en O(n) — tout le reste doit être décalé.

HashMap

Une table de hachage : get/put en O(1) en moyenne. Aucun ordre garanti. C'est la structure la plus utile en entretien, et de loin.

HashSet

Un ensemble sans doublon, adossé à une HashMap. add renvoie false si l'élément était déjà présent — un détail qui résout à lui seul beaucoup d'exercices.

ArrayDeque

Une file double : ajout et retrait aux deux extrémités en O(1). C'est la bonne pile et la bonne file en Java — Stack est obsolète, LinkedList est plus lente.

PriorityQueue

Un tas binaire : offer et poll en O(log n), avec accès immédiat au plus petit élément. La structure des problèmes de « top K ».

TreeMap / TreeSet

Structures ordonnées en O(log n), qui offrent firstKey, floorKey, ceilingKey, subMap. Le choix dès qu'on a besoin d'un ordre ou d'une recherche par intervalle.

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.