NSI (Spé) — Structures de données
Listes chaînées, piles et files
Structures de données linéaires : listes chaînées, piles (LIFO), files (FIFO), implémentation en Python
Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
Comment ranger des données quand on ignore combien elles seront, et dans quel ordre on devra les ressortir ? Trois structures linéaires y répondent différemment. La liste chaînée enchaîne des maillons reliés par des références : insérer en tête coûte $O(1)$, mais atteindre le i-ème élément coûte $O(n)$. La pile (LIFO, Last In First Out) ne donne accès qu'à son sommet, comme une pile d'assiettes ou le Ctrl+Z. La file (FIFO, First In First Out) sert dans l'ordre d'arrivée, comme une file d'attente. Maîtriser ces trois structures, c'est savoir choisir la bonne boîte de rangement selon la façon dont on devra ressortir les données — et c'est le socle des arbres, des graphes et des parcours qui suivront.
Dans un tableau, les éléments sont rangés côte à côte en mémoire. Une liste chaînée, elle, les éparpille : chaque maillon stocke une valeur et une référence vers le maillon suivant. On ne connaît que la tête ; pour atteindre le reste, on suit la chaîne de référence en référence.
- Un maillon (nœud) contient une valeur et une référence vers le maillon suivant — ou None pour le dernier.
- On accède à la liste par sa tête ; le dernier maillon pointe vers None, qui marque la fin.
- Insertion / suppression en tête : $O(1)$ — on ne touche qu'à la référence de tête.
- Accès au i-ème élément : $O(n)$ — il faut parcourir $i$ maillons depuis la tête.
- Liste vs tableau : le tableau offre l'accès direct par indice en $O(1)$ ; la liste chaînée, l'insertion en tête en $O(1)$.
Exemple
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
# Insertion en tête, en O(1)
tete = Maillon(10)
tete = Maillon(5, tete) # 5 -> 10 -> None
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
# Insertion en tête, en O(1)
tete = Maillon(10)
tete = Maillon(5, tete) # 5 -> 10 -> None
Piège à éviter
Lors d'une insertion ou d'une suppression en tête, oublier de mettre à jour la référence de tête fait perdre l'accès à toute la liste. Mets toujours la tête à jour en dernier.
Une pile (stack) n'autorise qu'un seul point d'accès : son sommet. On empile (push) au sommet et on dépile (pop) au sommet. Le dernier arrivé est donc le premier servi — c'est le mode LIFO, Last In, First Out, comme une pile d'assiettes qu'on prend par le haut.
La pile (LIFO) ne travaille que par le sommet ; la file (FIFO) entre par l'arrière et sort par l'avant.
- LIFO : le dernier élément empilé est le premier dépilé.
- Opérations : empiler(x) (push), dépiler() (pop), sommet() (peek), est_vide().
- Implémentation simple avec une liste Python : empiler = append, dépiler = pop() — toutes en $O(1)$.
- Exemples : la pile d'appels des fonctions, le Ctrl+Z (annuler), l'évaluation d'expressions.
- Toutes les opérations sont en $O(1)$.
Exemple
class Pile:
def __init__(self):
self._elements = []
def empiler(self, x):
self._elements.append(x)
def depiler(self):
return self._elements.pop() # retire le sommet
def est_vide(self):
return self._elements == []
def __init__(self):
self._elements = []
def empiler(self, x):
self._elements.append(x)
def depiler(self):
return self._elements.pop() # retire le sommet
def est_vide(self):
return self._elements == []
Piège à éviter
Dépiler une pile vide lève une erreur (IndexError). Teste toujours est_vide() avant d'appeler depiler().
Une file (queue) sert dans l'ordre d'arrivée : on enfile par l'arrière et on défile par l'avant. Le premier arrivé est le premier servi — c'est le mode FIFO, First In, First Out, comme la file d'attente à la boulangerie.
- FIFO : le premier élément enfilé est le premier défilé.
- Opérations : enfiler(x) (enqueue), défiler() (dequeue), premier(), est_vide().
- Implémentation naïve avec une liste : enfiler = append, défiler = pop(0) — mais pop(0) est en $O(n)$ (décalage de tous les éléments).
- Implémentation efficace avec collections.deque : défiler = popleft() en $O(1)$.
- Exemples : file d'impression, tampon réseau, parcours en largeur (BFS).
Exemple
from collections import deque
file = deque()
file.append('A') # enfiler par l'arrière
file.append('B')
file.popleft() # défile 'A' (le premier arrivé), en O(1)
file = deque()
file.append('A') # enfiler par l'arrière
file.append('B')
file.popleft() # défile 'A' (le premier arrivé), en O(1)
Piège à éviter
Ne confonds pas pile et file : la pile retire par le sommet (le dernier arrivé), la file retire par l'avant (le premier arrivé). Utiliser pop(0) sur une grande liste dégrade les performances en $O(n)$.
Piles et files sont des types abstraits : on les définit par leurs opérations, pas par leur réalisation interne. C'est le principe d'abstraction — l'utilisateur manipule empiler/dépiler sans savoir si, dessous, c'est un tableau ou une liste chaînée.
- On encapsule données et opérations dans une classe (class Pile, class File).
- L'interface (méthodes publiques) est séparée de l'implémentation interne.
- Une pile peut reposer sur un tableau ou une liste chaînée.
- Une file peut reposer sur deux piles, une liste chaînée ou un tableau circulaire.
- Le choix d'implémentation ne change pas l'interface : c'est tout l'intérêt de l'abstraction.
- Invariant de structure : après chaque opération, la structure reste cohérente (taille à jour, références valides).
Exemple
Une file avec deux piles : on empile les arrivées sur une pile « entrée ». Pour défiler, si la pile « sortie » est vide, on y bascule toute la pile « entrée » (l'ordre s'inverse), puis on dépile. Chaque élément ne transite qu'une fois : coût amorti $O(1)$.
Piège à éviter
Changer l'implémentation ne doit jamais obliger à réécrire le code qui utilise la structure. Si c'est le cas, c'est que l'abstraction (l'interface) a fui.
Quiz - Listes chaînées, piles et files
10 questions
S'entraîner
- Quiz : Listes chaînées, piles et files10 questions corrigées sur ce chapitre
- Bac 2026 NSI – MétropoleSujet officiel
- Bac 2025 NSI – MétropoleSujet officiel
- Bac 2024 NSI – MétropoleSujet officiel
- Annales du bac de NSITous les sujets officiels, par année
- Coefficient de NSI au bacPoids de l'épreuve dans la note finale
Articles utiles
Questions fréquentes
Les points clés à retenir sur Listes chaînées, piles et files, extraits du quiz de révision.
Quel est le mode de fonctionnement d'une pile ?
Réponse :
LIFO
Une pile fonctionne en mode LIFO (Last In, First Out) : le dernier élément ajouté est le premier retiré, comme une pile d'assiettes.
Quelle est la complexité de l'accès au i-ème élément dans une liste chaînée ?
Réponse :
O(n)
Dans une liste chaînée, il faut parcourir les maillons un par un depuis la tête, ce qui donne une complexité O(n) pour accéder au i-ème élément.
Quelle structure utilise-t-on pour un parcours en largeur (BFS) ?
Réponse :
Une file
Le parcours en largeur (BFS) utilise une file (FIFO) pour traiter les nœuds dans l'ordre où ils ont été découverts.
Quelle opération est en O(n) avec une implémentation naïve de file par liste Python ?
Réponse :
defiler (pop(0))
pop(0) sur une liste Python est en O(n) car tous les éléments doivent être décalés d'un cran vers la gauche. Il vaut mieux utiliser collections.deque avec popleft().
Comment est composé un maillon d'une liste chaînée ?
Réponse :
Une valeur et une référence vers le maillon suivant
Un maillon contient une valeur (la donnée) et une référence (pointeur) vers le maillon suivant, ou None s'il est le dernier.
Que signifie FIFO ?
Réponse :
First In, First Out
FIFO signifie First In, First Out : le premier élément entré est le premier sorti, comme dans une file d'attente.
Quelle est la complexité de l'insertion en tête d'une liste chaînée ?
Réponse :
O(1)
L'insertion en tête est en O(1) : on crée un nouveau maillon qui pointe vers l'ancienne tête, puis on met à jour la tête.
Le mécanisme Ctrl+Z (annuler) est modélisé par quelle structure ?
Réponse :
Une pile
Le Ctrl+Z utilise une pile : chaque action est empilée, et annuler revient à dépiler la dernière action (LIFO).
Quelle méthode Python permet de défiler efficacement avec collections.deque ?
Réponse :
popleft()
collections.deque.popleft() retire le premier élément en O(1), contrairement à list.pop(0) qui est en O(n).
Une file peut être implémentée avec :
Réponse :
Deux piles
On peut implémenter une file avec deux piles : une pile d'entrée pour enfiler et une pile de sortie pour défiler. Quand la pile de sortie est vide, on transfère la pile d'entrée dedans.