On choisit une structure d'après l'ordre de sortie attendu : dernier entré premier sorti pour une pile, premier entré premier sorti pour une file.
L'erreur que tout le monde fait
Supposer qu'accéder au i-ième élément d'une liste chaînée coûte autant que dans un tableau.
Un tableau connaît l'adresse de chaque case et y accède directement ; une liste chaînée doit partir du premier maillon et suivre les liens un par un. L'accès direct est immédiat dans un cas, proportionnel à la position dans l'autre, et c'est précisément l'inverse pour l'insertion en tête.
Se demander ce que le programme fera le plus : accéder par indice, ou insérer et supprimer.
Une pile d'assiettes et une file d'attente contiennent les mêmes objets et n'en rendent pas le même en premier. On choisit une structure d'après l'ordre dans lequel les choses doivent ressortir.
1Deux structures aux ordres opposés
Règle
Une pile fonctionne en LIFO — last in, first out : le dernier entré est le premier sorti. Ses deux opérations sont empiler et dépiler, toutes deux sur le sommet. Une file fonctionne en FIFO — first in, first out : le premier entré est le premier sorti. On enfile à une extrémité et on défile à l'autre. Le choix se fait donc d'après l'ordre de sortie attendu, jamais d'après le contenu.
pile:LIFO⋅file:FIFO
Propriété
Chacune correspond à des usages précis. La pile sert partout où il faut revenir en arrière dans l'ordre inverse : annulation d'actions, historique de navigation, évaluation d'expressions parenthésées, et la pile d'appels d'un programme. La file sert partout où il faut traiter dans l'ordre d'arrivée : file d'impression, gestion de requêtes, parcours en largeur d'un graphe.
2Tableau ou liste chaînée
Définition
Liste chaînée — Une liste chaînée est une suite de cellules dont chacune contient une valeur et une référence vers la suivante. À la différence d'un tableau, ses éléments ne sont pas contigus en mémoire : on ne peut donc pas sauter directement au i-ième, il faut parcourir depuis le début. En contrepartie, insérer ou supprimer au milieu ne demande que de modifier deux références, sans décaler quoi que ce soit.
Piège
Supposer qu'accéder au i-ième élément d'une liste chaînée coûte autant que dans un tableau.
Pourquoi — Dans un tableau, l'adresse du i-ième élément se calcule : l'accès est en O(1). Dans une liste chaînée, il faut suivre les références une par une : l'accès est en O(n). Écrire une boucle qui accède à l'indice i à chaque tour transforme donc un parcours en O(n) en un parcours en O(n²), sans que rien dans le code ne le signale.
Le réflexe — Pour parcourir une liste chaînée, suivre les références, jamais les indices.
Le compromis est symétrique et c'est ce qui rend le choix intéressant. Le tableau donne un accès direct et une insertion coûteuse — il faut décaler. La liste chaînée donne une insertion locale bon marché et un accès coûteux. Aucune n'est meilleure : la question est de savoir quelle opération sera la plus fréquente dans le programme.
3Dictionnaires et hachage
Définition
Dictionnaire — Un dictionnaire associe des clés à des valeurs. Il repose sur une table de hachage : une fonction transforme la clé en un indice dans un tableau interne, ce qui permet d'accéder à la valeur sans parcourir la structure. L'accès est donc en O(1) en moyenne — et non dans tous les cas : si plusieurs clés produisent le même indice, il y a collision, et la structure doit les départager.
Deux conséquences pratiques. Une clé doit être immuable : si l'objet servant de clé changeait, son hachage changerait et la valeur deviendrait introuvable — c'est pourquoi une liste ne peut pas servir de clé. Et la performance annoncée est une moyenne : une fonction de hachage mal choisie concentre les collisions et fait retomber l'accès vers O(n).
4Les arbres
Définition
Arbre binaire — Un arbre binaire est une structure hiérarchique où chaque nœud possède au plus deux enfants. Le nœud sans parent est la racine ; les nœuds sans enfant sont les feuilles. La profondeur d'un nœud est sa distance à la racine ; la hauteur de l'arbre est la profondeur maximale. Un arbre équilibré de n nœuds a une hauteur de l'ordre de log n — ce qui explique l'efficacité des recherches qu'on y mène.
Un arbre binaire dégénéré, où chaque nœud n'a qu'un seul enfant, n'est rien d'autre qu'une liste chaînée déguisée : sa hauteur vaut n, et toute recherche y redevient linéaire. C'est pourquoi les structures d'arbres utilisées en pratique maintiennent leur équilibre lors des insertions : l'efficacité annoncée dépend entièrement de cette propriété.
Choisir la structure adaptée à un problème
Déterminer l'ordre de sortie attendu : le dernier arrivé, le premier arrivé, ou un accès quelconque ?
Recenser les opérations fréquentes : accès par indice, par clé, insertion, suppression, parcours.
Confronter chaque opération au coût de la structure envisagée.Accès par indice : O(1) en tableau, O(n) en liste chaînée.
Vérifier les contraintes : mémoire disponible, taille connue ou variable, clés immuables.
Conclure en nommant la structure et l'opération qui a décidé du choix.
▢Ai-je choisi d'après l'ordre de sortie et non d'après le contenu ?
▢LIFO pour une pile, FIFO pour une file : ai-je vérifié ?
▢Ai-je évité d'accéder par indice dans une liste chaînée ?
▢Ai-je dit que l'accès d'un dictionnaire est O(1) en moyenne ?
▢Mes clés de dictionnaire sont-elles immuables ?
▢Ai-je vérifié qu'un arbre binaire est équilibré avant d'annoncer log n ?
L'essentiel en 11 points
·On choisit une structure d'après l'ordre de sortie et le coût des opérations.
·Pile : LIFO, dernier entré premier sorti. File : FIFO.
a.Différencier LIFO et FIFO. À quelle structure chacun correspond-il ?
b.Qu'est-ce qu'une liste chaînée ? En quoi diffère-t-elle d'un tableau ?
c.Sur quoi repose un dictionnaire ? Quel est le coût d'un accès ?
d.Définir racine, feuille, profondeur et hauteur dans un arbre binaire.
e.Qu'est-ce qu'une collision de hachage ?
›Voir le corrigéMasquer le corrigé
a. LIFO : dernier entré, premier sorti — la pile. FIFO : premier entré, premier sorti — la file.
b. Une suite de cellules contenant chacune une valeur et une référence vers la suivante. Ses éléments ne sont pas contigus en mémoire, contrairement au tableau.
c. Sur une table de hachage. L'accès est en O(1) en moyenne, pas dans tous les cas.
d. La racine est le nœud sans parent ; une feuille n'a pas d'enfant ; la profondeur est la distance d'un nœud à la racine ; la hauteur est la profondeur maximale.
e. Le cas où deux clés différentes produisent le même indice dans le tableau interne.
2
On empile successivement 3, 7, 2, 9 dans une pile, puis on dépile deux fois. On enfile les mêmes valeurs dans une file, puis on défile deux fois.
Appliquer
a.Quelles valeurs sort-on de la pile, et dans quel ordre ?
b.Que reste-t-il dans la pile ?
c.Quelles valeurs sort-on de la file, et dans quel ordre ?
d.Que reste-t-il dans la file ?
e.Quelle structure choisir pour un historique de navigation ? Pour une file d'impression ?
›Voir le corrigéMasquer le corrigé
a. 9 puis 2 : la pile rend le dernier entré en premier.
b. 3 et 7, le sommet étant désormais le 7.
c. 3 puis 7 : la file rend le premier entré en premier.
d. 2 et 9, dans cet ordre.
e. Une pile pour l'historique de navigation — revenir en arrière dans l'ordre inverse. Une file pour l'impression — traiter dans l'ordre d'arrivée.
3
Un développeur parcourt une liste chaînée de n éléments avec une boucle qui accède à l'indice i à chaque tour. Analyser.
Analyser
a.Quel est le coût d'un accès à l'indice i dans une liste chaînée ?
b.Quelle est alors la complexité totale de ce parcours ?
c.Quelle aurait été la complexité avec un parcours par références ?
d.Pourquoi cette erreur est-elle difficile à repérer dans le code ?
e.Le même code sur un tableau aurait-il ce défaut ?
›Voir le corrigéMasquer le corrigé
a. O(n) : il faut suivre les références depuis le début, aucun calcul d'adresse n'est possible.
b. O(n²) : n tours de boucle, chacun coûtant O(n).
c. O(n) : en conservant la référence courante et en passant à la suivante, chaque élément n'est atteint qu'une fois.
d. Parce que le code est lisible et correct : il produit le bon résultat. Seule la performance diffère, et elle ne se voit que sur de grandes entrées. Rien dans la syntaxe ne signale que l'accès par indice est coûteux ici.
e. Non. Dans un tableau, l'adresse du i-ième élément se calcule : l'accès est en O(1), et le parcours reste en O(n). C'est le même code avec deux coûts différents — d'où l'importance de savoir sur quelle structure on travaille.
4
Dictionnaires et arbres. Raisonner.
Raisonner
a.Pourquoi une clé de dictionnaire doit-elle être immuable ?
b.Pourquoi l'accès n'est-il en O(1) qu'en moyenne ?
c.Quelle est la hauteur d'un arbre binaire équilibré de n nœuds ?
d.Que devient un arbre dont chaque nœud n'a qu'un seul enfant ?
e.Que faut-il retenir de ces deux cas sur les performances annoncées ?
›Voir le corrigéMasquer le corrigé
a. Parce que son hachage détermine l'emplacement de la valeur. Si la clé changeait, son hachage changerait et la valeur deviendrait introuvable — c'est pourquoi une liste ne peut pas servir de clé.
b. À cause des collisions : si plusieurs clés produisent le même indice, la structure doit les départager. Une fonction de hachage mal choisie concentre les collisions et fait retomber l'accès vers O(n).
c. De l'ordre de log n — c'est ce qui rend les recherches efficaces.
d. Une liste chaînée déguisée : sa hauteur vaut n, et toute recherche y redevient linéaire.
e. Qu'une performance annoncée repose toujours sur une hypothèse — hachage bien réparti, arbre équilibré — et qu'elle s'effondre quand l'hypothèse tombe. Retenir « un dictionnaire, c'est O(1) » sans retenir la condition revient à retenir la moitié de l'énoncé.
Ce qui rapporte des points, ce qui en coûte
Distinguer LIFO et FIFO et leurs usages4 ptsPerdu si : Choisir une structure d'après son contenu
Comparer tableau et liste chaînée par les coûts5 ptsPerdu si : Accéder par indice dans une liste chaînée
Expliquer le hachage et la réserve « en moyenne »4 ptsPerdu si : Annoncer O(1) sans condition
Justifier l'immuabilité des clés3 ptsPerdu si : Employer une liste comme clé
Relier hauteur d'arbre et efficacité4 ptsPerdu si : Annoncer log n pour un arbre quelconque
4
La méthode
Choisir la structure adaptée à un problème
1
Recenser les opérations dont le programme a besoin : ajouter, retirer, chercher, parcourir.
2
Préciser l'ordre de sortie attendu et l'endroit où les éléments entrent et sortent.
3
Estimer le coût de chaque opération pour les structures candidates.
Un dictionnaire retrouve une valeur par sa clé sans parcourir l'ensemble des entrées.
4
Vérifier que la structure retenue interdit les opérations que le problème ne doit pas permettre.
5
Écrire les primitives choisies et tester le comportement sur une structure vide.
5
Se tester
Touches 1 à 4
NSIPremière
Question 1
Voici un extrait de code Python simulant une liste chaînée. Quelle est la valeur de `valeur` après l'exécution ?
```python
class Noeud:
def __init__(self, valeur):
self.valeur = valeur
self.suivant = None
n1 = Noeud(10)
n2 = Noeud(20)
n3 = Noeud(30)
n1.suivant = n2
n2.suivant = n3
valeur = n1.suivant.suivant.valeur
```
Aucun compte requis — réponds, la correction s'affiche aussitôt.
Structures de données — Listes, piles, files : c'est en quelle classe ?+
Ce chapitre est au programme de NSI au lycée, en classe de Première, année du Bac de français. Il est défini par le Bulletin Officiel de l'Éducation nationale, le texte de référence qui fixe ce qui doit être enseigné dans chaque matière.
Que faut-il savoir sur Structures de données — Listes, piles, files ?+
Tableau, liste chaînée. Pile (LIFO) : push/pop. File (FIFO) : enqueue/dequeue. Dictionnaire (table de hachage). Arbre binaire : nœud, racine, feuille, profondeur, hauteur. Les notions à maîtriser sont : pile, file, liste chaînée, dictionnaire, arbre binaire, LIFO.
Où télécharger la fiche PDF de Structures de données — Listes, piles, files ?+
Sur cette page, dans le bloc « Imprimer » : 3 documents à télécharger — le cours, les exercices et le corrigé — soit 6 pages au format A4, prêtes à imprimer. Le téléchargement est gratuit, immédiat, et ne demande ni compte ni adresse e-mail.
Le corrigé de Structures de données — Listes, piles, files est-il fourni ?+
Oui, et c'est un document à part : chaque exercice y est repris étape par étape, avec le barème détaillé en fin de fiche — ce qui est attendu, combien de points, et ce qui fait perdre le point. Un parent qui ne se souvient plus du programme peut corriger une copie avec.
Structures de données — Listes, piles, files peut-il tomber au Bac de français ?+
Ce chapitre fait partie du programme officiel de Première, il entre donc dans le périmètre du Bac de français. Le sujet exact varie chaque année et aucun chapitre n'est garanti, mais l'ensemble du programme de l'année est susceptible d'être évalué : mieux vaut ne pas parier sur des impasses.
Commence par lire la fiche de révision pour remettre la règle en place, puis enchaîne immédiatement sur le quiz de cette page. Répondre juste après avoir lu ne suffit pas : reviens sur le chapitre deux ou trois jours plus tard. C'est l'espacement des révisions, plus que leur durée, qui fait tenir une notion en mémoire. Une session de quinze minutes répétée vaut mieux qu'une heure unique.
Faut-il un compte pour s'entraîner sur Structures de données — Listes, piles, files ?+
Non. Les quiz, les corrections détaillées et les fiches de révision sont accessibles sans créer de compte et sans donner d'adresse e-mail. Le compte gratuit sert uniquement à conserver la progression d'un appareil à l'autre.
Notions voisines
Les chapitres qui traitent des mêmes notions, ici ou dans une autre année.