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/puten 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.addrenvoiefalsesi 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 —
Stackest obsolète,LinkedListest plus lente.- PriorityQueue
Un tas binaire :
offeretpollen 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.
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.