Structures de données linéaires

Type abstrait : interface contre implémentation#

~5 min de lectureBaseeduscol-programme-nsi-terminale

Type abstrait « Pile » : une interface, plusieurs implémentations

Fig. 1Une même interface (le contrat : empiler, dépiler, sommet, est_vide) admet plusieurs implémentations. L'interface dit CE QUE fait la structure ; l'implémentation, COMMENT elle le fait.

Un type abstrait de données (TAD) décrit un ensemble de valeurs et les opérations autorisées sur elles, sans préciser comment ces valeurs sont stockées en mémoire. C'est un contrat.

L'interface répond à la question « CE QUE fait la structure » : la liste des opérations, leur signature (entrées/sorties) et leur contrat (préconditions, effet). Exemple pour une pile : empiler(p, x), dépiler(p), sommet(p), est_vide(p).

L'implémentation répond à la question « COMMENT elle le fait » : la représentation interne choisie (un tableau dynamique, une liste chaînée de maillons, etc.) et le code des opérations sur cette représentation.

Un même type abstrait admet plusieurs implémentations qui respectent toutes le même contrat ; on peut donc changer l'implémentation sans modifier le code qui utilise la structure. C'est le principe d'abstraction (ou d'encapsulation).

Une structure peut être implémentée à l'aide d'une autre : une pile ou une file au moyen d'une liste, un dictionnaire au moyen d'une liste de couples (clé, valeur). On parle d'implémentation par délégation.

Écrire un contrat, c'est répondre à trois questions pour CHAQUE opération, et l'épreuve pratique note précisément cela. La SIGNATURE : quels arguments, de quel type, et que renvoie l'opération (une valeur ? rien ?). La PRÉCONDITION : ce qui doit être vrai pour que l'appel ait un sens — dépiler exige une pile non vide, et cette exigence est portée par le contrat, pas devinée par l'appelant. L'EFFET : ce que l'opération change dans la structure, énoncé en termes observables par les autres opérations. Le contrat de empiler(p, x) ne dit pas « ajoute x dans le tableau interne » ; il dit « après l'appel, sommet(p) vaut x » — une phrase vraie quelle que soit la représentation choisie.

L'intérêt de la séparation se mesure au moment où l'on change d'avis. Un programme écrit contre l'interface d'une file continue de fonctionner si l'on remplace la liste Python par une deque : le code appelant ne mentionne nulle part append ni pop(0), seulement enfiler et defiler. Si le même programme manipulait directement la liste interne, chaque changement de représentation imposerait de relire tout le code. C'est cette propriété — un changement d'implémentation reste local — que l'on nomme encapsulation, et c'est elle qui justifie l'effort d'écrire une interface avant d'écrire du code.

Vocabulaire

→ Cartes

type abstrait de donnéesDescription d'un ensemble de valeurs et des opérations autorisées sur elles, indépendamment de toute représentation en mémoire.
interfaceEnsemble des opérations offertes par une structure, avec leur signature et leur contrat ; ce que la structure fait.
implémentationReprésentation interne choisie et code des opérations sur cette représentation ; comment la structure le fait.
préconditionCondition qui doit être vraie au moment de l'appel pour que l'opération ait un sens ; sa violation rend le résultat indéfini.
encapsulationPrincipe selon lequel la représentation interne n'est atteinte que par les opérations de l'interface, ce qui rend tout changement de représentation local.

La lecture charge du contenu depuis YouTube (Google).Ouvrir sur YouTube ↗

Exemple corrigé

Spécifier l'interface d'une pile, indépendamment de l'implémentation

Rédigez l'interface (le contrat) d'une pile d'entiers : pour chaque opération, donnez sa signature, son effet et, le cas échéant, sa précondition. N'écrivez aucun code de représentation interne.

creer_pile()
Signature : creer_pile() → Pile. Effet : renvoie une nouvelle pile vide. Précondition : aucune.
est_vide(p)
Signature : est_vide(p) → bool. Effet : renvoie True si la pile p ne contient aucun élément, False sinon. Précondition : aucune.
empiler(p, x)
Signature : empiler(p, x) → None. Effet : ajoute x au sommet de p ; après l'appel, sommet(p) vaut x. Précondition : aucune.
depiler(p)
Signature : depiler(p) → élément. Effet : retire et renvoie l'élément situé au sommet de p. Précondition : p ne doit pas être vide (sinon l'opération est indéfinie).
sommet(p)
Signature : sommet(p) → élément. Effet : renvoie l'élément au sommet SANS le retirer. Précondition : p ne doit pas être vide.

Résultat : L'interface décrit entièrement le comportement attendu de la pile (le contrat) sans rien dire de sa représentation : on peut maintenant l'implémenter de plusieurs façons.

Objectif Bac

Objectif Bac : énoncer la différence interface / implémentation et l'illustrer sur un exemple (deux représentations possibles d'une même pile).
Objectif Bac : à partir d'une interface donnée, écrire le code d'une opération en respectant exactement sa signature et son contrat (sans changer les noms ni les paramètres imposés).
Objectif Bac : rédiger un contrat complet pour une opération donnée — signature, précondition, effet — sans jamais nommer la représentation interne.
Objectif Bac : montrer par un exemple que deux implémentations distinctes satisfont le même contrat, et nommer ce qui les sépare : le COÛT des opérations, non leur résultat.
Objectif Bac : reconnaître dans un énoncé une violation d'encapsulation (le code appelant accède directement à la représentation interne) et la corriger en passant par l'interface.

Erreurs fréquentes

Confondre l'interface et l'implémentation : décrire la structure par sa représentation interne (« une pile, c'est un tableau ») au lieu de son contrat d'opérations.
Croire qu'il existe une seule « bonne » implémentation : tant que le contrat est respecté, plusieurs représentations sont valides ; elles diffèrent seulement par leurs coûts.
Écrire une précondition dans le corps de la fonction sous forme de commentaire et croire le contrat rempli : une précondition se vérifie par une assertion ou se documente dans la spécification, elle n'est pas une remarque en passant.
Confondre « type abstrait » et « classe » : la classe est un moyen d'implémenter un type abstrait dans un langage objet ; le type abstrait existe indépendamment de tout langage.
Modifier la signature imposée par l'énoncé (renommer un paramètre, renvoyer un couple au lieu d'une valeur) : le programme de test fourni appelle la signature exacte, tout écart le fait échouer.

Révision active

On donne l'interface d'une file : creer_file(), enfiler(f, x), defiler(f), est_vide(f). Sans choisir d'implémentation, écrivez en français le contrat (effet attendu, valeur renvoyée, précondition) de chacune des quatre opérations.

S’entraîner sur des exercices associés50 questions sur ce thème

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Annexe de l'arrêté du 19-7-2019 (NOR MENE1921247A) — programme de spécialité NSI, classe terminale (BO spécial n° 8 du 25 juillet 2019) (Ministère de l'Éducation nationale)

Listes : tableaux dynamiques et listes chaînées#

~5 min de lectureStandardeduscol-programme-nsi-terminale

Liste chaînée : maillons valeur / suivant et coûts des opérations

Fig. 2Chaque maillon porte une valeur et une référence vers le suivant ; le dernier pointe vers None. Insérer en tête est en O(1) (on crée un maillon sans rien décaler) ; accéder à l'élément d'indice i coûte O(i) (suivre i références).

Une liste est une suite ordonnée d'éléments accessibles par leur position (indice). Les opérations usuelles sont l'accès à l'élément d'indice i, l'insertion et la suppression d'un élément.

Le type list de Python est un tableau dynamique : les éléments sont rangés dans une zone contiguë de mémoire qui s'agrandit automatiquement. L'accès par indice tab[i] est en temps constant O(1) ; ajouter en fin (append) est en O(1) amorti.

En revanche, insérer ou supprimer en début ou au milieu d'un tableau dynamique oblige à décaler tous les éléments suivants : c'est en O(n) dans le pire des cas.

Une liste chaînée représente la suite par une chaîne de maillons : chaque maillon contient une valeur et une référence vers le maillon suivant (None pour le dernier). On accède à la liste par sa tête.

Dans une liste chaînée, insérer ou supprimer en tête se fait en O(1) (on ne déplace rien, on rebranche une référence) ; mais l'accès à l'élément d'indice i coûte O(i) car il faut parcourir les maillons un à un.

Choisir entre tableau dynamique et liste chaînée dépend des opérations dominantes : accès fréquent par indice → tableau ; insertions/suppressions fréquentes en tête → liste chaînée.

Le « O(1) amorti » de append mérite une explication, parce qu'il revient chaque année sous une forme ou une autre. Un tableau dynamique réserve une zone contiguë plus grande que nécessaire ; tant qu'il reste de la place, ajouter en fin coûte une écriture, donc O(1). Quand la zone est pleine, l'interpréteur alloue une zone plus grande (typiquement d'un facteur constant) et RECOPIE tous les éléments : ce redimensionnement coûte O(n). Mais il devient de plus en plus rare à mesure que la liste grandit, si bien que le coût moyen d'un append, réparti sur une longue suite d'ajouts, reste constant. « Amorti » signifie exactement cela : moyenné sur la suite des opérations, pas garanti à chaque appel.

Le tableau et la chaîne s'opposent par leur rapport à la MÉMOIRE, et tout le reste en découle. Le tableau occupe des cases consécutives : connaissant l'adresse de départ et l'indice, la machine calcule directement l'adresse de la case voulue — d'où l'accès en O(1), et d'où l'obligation de tout décaler quand on insère au milieu. La chaîne éparpille ses maillons n'importe où en mémoire, chacun portant l'adresse du suivant : rien n'est à décaler quand on insère, mais rien ne permet non plus de sauter directement au i-ième maillon. Retenez la cause (contiguïté ou non), les coûts s'en déduisent.

Vocabulaire

→ Cartes

tableau dynamiqueSuite d'éléments rangés dans une zone mémoire contiguë redimensionnée automatiquement ; le type list de Python en est un.
liste chaînéeSuite représentée par des maillons dispersés en mémoire, chacun portant une valeur et la référence du maillon suivant.
maillonCellule d'une liste chaînée contenant une valeur et la référence vers le maillon suivant (None pour le dernier).
coût amortiCoût moyen d'une opération réparti sur une longue suite d'appels, qui lisse les opérations coûteuses mais rares.
accès par indiceLecture de l'élément de rang i ; en temps constant dans un tableau contigu, proportionnel à i dans une chaîne.

Coûts dans un tableau dynamique (list Python)

\text{accès tab}[i] : \mathcal{O}(1) \qquad \text{insertion en tête (tableau)} : \mathcal{O}(n)

L'accès direct par indice est immédiat, mais insérer en tête décale les n éléments suivants.

Coûts dans une liste chaînée

\text{accès à l'indice } i \text{ (chaînée)} : \mathcal{O}(i) \qquad \text{insertion en tête} : \mathcal{O}(1)

Le compromis est inversé : l'accès devient linéaire, mais l'insertion en tête est immédiate car on ne déplace aucun élément.

Exemple corrigé

Insertion en tête d'une liste chaînée

On modélise une liste chaînée par une classe Maillon (attributs valeur et suivant). Écrivez la fonction inserer_en_tete(tete, x) qui insère x au début et renvoie la nouvelle tête, et justifiez son coût.

Représentation
Un maillon a deux champs : valeur (l'entier stocké) et suivant (le maillon d'après, ou None). La liste est désignée par son premier maillon, la tête.
Créer le nouveau maillon
On crée m = Maillon(x). On veut que m précède l'ancienne tête : on règle donc m.suivant sur l'ancienne tête.
Renvoyer la nouvelle tête
Le nouveau premier maillon est m : on le renvoie. Aucun autre maillon n'a été déplacé ni modifié.
Coût
On a effectué un nombre constant d'opérations (création d'un maillon + une affectation), indépendant de la longueur de la liste.

Résultat : inserer_en_tete s'écrit en trois lignes (m = Maillon(x) ; m.suivant = tete ; return m) et s'exécute en temps constant O(1), là où l'insertion en tête d'un tableau dynamique serait en O(n).

Erreurs fréquentes

Croire que l'accès tab[i] dans une liste chaînée est en O(1) comme dans un tableau : il faut suivre i références, donc O(i).
Oublier de traiter le maillon de fin de chaîne (référence None) dans un parcours, ce qui provoque une boucle infinie ou une erreur d'attribut sur None.
Écrire `while m.suivant is not None` pour parcourir toute la chaîne : cette boucle s'arrête sur l'AVANT-dernier maillon et oublie le dernier. La condition correcte porte sur `m`, pas sur `m.suivant`.
Annoncer qu'une liste chaînée « économise la mémoire » : chaque maillon stocke une référence supplémentaire, si bien qu'à contenu égal elle occupe généralement PLUS de place qu'un tableau. Son avantage est le coût des insertions, pas l'encombrement.
Confondre suppression en tête et suppression d'une valeur : rebrancher la tête coûte O(1), mais RETROUVER la valeur à supprimer impose d'abord un parcours en O(n).

Révision active

Implémentez une liste chaînée d'entiers (classe Maillon avec attributs valeur et suivant). Écrivez une fonction longueur(tete) qui renvoie le nombre de maillons, et une fonction inserer_en_tete(tete, x) qui renvoie la nouvelle tête après insertion de x.

S’entraîner sur des exercices associés50 questions sur ce thème

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Annexe de l'arrêté du 19-7-2019 (NOR MENE1921247A) — programme de spécialité NSI, classe terminale (BO spécial n° 8 du 25 juillet 2019) (Ministère de l'Éducation nationale)

Piles (LIFO) et files (FIFO) : opérations et applications#

~7 min de lectureStandardeduscol-programme-nsi-terminale

Pile (LIFO) : empiler et dépiler au sommet

Fig. 3On empile et on dépile au même bout, le sommet. Le premier dépiler renvoie 8, le dernier entré (cellule mise en évidence) : c'est la discipline LIFO (dernier entré, premier sorti).

Une pile est une structure LIFO (last in, first out) : le dernier élément entré est le premier sorti. Toutes les opérations se font au même bout, le sommet : empiler ajoute au sommet, dépiler retire le sommet.

Opérations d'une pile : empiler(x), dépiler() (retire et renvoie le sommet), sommet() (lit le sommet sans le retirer), est_vide(). Dépiler ou lire le sommet d'une pile vide est une erreur (précondition : pile non vide).

Une file est une structure FIFO (first in, first out) : le premier élément entré est le premier sorti. Les deux bouts sont distincts : enfiler ajoute en queue, défiler retire en tête. L'ordre d'arrivée est préservé.

Opérations d'une file : enfiler(x), défiler() (retire et renvoie la tête), est_vide(). Comme pour la pile, défiler une file vide est indéfini.

Implémentation en Python : une liste sert naturellement de pile via append (empiler) et pop (dépiler) qui agissent en fin de liste en O(1) amorti. Pour une file, retirer en tête avec pop(0) est en O(n) ; on préfère collections.deque, dont les retraits aux deux bouts sont en O(1).

Applications typiques : la pile sert à l'évaluation d'expressions, à la vérification du bon parenthésage et à la gestion des appels de fonctions (pile d'exécution) ; la file sert à la gestion de tampons (files d'attente) et au parcours en largeur d'un graphe.

Pourquoi `pop(0)` est-il en O(n) alors que `pop()` est en O(1) ? Parce qu'une liste Python est un tableau contigu : retirer le dernier élément libère simplement la dernière case, tandis que retirer le premier oblige à décaler d'un cran les n − 1 éléments restants pour que les indices restent consécutifs. Implémenter une file avec `append` et `pop(0)` donne donc un défilement en O(n) : sur n défilements, l'algorithme entier passe en O(n²), ce qui suffit à faire échouer un parcours en largeur sur un grand graphe. `collections.deque` maintient une structure doublement chaînée par blocs et offre `append`, `appendleft`, `pop` et `popleft` tous en O(1) : c'est l'implémentation à citer.

La pile n'est pas seulement une structure que l'on programme : c'est aussi celle que la MACHINE utilise pour vous. À chaque appel de fonction, le processeur empile un enregistrement d'activation contenant les paramètres, les variables locales et l'adresse de retour ; au retour, il dépile. C'est exactement une discipline LIFO, et c'est ce qui explique qu'une récursion trop profonde provoque un débordement de pile — en Python, une RecursionError levée par défaut au-delà d'environ mille appels imbriqués. Le lien est explicitement au programme : la pile d'appels du thème « récursivité » est la pile spécifiée ici.

Vocabulaire

→ Cartes

pile (LIFO)Structure où le dernier élément entré est le premier sorti ; toutes les opérations agissent au sommet.
file (FIFO)Structure où le premier élément entré est le premier sorti ; on enfile en queue et on défile en tête.
sommetExtrémité d'une pile où l'on empile et dépile ; `sommet(p)` le lit sans le retirer.
défilerRetirer et renvoyer l'élément situé en tête d'une file ; opération indéfinie sur une file vide.
dequeFile à deux bouts de la bibliothèque standard Python, dont les ajouts et retraits aux deux extrémités sont en temps constant.

Discipline LIFO de la pile

\text{Pile (LIFO)} : \text{empiler puis dépiler renvoie le DERNIER entré}

Last In, First Out : la dernière valeur empilée est la première dépilée.

Discipline FIFO de la file

\text{File (FIFO)} : \text{enfiler puis défiler renvoie le PREMIER entré}

First In, First Out : la file préserve l'ordre d'arrivée des éléments.

File (FIFO) : enfiler en queue, défiler en tête

Fig. 4On enfile en queue, on défile en tête. Le premier défiler renvoie 3, le premier entré (cellule mise en évidence) : c'est la discipline FIFO (premier entré, premier sorti) ; l'ordre d'arrivée est préservé.

Application : une pile vérifie le bon parenthésage de « ([]) »

Fig. 5On empile chaque parenthèse ouvrante et on dépile à chaque fermante (en vérifiant qu'elle correspond au sommet). Une pile vide à la fin (cellule mise en évidence) signe une expression bien parenthésée.

Exemple corrigé

Dérouler une suite d'opérations sur une pile puis sur une file

On part d'une structure vide et on exécute la suite d'opérations : ajouter 3, ajouter 7, ajouter 8, puis retirer, retirer. Donnez la valeur renvoyée par chaque retrait et l'état final (a) si la structure est une pile, (b) si c'est une file.

Pile — empilements
On empile 3, 7, 8 dans cet ordre. De bas en haut, la pile contient [3, 7, 8] ; le sommet est 8.
Pile — dépilements
Le premier depiler() retire le sommet 8 et le renvoie. Le second retire le nouveau sommet 7 et le renvoie (LIFO). Il reste [3].
File — enfilements
On enfile 3, 7, 8 ; de la tête vers la queue : [3, 7, 8]. La tête est 3.
File — défilements
Le premier defiler() retire la tête 3 et le renvoie. Le second retire la nouvelle tête 7 et le renvoie (FIFO). Il reste [8].

Résultat : Pile : les retraits renvoient 8 puis 7, état final [3]. File : les retraits renvoient 3 puis 7, état final [8]. Même suite d'entrées, ordres de sortie opposés : c'est toute la différence LIFO / FIFO.

Exemple corrigé

Vérifier le bon parenthésage avec une pile

À l'aide d'une pile, écrivez l'algorithme bien_parenthesee(ch) qui renvoie True si la chaîne ch, composée des symboles ( ) [ ], est correctement parenthésée (chaque fermante correspond à la dernière ouvrante non encore fermée). Déroulez-le sur « ([]) » puis sur « ([)] ».

Principe
On parcourt ch de gauche à droite. À chaque ouvrante ( ou [, on l'empile. À chaque fermante, on dépile : la pile doit être non vide et son sommet doit être l'ouvrante correspondante, sinon la chaîne est mal parenthésée.
Test final
Après lecture complète, la chaîne est bien parenthésée si et seulement si la pile est vide (toutes les ouvrantes ont été refermées).
Dérouler « ([]) »
( → empile ( ; [ → empile [ ; ] → sommet [ correspond, on dépile ; ) → sommet ( correspond, on dépile. Pile vide à la fin → True.
Dérouler « ([)] »
( → empile ( ; [ → empile [ ; ) → sommet est [ mais on attend [ ↔ ], incompatibilité → False (les paires se croisent).

Résultat : L'algorithme renvoie True pour « ([]) » (pile vide à la fin) et False pour « ([)] » (sommet incompatible à la fermeture). La discipline LIFO de la pile capture exactement l'imbrication correcte des parenthèses.

Objectif Bac

Objectif Bac : dérouler à la main une suite d'empilements/dépilements ou d'enfilements/défilements et donner l'état final, ou la valeur renvoyée par chaque dépiler/défiler.
Objectif Bac : écrire les opérations de base d'une pile (empiler, dépiler, est_vide, sommet) ou d'une file (enfiler, défiler, est_vide), et reconnaître si un usage donné relève d'une pile ou d'une file.
Objectif Bac : justifier le choix de `collections.deque` pour une file par le coût de `pop(0)` sur une liste, en chiffrant l'effet sur l'algorithme complet (O(n) par défilement, donc O(n²) au total).
Objectif Bac : tenir une trace propre — un tableau à colonnes « opération / structure après / valeur renvoyée » — plutôt qu'un état final seul, car les points portent sur les étapes intermédiaires.

Erreurs fréquentes

Confondre pile et file : utiliser une pile (LIFO) là où l'ordre d'arrivée doit être respecté, alors qu'une file (FIFO) est requise (par exemple une file d'attente d'impression).
Appeler dépiler / défiler sans tester est_vide au préalable : sur une structure vide, l'opération est indéfinie et lève une erreur (IndexError sur une liste Python).
Écrire que `depiler` « renvoie le sommet » sans dire qu'elle le RETIRE : c'est précisément ce qui la distingue de `sommet`, et l'oubli fausse toute trace d'exécution.
Traiter le parenthésage en comptant les ouvrantes et les fermantes : « )( » donne un compte équilibré et n'est pourtant pas correct. Seule la pile, qui vérifie la correspondance dans l'ordre, décide.

Révision active

Implémentez une pile à l'aide d'une liste Python : écrivez les fonctions creer_pile(), est_vide(p), empiler(p, x), depiler(p) et sommet(p). Puis utilisez votre pile pour écrire bien_parenthesee(ch) qui teste si une chaîne formée de ( ) [ ] est correctement parenthésée.

S’entraîner sur des exercices associés50 questions sur ce thème

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Annexe de l'arrêté du 19-7-2019 (NOR MENE1921247A) — programme de spécialité NSI, classe terminale (BO spécial n° 8 du 25 juillet 2019) (Ministère de l'Éducation nationale)

Dictionnaires : clé, valeur et table de hachage#

~5 min de lectureStandardeduscol-programme-nsi-terminale

Dictionnaire (table de hachage) : la clé est transformée en indice d'alvéole

Fig. 6La clé passe par la fonction de hachage h, qui calcule l'indice de son alvéole dans le tableau. D'où un accès, une insertion et un test d'appartenance en O(1) en moyenne (les collisions éventuelles sont gérées dans le tableau).

Un dictionnaire associe à chaque clé une valeur (association clé → valeur). On accède à une valeur par sa clé, et non par une position : c'est un accès associatif, contrairement à l'accès par index d'une liste.

Les opérations usuelles sont : créer un dictionnaire, ajouter ou modifier un couple d[cle] = valeur, accéder à d[cle], tester l'appartenance d'une clé (cle in d), supprimer un couple, et parcourir l'ensemble des couples clé-valeur.

Le type dict de Python implémente le dictionnaire par une table de hachage : une fonction de hachage h transforme la clé en un indice de tableau (une alvéole), ce qui permet un accès direct à la valeur.

Grâce au hachage, l'accès, l'insertion et le test d'appartenance par clé sont en temps quasi constant O(1) en moyenne — bien plus rapide qu'une recherche séquentielle O(n) dans une liste de couples.

Les clés d'un dictionnaire Python doivent être hachables et sont uniques : affecter d[cle] avec une clé déjà présente remplace l'ancienne valeur. On peut parcourir les clés (for c in d), les valeurs (d.values()) ou les couples (d.items()).

On peut implémenter un dictionnaire au moyen d'une autre structure, par exemple une liste de couples (clé, valeur) ; mais la recherche d'une clé y est alors séquentielle, donc en O(n), d'où l'intérêt de la table de hachage.

La fonction de hachage fait tout le travail, et le comprendre suffit à répondre aux questions de coût. Elle transforme une clé en un entier, dont on prend le reste modulo la taille du tableau interne : la clé désigne ainsi directement une alvéole, sans aucune comparaison avec les autres clés. D'où l'accès en O(1) en moyenne. Deux clés distinctes peuvent toutefois tomber sur la même alvéole — c'est une COLLISION —, et la table doit alors les distinguer, par exemple en conservant dans chaque alvéole la liste des couples qui s'y rangent. Tant que les collisions restent rares, le coût moyen demeure constant ; dans le pire des cas, toutes les clés collisionnent et l'on retombe sur O(n).

Une clé Python doit être HACHABLE : son hachage doit rester le même pendant toute sa présence dans le dictionnaire. Les types immuables (nombres, chaînes, tuples d'immuables) le sont ; les listes et les dictionnaires ne le sont pas, et `d[[1, 2]] = 3` lève un TypeError. La raison est mécanique : si l'on pouvait modifier une clé après l'avoir rangée, son hachage changerait, la valeur resterait dans l'ancienne alvéole et deviendrait introuvable.

Vocabulaire

→ Cartes

dictionnaireStructure associant à chaque clé une valeur unique, avec accès par clé et non par position.
fonction de hachageFonction qui transforme une clé en un entier servant, après réduction modulo la taille de la table, d'indice d'alvéole.
collisionSituation où deux clés distinctes reçoivent la même alvéole ; la table doit alors les départager.
clé hachableClé dont le hachage ne change pas au cours de son séjour dans la table ; en Python, les objets immuables.
accès associatifAccès à une valeur par la clé qui lui est associée, par opposition à l'accès par position dans une séquence.

Principe de la table de hachage

h : \text{clé} \longmapsto \text{indice d'alvéole} \quad\Rightarrow\quad \text{accès par clé en } \mathcal{O}(1) \text{ (en moyenne)}

La fonction de hachage h calcule directement l'indice où ranger (ou retrouver) la valeur, d'où un accès quasi instantané.

Dictionnaire contre liste de couples

\text{liste de couples} : \text{recherche d'une clé en } \mathcal{O}(n) \quad\text{vs}\quad \text{dict} : \mathcal{O}(1) \text{ en moyenne}

Chercher une clé dans une liste de n couples exige de la parcourir (O(n)) ; la table de hachage évite ce parcours.

Exemple corrigé

Compter les occurrences des lettres d'un mot avec un dictionnaire

Écrivez compter_lettres(mot) qui renvoie un dictionnaire {lettre : nombre d'occurrences}, et déroulez-le sur « banane ».

Initialiser
On part d'un dictionnaire vide d = {}. Il associera chaque lettre rencontrée à son compteur.
Parcourir le mot
Pour chaque lettre du mot : si la lettre est déjà une clé de d (lettre in d), on incrémente d[lettre] ; sinon on crée le couple d[lettre] = 1. Le test in s'appuie sur le hachage, en O(1) moyen.
Dérouler « banane »
b → {b:1} ; a → {b:1, a:1} ; n → {b:1, a:1, n:1} ; a → a déjà présent, {b:1, a:2, n:1} ; n → {b:1, a:2, n:2} ; e → {b:1, a:2, n:2, e:1}.
Coût
Chaque lettre déclenche un test d'appartenance et une mise à jour en O(1) moyen ; pour un mot de longueur n, le total est O(n).

Résultat : compter_lettres('banane') renvoie {'b': 1, 'a': 2, 'n': 2, 'e': 1}. Le dictionnaire permet un comptage direct par clé, là où une liste de couples imposerait une recherche séquentielle à chaque lettre.

Erreurs fréquentes

Croire qu'un dictionnaire est ordonné par valeurs de clés ou indexé par des positions entières : on accède par clé, et l'ordre des couples n'est pas un ordre de tri.
Accéder à d[cle] pour une clé absente, ce qui lève une KeyError : il faut d'abord tester cle in d (ou utiliser d.get(cle)).
Utiliser une liste comme clé de dictionnaire : les listes sont muables donc non hachables, et l'affectation lève TypeError.
Modifier un dictionnaire pendant qu'on le parcourt (`for c in d: del d[c]`) : Python lève RuntimeError. Parcourez une copie des clés, `list(d)`, si vous devez supprimer.
Annoncer l'accès par clé « en O(1) » sans réserve : la formulation exigible est « O(1) en moyenne », le pire des cas restant linéaire.

Révision active

Écrivez compter_lettres(mot) qui renvoie un dictionnaire associant à chaque lettre de mot son nombre d'occurrences. Par exemple, compter_lettres('banane') doit donner {'b': 1, 'a': 2, 'n': 2, 'e': 1}.

S’entraîner sur des exercices associés50 questions sur ce thème

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Annexe de l'arrêté du 19-7-2019 (NOR MENE1921247A) — programme de spécialité NSI, classe terminale (BO spécial n° 8 du 25 juillet 2019) (Ministère de l'Éducation nationale)

Choisir et implémenter la structure adaptée à un problème#

~6 min de lectureApprofondissementeduscol-programme-nsi-terminale

Croissance du coût : accès par clé en O(1) (dictionnaire) contre O(n) (liste de couples)

Choisir une structure de données revient à identifier les opérations dominantes du problème (accès, insertion, suppression, recherche par clé, ordre de traitement) et à retenir la structure qui les rend efficaces.

Repère LIFO/FIFO : si le dernier élément arrivé doit être traité en premier (annulation, parcours en profondeur, pile d'appels), c'est une pile ; si l'ordre d'arrivée doit être respecté (file d'attente, tampon, parcours en largeur), c'est une file.

Repère accès : accès par position (indice) → liste/tableau ; accès par clé symbolique → dictionnaire ; accès uniquement aux extrémités selon une discipline → pile ou file.

Implémenter une structure à l'aide d'une autre est courant : une pile et une file se réalisent avec une liste ; un dictionnaire se réalise (naïvement) avec une liste de couples, ou (efficacement) avec une table de hachage.

Tableau récapitulatif des coûts moyens : accès par indice — liste O(1), chaînée O(n) ; insertion en tête — liste O(n), chaînée O(1), pile/file O(1) ; recherche par clé — liste de couples O(n), dictionnaire O(1) en moyenne.

Justifier le choix, c'est nommer l'opération critique et son coût dans chaque structure candidate, puis conclure : un bon choix peut faire passer un algorithme de O(n²) à O(n).

La justification attendue à l'écrit suit toujours la même charpente, et l'écrire dans cet ordre rapporte les points : (1) nommer l'opération dominante et son NOMBRE d'exécutions dans l'algorithme ; (2) donner son coût dans chaque structure candidate ; (3) multiplier, puis comparer les totaux ; (4) conclure. Exemple : « le programme teste l'appartenance de chacun des n mots du texte au lexique ; dans une liste ce test coûte O(m), soit O(n·m) au total, tandis que dans un ensemble ou un dictionnaire il coûte O(1) en moyenne, soit O(n) ; on retient donc le dictionnaire. » Un raisonnement de cette forme est complet ; « le dictionnaire est plus rapide » ne l'est pas.

Trois pièges de sélection reviennent avec régularité. Le premier : un besoin d'ORDRE (« traiter par ordre d'arrivée », « annuler la dernière action ») impose une pile ou une file, pas une liste que l'on trierait. Le deuxième : une contrainte d'UNICITÉ (« sans doublon ») oriente vers un ensemble ou les clés d'un dictionnaire, dont la structure interdit le doublon au lieu de le faire vérifier à chaque insertion. Le troisième : un besoin de PRIORITÉ (« traiter d'abord le plus urgent ») n'est ni une pile ni une file — il demande une file de priorité, hors programme mais que l'on peut simuler par un parcours du minimum, et il faut alors annoncer le coût O(n) de ce parcours.

Vocabulaire

→ Cartes

opération dominanteOpération dont le nombre d'exécutions détermine l'ordre de grandeur du coût total de l'algorithme.
implémentation par délégationRéalisation d'une structure au moyen d'une autre, dont les opérations sont appelées par celles de l'interface.
file de prioritéStructure d'où l'on extrait toujours l'élément de plus forte priorité, indépendamment de son ordre d'arrivée.
ensembleCollection sans doublon ni ordre imposé, offrant un test d'appartenance en temps constant moyen.

Principe du choix par le coût

\text{coût total} = (\text{nombre d'opérations}) \times (\text{coût unitaire de l'opération dominante})

Le bon choix de structure minimise le coût unitaire de l'opération répétée le plus souvent.

Exemple corrigé

Choisir et justifier les structures d'une file d'impression

Un logiciel gère les travaux envoyés à une imprimante : ils doivent être imprimés dans l'ordre d'arrivée, et l'on veut pouvoir retrouver instantanément le propriétaire d'un travail à partir de son identifiant. Choisissez les structures adaptées et justifiez par le coût des opérations.

Identifier les opérations
Besoin 1 : traiter les travaux dans l'ordre d'arrivée (on ajoute à la fin, on retire au début). Besoin 2 : retrouver un propriétaire à partir d'un identifiant (accès par clé, répété).
Besoin 1 → file (FIFO)
L'ordre d'arrivée doit être respecté : c'est exactement la discipline FIFO d'une file. Enfiler en queue et défiler en tête (avec collections.deque) coûtent O(1).
Besoin 2 → dictionnaire
On veut un accès direct par identifiant : un dictionnaire identifiant → propriétaire donne cet accès en O(1) en moyenne. Une liste de couples imposerait une recherche séquentielle en O(n) à chaque requête.
Conclusion chiffrée
Pour q requêtes sur n travaux, la liste de couples coûte O(q·n) tandis que le dictionnaire coûte O(q) en moyenne : le gain est décisif quand n grandit.

Résultat : On choisit une file (FIFO) pour l'ordre d'impression — enfiler/défiler en O(1) — et un dictionnaire identifiant → propriétaire pour l'accès par clé en O(1) moyen, là où une liste de couples donnerait O(n) par requête. Le choix est justifié par le coût des opérations dominantes.

Explication pas à pas5 étapes

1
Tout part d'une question : quelle est l'opération que mon programme va répéter le plus souvent ?
2
Si je dois respecter l'ordre d'arrivée — imprimer les documents dans l'ordre où ils ont été envoyés — la discipline est FIFO : je choisis une file.
3
Si au contraire je veux retrouver une valeur à partir d'une clé symbolique, par exemple le propriétaire d'un travail à partir de son identifiant, je choisis un dictionnaire.
4
La justification est toujours chiffrée : recherche par clé dans une liste de couples, O(n) par requête ; dans un dictionnaire, O(1) en moyenne. L'écart se creuse vite.
5
Bien choisir sa structure de données, ce n'est donc pas un détail : cela peut faire passer un algorithme de O(n carré) à O(n).

Objectif Bac

Objectif Bac : face à une situation décrite en français, choisir la structure (liste, pile, file ou dictionnaire) et JUSTIFIER le choix par le coût des opérations dominantes.
Objectif Bac : implémenter une structure au moyen d'une autre (par exemple une file à l'aide d'une liste) et en commenter le coût.
Objectif Bac : construire la justification en quatre temps — opération dominante, nombre d'exécutions, coût unitaire par structure, total comparé — et non par une préférence qualitative.
Objectif Bac : implémenter une file au moyen d'une liste, puis commenter honnêtement le coût obtenu et proposer l'implémentation qui le corrige.
Objectif Bac : traduire une contrainte de l'énoncé (ordre d'arrivée, absence de doublon, accès par identifiant) en propriété de structure avant d'écrire la moindre ligne de code.

Erreurs fréquentes

Choisir une structure « par habitude » (toujours une liste) sans regarder l'opération dominante : une recherche par clé répétée dans une liste donne O(n) par requête, là où un dictionnaire donne O(1) en moyenne.
Justifier un choix sans argument de coût : dire « c'est plus pratique » ne suffit pas, il faut comparer les complexités des opérations critiques.
Comparer des structures sur le coût d'une opération qui n'est pas dominante : si l'algorithme fait un seul accès par indice et un million de recherches par clé, le coût de l'accès par indice ne pèse rien.
Confondre le coût d'une opération et le coût de l'algorithme : passer de O(n) à O(1) sur une opération exécutée n fois fait passer l'algorithme de O(n²) à O(n) — c'est ce total qu'il faut annoncer.

Révision active

Un logiciel doit gérer les travaux envoyés à une imprimante (traités dans l'ordre d'arrivée) et retrouver instantanément, à partir d'un identifiant de travail, son propriétaire. Quelles structures de données choisissez-vous pour chaque besoin ? Justifiez par le coût des opérations.

S’entraîner sur des exercices associés50 questions sur ce thème

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Annexe de l'arrêté du 19-7-2019 (NOR MENE1921247A) — programme de spécialité NSI, classe terminale (BO spécial n° 8 du 25 juillet 2019) (Ministère de l'Éducation nationale)

Points clés

Spécifier l'interface d'une pile, indépendamment de l'implémentation

Points clés

Insertion en tête d'une liste chaînée

Points clés

Dérouler une suite d'opérations sur une pile puis sur une file

Vérifier le bon parenthésage avec une pile

Points clés

Compter les occurrences des lettres d'un mot avec un dictionnaire

Points clés

Choisir et justifier les structures d'une file d'impression

Sources

Structures de données linéaires

Points clés

Spécifier l'interface d'une pile, indépendamment de l'implémentation

Points clés

Insertion en tête d'une liste chaînée

Points clés

Dérouler une suite d'opérations sur une pile puis sur une file

Vérifier le bon parenthésage avec une pile

Points clés

Compter les occurrences des lettres d'un mot avec un dictionnaire

Points clés

Choisir et justifier les structures d'une file d'impression

Sources