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
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.
- **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 == []
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)
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
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().