Cours Structures de Données Complet 📦
Les 12 chapitres essentiels — arrays, listes chaînées, arbres, graphes, hash tables et files de priorité
Introduction
Une structure de données est une façon d'organiser l'information en mémoire pour pouvoir y accéder et la modifier efficacement. Le choix de la structure impacte directement la performance. Chercher un nom dans une liste non triée de 1 million d'éléments prend O(n) = 1 million d'opérations. Dans une hash table, ça prend O(1) = 1 seule opération. Même algorithme, structure différente, 1 million de fois plus rapide.
| Structure | Accès | Recherche | Insertion | Suppression | Usage principal |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | Données indexées |
| Linked List | O(n) | O(n) | O(1) | O(1) | Insertions/suppressions fréquentes |
| Hash Table | — | O(1) | O(1) | O(1) | Lookup rapide (dict, set) |
| Stack | O(n) | O(n) | O(1) | O(1) | LIFO (undo, parenthèses) |
| Queue | O(n) | O(n) | O(1) | O(1) | FIFO (BFS, tâches) |
| BST | O(log n) | O(log n) | O(log n) | O(log n) | Données triées dynamiques |
| Heap | O(1) min | O(n) | O(log n) | O(log n) | Min/max rapide, priorités |
Arrays et listes
# Accès par index en O(1), recherche en O(n)
arr = [10, 20, 30, 40, 50]
# Accès — O(1)
arr[0] # 10
arr[–1] # 50 (dernier)
# Ajout — O(1) amorti en fin, O(n) au début/milieu
arr.append(60) # [10,20,30,40,50,60] → O(1)
arr.insert(0, 5) # [5,10,20,…] → O(n) ! décale tout
# Suppression
arr.pop() # Retire le dernier → O(1)
arr.pop(0) # Retire le premier → O(n) ! décale tout
arr.remove(30) # Retire la valeur 30 → O(n)
# Slicing — O(k) où k = taille du slice
arr[1:3] # [20, 30]
arr[::–1] # Inverse la liste
# Techniques courantes
sorted(arr) # Copie triée → O(n log n)
arr.sort() # Tri in-place → O(n log n)
len(arr) # Taille → O(1)
sum(arr) # Somme → O(n)
min(arr), max(arr) # Min/Max → O(n)
Piège courant : arr.insert(0, x) et arr.pop(0) sont O(n) car ils décalent tous les éléments. Si vous faites ça souvent → utilisez un deque (chapitre 4) qui est O(1) aux deux extrémités.
Stacks (piles)
# Push (empiler) et Pop (dépiler) en O(1)
# En Python, une list suffit comme stack
stack = []
stack.append(1) # Push → [1]
stack.append(2) # Push → [1, 2]
stack.append(3) # Push → [1, 2, 3]
stack.pop() # Pop → 3, stack = [1, 2]
stack[–1] # Peek (voir le sommet) → 2
# Cas d'usage classique : vérifier des parenthèses
def parentheses_valides(s):
stack = []
paires = ': '
for c in s:
if c in '([{':
stack.append(c)
elif c in paires:
if not stack or stack.pop() != paires[c]:
return False
return len(stack) == 0
print(parentheses_valides(« () »)) # True
print(parentheses_valides(« () »)) # False
Utilisations des stacks : vérifier les parenthèses, évaluer des expressions mathématiques (notation polonaise), Ctrl+Z (undo/redo), call stack des langages de programmation, DFS (parcours en profondeur), conversion décimal→binaire.
Queues (files)
# Enqueue (enfiler) et Dequeue (défiler) en O(1)
from collections import deque
queue = deque()
queue.append(« Alice ») # Enqueue → deque(['Alice'])
queue.append(« Bob ») # Enqueue → deque(['Alice', 'Bob'])
queue.append(« Claire ») # Enqueue → deque(['Alice', 'Bob', 'Claire'])
queue.popleft() # Dequeue → 'Alice' (premier arrivé)
queue[0] # Peek → 'Bob' (prochain)
# ⚠️ Ne PAS utiliser list pour une queue
# list.pop(0) est O(n) — deque.popleft() est O(1)
# Cas d'usage : BFS (parcours en largeur)
def bfs(graphe, depart):
visite = set([depart])
queue = deque([depart])
while queue:
noeud = queue.popleft()
for voisin in graphe[noeud]:
if voisin not in visite:
visite.add(voisin)
queue.append(voisin)
return visite
Utilisations des queues : BFS (parcours en largeur), file d'impression, serveur web (requêtes en attente), task queues (Celery, RabbitMQ, SQS), buffer de streaming. deque est aussi une stack efficace et supporte O(1) aux deux extrémités (appendleft, popleft, append, pop).
Listes chaînées
# Insertion/suppression O(1) si on a le nœud, accès O(n)
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def prepend(self, val): # O(1) — ajout au début
self.head = Node(val, self.head)
def append(self, val): # O(n) — ajout à la fin
if not self.head:
self.head = Node(val)
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = Node(val)
def delete(self, val): # O(n) — trouver + supprimer
if self.head and self.head.val == val:
self.head = self.head.next
return
curr = self.head
while curr.next:
if curr.next.val == val:
curr.next = curr.next.next
return
curr = curr.next
# Technique d'entretien : Inverser une liste chaînée — O(n)
def inverser(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev # Nouvelle tête
En pratique, les listes chaînées sont rarement utilisées directement en Python ou JavaScript — les arrays dynamiques (list/Array) sont plus performants grâce au cache CPU (données contiguës en mémoire). Mais elles sont essentielles en entretien technique et servent de base aux stacks, queues et tables de hachage (chaining). Doubly linked list (prev + next) permet la suppression en O(1) quand on a le nœud.
Hash maps et sets
# Fonctionnement : hash(clé) → index dans un tableau interne
# Dict Python — O(1) get/set/delete/in
ages =
ages[« Claire »] = 24 # Insert O(1)
ages[« Alice »] # Lookup O(1) → 28
« Bob » in ages # Recherche O(1) → True
del ages[« Bob »] # Suppression O(1)
ages.get(« David », 0) # Défaut si absent → 0
# Set Python — collection sans doublons, O(1) add/in/remove
s =
s.add(4) #
s.add(2) # (pas de doublon)
3 in s # O(1) → True
# Pattern : compter les fréquences
from collections import Counter
mots = [« chat », « chien », « chat », « oiseau », « chat »]
freq = Counter(mots) # Counter()
# Pattern : Two Sum — trouver 2 nombres qui font target
def two_sum(nums, target):
seen = # valeur → index
for i, n in enumerate(nums):
complement = target – n
if complement in seen:
return [seen[complement], i]
seen[n] = i
return []
# defaultdict — dict avec valeur par défaut
from collections import defaultdict
graph = defaultdict(list)
graph[« A »].append(« B ») # Pas de KeyError si « A » n'existe pas
Le dictionnaire est la structure de données la plus importante en programmation quotidienne. Quand vous voyez « trouver si X existe » ou « compter les occurrences » ou « grouper par clé » → pensez dict ou set immédiatement. C'est la différence entre un algorithme O(n²) (2 boucles) et O(n) (1 boucle + hashmap).
Arbres binaires (BST)
# Recherche, insertion, suppression en O(log n) moyen
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Recherche dans un BST — O(log n)
def search(root, val):
if not root or root.val == val:
return root
if val < root.val:
return search(root.left, val)
return search(root.right, val)
# Insertion dans un BST — O(log n)
def insert(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
# 3 traversées — toutes O(n)
def inorder(root): # Gauche → Racine → Droite (TRIÉ !)
if not root: return []
return inorder(root.left) + [root.val] + inorder(root.right)
def preorder(root): # Racine → Gauche → Droite (copier l'arbre)
if not root: return []
return [root.val] + preorder(root.left) + preorder(root.right)
def postorder(root): # Gauche → Droite → Racine (supprimer l'arbre)
if not root: return []
return postorder(root.left) + postorder(root.right) + [root.val]
Inorder sur un BST donne les éléments triés. Un BST déséquilibré (type linked list) tombe à O(n). Les arbres auto-équilibrés (AVL, Red-Black) garantissent O(log n) — c'est ce qu'utilisent en interne TreeMap (Java), std::map (C++), et les index B-tree des bases de données.
Heaps et files de priorité
# Accès au minimum en O(1), insertion/suppression en O(log n)
import heapq
# Min-heap (Python heapq = toujours min-heap)
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)
heap[0] # Peek min → 1, O(1)
heapq.heappop(heap) # Pop min → 1, O(log n)
heapq.heappop(heap) # Pop min → 2
# Max-heap : astuce — inverser le signe
max_heap = []
heapq.heappush(max_heap, –5)
heapq.heappush(max_heap, –2)
heapq.heappush(max_heap, –8)
–heapq.heappop(max_heap) # → 8 (le plus grand)
# Top K éléments — O(n log k)
def top_k(arr, k):
return heapq.nlargest(k, arr)
# heapify — transformer une liste en heap O(n)
arr = [5, 3, 8, 1, 9]
heapq.heapify(arr) # arr est maintenant un min-heap
Le heap est indispensable pour : trouver le min/max en O(1), Dijkstra (chemin le plus court), trouver les K plus grands/petits éléments, scheduler de tâches par priorité, merge de K listes triées. En entretien, dès que vous voyez « Kème plus grand » ou « top K » → pensez heap.
Hash tables (en profondeur)
class HashTable:
def __init__(self, size=16):
self.size = size
self.buckets = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size # Index dans le tableau
def set(self, key, value): # O(1) amorti
idx = self._hash(key)
for pair in self.buckets[idx]:
if pair[0] == key:
pair[1] = value
return
self.buckets[idx].append([key, value])
def get(self, key): # O(1) amorti
idx = self._hash(key)
for pair in self.buckets[idx]:
if pair[0] == key:
return pair[1]
raise KeyError(key)
# Collision = 2 clés avec le même hash → même bucket
# Résolution : chaining (linked list dans le bucket)
# ou open addressing (chercher le prochain slot libre)
O(1) « amorti » signifie O(1) en moyenne. Pire cas O(n) si toutes les clés tombent dans le même bucket (collision extrême). En pratique, Python redimensionne automatiquement la table quand le load factor dépasse ~66%, ce qui maintient O(1). Seules les clés hashables (immuables) fonctionnent : int, str, tuple → oui. list, dict, set → non.
Graphes
graphe =
# 2. Matrice d'adjacence — pour graphes denses
# A B C D
# A [ 0, 1, 1, 0 ]
# B [ 1, 0, 0, 1 ]
# C [ 1, 0, 0, 0 ]
# D [ 0, 1, 0, 0 ]
# Graphe pondéré
graphe_p =
# Détecter un cycle (DFS + 3 couleurs)
def has_cycle(graphe):
WHITE, GRAY, BLACK = 0, 1, 2
color =
def dfs(node):
color[node] = GRAY
for voisin in graphe[node]:
if color[voisin] == GRAY: # Cycle !
return True
if color[voisin] == WHITE and dfs(voisin):
return True
color[node] = BLACK
return False
return any(dfs(n) for n in graphe if color[n] == WHITE)
| Représentation | Espace | Vérifier arête | Lister voisins | Idéal pour |
|---|---|---|---|---|
| Liste d'adjacence | O(V + E) | O(degré) | O(degré) | Graphes épars (la plupart) |
| Matrice d'adjacence | O(V²) | O(1) | O(V) | Graphes denses, petits graphes |
Tries (arbres de préfixes)
# Recherche/insertion en O(m) où m = longueur du mot
# Idéal pour : autocomplétion, correcteur orthographique, dictionnaire
class TrieNode:
def __init__(self):
self.children =
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word): # O(m)
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word): # O(m) — mot exact
node = self._find(word)
return node is not None and node.is_end
def starts_with(self, prefix): # O(m) — préfixe
return self._find(prefix) is not None
def _find(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return node
trie = Trie()
trie.insert(« python »)
trie.insert(« pytorch »)
trie.search(« python ») # True
trie.starts_with(« py ») # True (autocomplétion !)
Bonnes pratiques
| Besoin | Structure | Python |
|---|---|---|
| Accès par index rapide | Array | list |
| Recherche rapide par clé | Hash map | dict |
| Vérifier l'existence | Hash set | set |
| LIFO (dernier entré, premier sorti) | Stack | list (append/pop) |
| FIFO (premier entré, premier sorti) | Queue | deque |
| Min/max rapide | Heap | heapq |
| Données triées dynamiques | BST / Sorted list | SortedList (sortedcontainers) |
| Autocomplétion, préfixes | Trie | Implémentation custom |
| Relations/connexions | Graphe | dict[list] |
| Comptage de fréquences | Counter | Counter |
✅ À FAIRE
• dict/set pour lookup O(1) (pas de boucle !)
• deque pour les queues (pas list.pop(0))
• heapq pour min/max/top-K
• Counter pour compter les fréquences
• defaultdict pour éviter les KeyError
• Connaître la complexité de chaque opération
• Choisir la structure AVANT d'écrire l'algorithme
• Préférer les built-ins (optimisés en C)
• Profiler avant d'optimiser
• Pratiquer les patterns d'entretien
❌ À ÉVITER
• if x in list dans une boucle → O(n²) (utiliser set)
• list.pop(0) ou list.insert(0, x) → O(n)
• Créer sa propre hash table (utiliser dict)
• Linked list quand un array suffit
• Ignorer la complexité spatiale
• Trier pour chercher (hash map = O(n) vs sort O(n log n))
• Boucles imbriquées quand un dict suffit
• BST non équilibré (pire cas O(n))
• Confondre heap et sorted array
• Oublier que list.sort() est in-place
🏠 Hub Programmation
🧠 Cours Algorithmes
🐍 Cours Python
⚡ Cours JavaScript
☕ Cours Java
