Chapitre 3
03 — Structures de Données
> **Objectif** : Comprendre la distinction entre types abstraits (ADT) et implémentations concrètes, connaître les interfaces fondamentales et savoir choisir la structure adaptée à chaque besoin. ---
03 — Structures de Données : Cours complet
Niveau : Université / Ingénierie — Durée de lecture : ~50 min
Table des matières
- ADT vs implémentation
- Les interfaces fondamentales
- Contiguë vs chaînée
- Choix de structure : les critères
- Généralités sur l'indexation
- Analyse des trade-offs
- Diagrammes de décision
- Résumé
1. ADT vs implémentation
1.1 Définition
Un Abstract Data Type (ADT) décrit un comportement : un ensemble d'opérations et leurs contrats (pré/post conditions), sans spécifier la représentation interne.
Une implémentation est la structure de données concrète qui réalise l'ADT avec des coûts précis.
Diagramme en cours de génération...
1.2 Exemple fondateur : l'ADT « List »
| Niveau | Contenu |
|---|---|
| ADT List | size(), get(i), set(i, v), add(i, v), remove(i), indexOf(v) |
| Implémentation tableau | accès O(1), insertion/milieu O(n) |
| Implémentation liste chaînée | accès O(n), insertion O(1) (si nœud connu) |
Le point central : le code client dépend de l'interface, pas de l'implémentation. C'est la base du polymorphisme et des design patterns (Strategy, Adapter).
1.3 Pourquoi cette distinction est cruciale
- Indépendance : on peut changer d'implémentation sans toucher le code client.
- Analyse : les coûts sont attachés à l'implémentation, pas à l'interface.
- Standardisation : les langages fournissent des interfaces standard (Java
List, C++std::vectorvsstd::list).
1.4 En pratique dans les langages
| Langage | ADT | Implémentations |
|---|---|---|
| Python | list | tableau dynamique uniquement |
| Java | List<T> | ArrayList (tableau), LinkedList |
| C++ | concept SequenceContainer | std::vector, std::deque, std::list |
| Go | []T | slice (tableau dynamique) |
| TypeScript | T[] | tableau dynamique |
2. Les interfaces fondamentales
2.1 List
Collection ordonnée, adressable par index, avec doublons autorisés.
| Opération | Contrat |
|---|---|
add(x) / add(i, x) | insère en fin / à la position i |
get(i) / set(i, x) | lit / remplace à la position i |
remove(i) / remove(x) | retire par position / valeur |
size() | nombre d'éléments |
indexOf(x) | première position de x |
Implémentations : tableau dynamique (O(1) accès, O(n) insert milieu), liste chaînée (O(n) accès, O(1) insertion si nœud).
2.2 Set
Collection sans doublons, sans notion d'ordre (ou ordre défini).
| Opération | Contrat |
|---|---|
add(x) | ajoute si absent (retourne false si présent) |
contains(x) | présence O(1) amorti (hash) |
remove(x) | retire si présent |
union, intersection, difference | opérations ensemblistes |
Implémentations : hash set (O(1) amorti), arbre de recherche équilibré (O(log n), ordonné).
2.3 Map (dictionnaire / associative array)
Association clé → valeur, clés uniques.
| Opération | Contrat |
|---|---|
put(k, v) | associe / remplace |
get(k) | valeur associée |
containsKey(k) | présence de la clé |
remove(k) | retire la paire |
Implémentations : hash map, tree map (ordonné), tableau (si clés entières petites).
2.4 Stack (pile)
LIFO — Last In First Out.
| Opération | Contrat |
|---|---|
push(x) | empile |
pop() | retire le sommet |
peek() / top() | consulte le sommet sans retirer |
isEmpty() | test |
2.5 Queue (file)
FIFO — First In First Out.
| Opération | Contrat |
|---|---|
enqueue(x) / offer(x) | ajoute en queue |
dequeue() / poll() | retire la tête |
peek() / front() | consulte la tête |
2.6 Deque (double-ended queue)
Ajout et retrait aux deux extrémités : addFirst, addLast, removeFirst, removeLast.
2.7 Priority Queue (file de priorité)
Retire toujours l'élément de priorité extrême (min ou max).
| Opération | Contrat |
|---|---|
insert(x) / push(x) | ajoute avec priorité |
extractMin() / pop() | retire le minimum |
peek() / getMin() | consulte le minimum |
decreaseKey(x, k) | diminue la priorité |
Implémentation canonique : tas binaire → O(log n) insert/extract, O(1) peek.
2.8 Synthèse des interfaces
Diagramme en cours de génération...
3. Contiguë vs chaînée
3.1 Les deux grandes familles
| Caractéristique | Stockage contigu (tableau) | Stockage chaîné (nœuds + pointeurs) |
|---|---|---|
| Mémoire | un seul bloc | un nœud par élément + pointeurs |
| Accès indexé | O(1) | O(n) |
| Insertion/suppression au milieu | O(n) (décalage) | O(1) (si nœud en main) |
| Localité de cache | excellente | mauvaise (nœuds dispersés) |
| Coût mémoire par élément | minimal | +1-2 pointeurs (8-16 octets) |
| Redimensionnement | nécessaire (copie) | naturel (pas de bloc) |
3.2 Localité de cache : la vraie différence
Sur les machines modernes, la mémoire cache rend le coût d'accès mémoire non uniforme :
- Tableau : accès séquentiels → préfetch → très rapide.
- Liste chaînée : sauts de pointeur aléatoires → cache misses → 10-100× plus lent sur les grands volumes.
Règle pratique : quand les données tiennent en cache et que les accès sont séquentiels, le tableau gagne presque toujours. La liste chaînée ne gagne que pour des insertions/suppressions fréquentes au milieu avec nœud déjà localisé.
3.3 Exemple : parcourir 10⁶ éléments
| Structure | Coût | Temps typique |
|---|---|---|
| Tableau (accès séquentiels) | O(n), cache-friendly | ~1 ms |
| Liste chaînée (parcours) | O(n), cache-hostile | ~10-30 ms |
Même complexité O(n), facteur 10-30 en pratique.
4. Choix de structure : les critères
4.1 Profil d'opérations
Le choix dépend des fréquences d'opérations de l'application :
- Accès par index fréquent → tableau.
- Recherche par valeur fréquente → hash set/map, ou arbre si ordre requis.
- Insertion/suppression au milieu fréquente → liste chaînée (nœud en main) ou skip list.
- Insertion/suppression aux extrémités → deque.
- Minimum/maximum fréquent → priority queue (heap).
- Parcours ordonné fréquent → arbre équilibré (AVL, rouge-noir).
4.2 La matrice de décision
| Besoin dominant | Structure | Coût signature |
|---|---|---|
| Accès index O(1) | Tableau dynamique | get O(1), insert milieu O(n) |
| Insertion milieu O(1) | Liste chaînée | get O(n), insert O(1)* |
| Recherche O(1) | Hash table | contains O(1) amorti |
| Min/max O(log n) | Tas binaire | extractMin O(log n) |
| Ordre + recherche O(log n) | Arbre équilibré | toutes O(log n) |
| LIFO | Pile (tableau) | push/pop O(1) |
| FIFO | File (circulaire) | enqueue/dequeue O(1) |
4.3 Exemple de raisonnement
Application : playlist d'un lecteur audio.
- Ajout en fin : fréquent.
- Lecture séquentielle : fréquente.
- Suppression : rare.
- → Tableau dynamique : O(1) ajout fin, O(1) accès, bonne localité.
Application : historique de navigation (undo).
- Ajout au sommet : fréquent.
- Retrait du sommet : fréquent.
- → Pile (tableau suffit) : O(1) partout.
Application : index de recherche d'un moteur.
- Recherche par mot-clé : très fréquente, volume énorme.
- → Hash map ou B-Tree (chapitre 06/07).
5. Généralités sur l'indexation
5.1 Indexer = transformer une recherche en accès
Rechercher par valeur coûte O(n) dans un tableau non trié. Les index accélèrent :
| Famille | Principe | Accès | Ordre ? | Mémoire |
|---|---|---|---|---|
| Index tableau | clé = position (entier) | O(1) | non | O(n) |
| Index hash | fonction de hachage → emplacement | O(1) amorti | non | O(n) |
| Index arbre | clés organisées en arbre | O(log n) | oui | O(n) |
5.2 Exemples concrets
- Base de données : index B+Tree (ordre + disque), index hash (égalité).
- Caches : hash map clé → valeur.
- Compilateurs : symbol table (hash map).
- OS : inode table (index tableau) pour les fichiers.
5.3 Tableau → hash → arbre : le continuum
Diagramme en cours de génération...
Règle d'or : si vous avez besoin de parcourir dans l'ordre ou de faire des requêtes de plage (a ≤ x ≤ b), l'arbre gagne ; sinon le hash gagne.
6. Analyse des trade-offs
6.1 Le compromis temps/mémoire revisité
Diagramme en cours de génération...
6.2 Tableau récapitulatif des implémentations (worst-case, amorti)
| Structure | get | insert | contains | min/max | espace |
|---|---|---|---|---|---|
| Tableau (dynamique) | O(1) | O(n) au milieu | O(n) | O(n) | O(n) |
| Liste chaînée | O(n) | O(1)* nœud | O(n) | O(n) | O(n) |
| Hash table | O(1) amorti | O(1) amorti | O(1) amorti | O(n) | O(n) |
| Arbre équilibré | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Tas binaire | — | O(log n) | O(n) | O(1) peek | O(n) |
| Pile/File (tableau) | O(1) | O(1) amorti | O(n) | O(n) | O(n) |
6.3 Les pièges classiques du choix
- Choisir la liste chaînée « parce que insertion O(1) » sans avoir le nœud : l'insertion au milieu exige d'abord O(n) de recherche.
- Choisir le hash pour tout en oubliant le besoin d'ordre (parcours trié, range query).
- Oublier la mémoire : une hash map vide sur 1M de clés peut consommer plus qu'un tableau rempli.
- Confondre O(1) amorti et O(1) garanti : les rehashing coûteux peuvent gêner les systèmes temps réel.
7. Diagrammes de décision
7.1 Arbre de choix principal
Diagramme en cours de génération...
7.2 Choix selon la fréquence des opérations
Diagramme en cours de génération...
8. Résumé
- ADT = quoi (interface + contrat), implémentation = comment (coûts précis).
- Interfaces : List (index), Set (unicité), Map (clé→valeur), Stack (LIFO), Queue (FIFO), Deque (deux bouts), Priority Queue (min/max).
- Contigu vs chaîné : O(1) accès + cache vs O(1) insertion flexible + cache-hostile.
- Choisir selon le profil : fréquences d'opérations > intuition.
- Indexation : tableau (clé entière), hash (égalité, O(1)), arbre (ordre, O(log n), range queries).
- Pièges : insertion liste sans nœud = O(n), oubli de l'ordre, confusion amorti/garanti.
- Diagrammes Mermaid : arbres de décision guident le choix.
Exercices d'auto-évaluation
- Pourquoi ne peut-on pas « changer d'implémentation sans toucher le client » si on manipule un tableau brut ?
- Donner un ADT et deux implémentations de coûts différents.
- Une application lit
T[i]10⁶ fois/s et insère au milieu 10 fois/s : quelle structure ? - Une application fait 10⁶ insertions au milieu/s et 10 lectures/s : quelle structure ?
- Pourquoi une hash map ne peut-elle pas répondre « liste les clés dans l'ordre » ?
- Citer 3 familles d'index et l'opération qu'elles accélèrent.