Structures de données : listes, piles, files et dictionnaires : fiche de révision

1Interface et implémentation : la distinction fondatrice

Une structure de données abstraite se définit par son interface : l'ensemble des opérations qu'elle offre (ajouter, retirer, tester si vide…) et leur comportement, indépendamment de la façon dont elles sont programmées. L'implémentation est le choix concret (tableau, cellules chaînées, classe Python) qui réalise cette interface. Le programme insiste sur cette séparation : on peut changer d'implémentation sans changer le code qui utilise la structure.

En Python, la liste native (type list) est un tableau dynamique : accès par indice en O(1), ajout en fin (append) en O(1) amorti, mais insertion ou suppression en tête en O(n) car tous les éléments sont décalés. Cette propriété conditionne le choix de structure pour chaque usage.

2Listes chaînées, piles et files

Une liste chaînée est une suite de cellules, chacune contenant une valeur et une référence vers la cellule suivante (None pour la dernière). Insérer en tête est en O(1), accéder au k-ième élément est en O(k). Implémentation minimale :

class Cellule:

def __init__(self, valeur, suivante=None): self.valeur = valeur ; self.suivante = suivante

Une pile (stack) suit la règle LIFO — Last In, First Out : le dernier élément empilé est le premier dépilé. Interface : empiler (push), dépiler (pop), est_vide, sommet. Usages : évaluation d'expressions, vérification de parenthésage, pile d'appels des fonctions récursives, parcours en profondeur. Avec une liste Python, append et pop() en fin de liste donnent une pile en O(1).

Une file (queue) suit la règle FIFO — First In, First Out : premier arrivé, premier servi. Interface : enfiler (enqueue), défiler (dequeue), est_vide. Usages : parcours en largeur d'un graphe, files d'attente, ordonnancement. Avec une liste Python, pop(0) est en O(n) : on préfère collections.deque (popleft en O(1)) ou une implémentation à deux piles.

3Dictionnaires et tables de hachage

Un dictionnaire associe des clés à des valeurs (paires clé/valeur). En Python, d[cle] = valeur, d[cle], cle in d, del d[cle], d.keys(), d.values(), d.items(). Les clés doivent être immuables (int, str, tuple), pas des listes.

L'implémentation par table de hachage explique son efficacité : une fonction de hachage transforme la clé en un indice de tableau, ce qui donne un accès, une insertion et une suppression en O(1) en moyenne. Les collisions (deux clés, même indice) sont gérées par chaînage ou adressage ouvert ; dans le pire cas, tout dégénère en O(n), mais ce cas est rarissime avec une bonne fonction de hachage.

Comparaison décisive au bac : chercher si un élément est dans une liste Python (x in liste) est en O(n) ; dans un dictionnaire ou un ensemble (set), c'est en O(1) en moyenne. Compter les occurrences des mots d'un texte, mémoriser des résultats (mémoïsation) ou indexer des données se font donc avec un dictionnaire.

4Exercice type et pièges classiques

Énoncé type : vérifier qu'une expression est bien parenthésée. Solution avec une pile : on parcourt les caractères ; une parenthèse ouvrante est empilée ; une fermante dépile (si la pile est vide, l'expression est incorrecte) ; à la fin, l'expression est correcte si et seulement si la pile est vide.

def bien_parenthesee(s):

pile = []

for c in s:

if c == '(': pile.append(c)

elif c == ')':

if len(pile) == 0: return False

pile.pop()

return len(pile) == 0

Pièges : confondre LIFO et FIFO dans l'énoncé ; utiliser pop(0) pour une file sans signaler la complexité O(n) ; utiliser une liste comme clé de dictionnaire (TypeError : unhashable) ; oublier que la longueur d'une liste chaînée nécessite un parcours O(n) si elle n'est pas mémorisée. À l'épreuve pratique, on demande souvent d'implémenter une pile ou une file par une classe avec les méthodes de l'interface.