Comment est composé un maillon d'une liste chaînée ?

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.

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 ?

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 ?

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 ?

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 :

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.

NSI (Spé) — Structures de données

Listes chaînées, piles et files

Q: Quel est le mode de fonctionnement d'une pile ?

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.

Q: Quelle est la complexité de l'accès au i-ème élément dans une liste chaînée ?

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.

Q: Quelle structure utilise-t-on pour un parcours en largeur (BFS) ?

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.

Q: Quelle opération est en O(n) avec une implémentation naïve de file par liste Python ?

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().

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é

Les structures de données linéaires sont fondamentales en informatique. Une liste chaînée est constituée de maillons, chacun contenant une valeur et une référence vers le maillon suivant (ou None pour le dernier). Contrairement aux tableaux Python, l'insertion en tête d'une liste chaînée est en O(1), mais l'accès au i-ème élément est en O(n). Une pile (stack) fonctionne en mode LIFO (Last In, First Out) : on empile (push) et on dépile (pop) par le sommet, comme une pile d'assiettes. Une file (queue) fonctionne en mode FIFO (First In, First Out) : on enfile par l'arrière et on défile par l'avant, comme une file d'attente à la boulangerie. Ces structures sont implémentées en Python à l'aide de classes avec des méthodes spécifiques (empiler/depiler pour la pile, enfiler/defiler pour la file).

Articles utiles

Spécialités

Bac NSI 2026 : comment réussir l'épreuve écrite et pratique

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().

Résumé

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().

Listes chaînées, piles et files

Résumé