Numérique et sciences informatiques (spécialité) · TerminaleBac
Listes chaînées : quiz de Terminale NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
- Une liste chaînée est une suite de cellules, chacune contenant une donnée et un pointeur vers une autre cellule.2
- Liste simplement chaînée : un pointeur vers le suivant, parcours dans un seul sens. Liste doublement chaînée : successeur et prédécesseur, parcours dans les deux sens.3
- Contrairement à un tableau, sa taille n'est limitée que par la mémoire disponible : on crée une cellule et on la fait pointer.3
- Elle convient quand l'ordre compte et que les insertions et suppressions sont plus fréquentes que les accès.2
- Le double chaînage coûte un pointeur de plus par élément et davantage d'instructions à chaque mise à jour.2
Avant de commencer
Ce quiz porte sur les listes chaînées : leur structure en mémoire, la différence entre liste simplement et doublement chaînée, la liste circulaire, le coût d'une insertion, les situations où elles sont adaptées, et quelques points d'histoire. Tu y retrouveras aussi des réflexes de test à avoir quand tu écris une fonction qui manipule une liste.
Les notions vues juste avant sont celles de la programmation orientée objet : une cellule se représente naturellement par un objet qui possède un attribut pour la donnée et un attribut pour la cellule suivante.
Quiz
14 questions · correction immédiate · ton score reste sur ton appareil.
-
Chaque maillon de la chaîne associe une donnée à un pointeur qui désigne une autre cellule.2 C'est ce pointeur qui relie les maillons entre eux. La réponse « uniquement la donnée » est tentante parce qu'on pense d'abord à ce qu'on veut stocker, mais sans pointeur il n'y aurait plus de chaîne : on aurait des valeurs isolées. Aucune cellule ne stocke l'indice de sa position ni les autres cellules.
-
C'est faux. La contiguïté en mémoire est la caractéristique d'un tableau, ce qui impose une taille fixe.3 Dans une liste chaînée, c'est le pointeur qui indique où se trouve la cellule suivante : elle peut être rangée n'importe où. L'erreur tentante vient de l'image du collier : les maillons sont liés logiquement, pas nécessairement voisins dans la mémoire.
-
Chaque élément d'une liste simplement chaînée dispose d'un pointeur sur son successeur seulement, donc le parcours se fait dans un seul sens.3 Le parcours dans les deux sens est la propriété de la liste doublement chaînée, qui est la confusion la plus fréquente. Quant à l'accès dans n'importe quel ordre sans suivre de pointeur, il ressemble à l'accès par indice d'un tableau, pas à ce qu'offre une chaîne.
-
Chaque élément d'une liste doublement chaînée possède deux pointeurs : l'un sur le successeur, l'autre sur le prédécesseur.3 Un seul pointeur correspond à la liste simplement chaînée. Il n'existe pas de pointeur « premier » dans la définition, et le nombre de pointeurs par cellule ne dépend pas de la longueur de la liste.
-
Chaque élément dispose de deux pointeurs, successeur et prédécesseur.3 Pour 6 cellules : . L'erreur tentante est de répondre 6 (un pointeur par cellule, comme dans une liste simplement chaînée) ou 5 (le nombre de liens entre cellules voisines). Ici on compte les pointeurs portés par les cellules, pas les liens visibles sur le dessin.
-
Contrairement à un tableau, la taille d'une liste chaînée est limitée seulement par la mémoire disponible, et l'on agrandit la liste en créant un nouvel élément vers lequel on fait pointer un élément déjà présent.3 La taille fixe est une propriété des tableaux, dont les données sont contiguës.3 La recopie complète est précisément ce que le chaînage permet d'éviter : on modifie quelques pointeurs, pas toute la structure.
-
C'est vrai : cette structure est plus coûteuse en mémoire, avec un pointeur supplémentaire par élément.2 On pourrait croire que la possibilité de parcourir dans les deux sens est gratuite, mais elle se paie par ce second pointeur dans chaque cellule, et aussi par plus d'instructions lors des mises à jour.
-
Une insertion coûte quatre copies de pointeurs dans une liste doublement chaînée, contre deux dans le cas d'une liste simplement chaînée.2 La réponse 2 est celle de la liste simple, donc c'est l'erreur tentante. On peut la retrouver par le raisonnement : le nouvel élément reçoit deux pointeurs, et ses deux voisins doivent en recevoir un chacun, ce qui fait bien écritures.
-
On recommande souvent la liste chaînée pour sa rapidité de traitement lorsque l'ordre est important et que l'on insère ou supprime des éléments quelconques plus souvent qu'on n'y accède.2 Pour des accès fréquents ou une taille connue et fixe, un tableau convient mieux. Et la liste chaînée n'économise pas la mémoire : chaque élément porte au moins un pointeur en plus de sa donnée.2
-
Dans une liste avec cycle, la chaîne forme une boucle : en continuant après la « fin », on se retrouve sur le premier élément, et la notion de début ou de fin n'a plus de raison d'être.3 Le cycle est une propriété qui s'ajoute aux deux grands types de listes chaînées, donc une liste simplement chaînée peut aussi être circulaire. Le tri n'a aucun rapport avec la forme de la chaîne.
-
C'est au milieu des années 1950 (1955-1956) que trois chercheurs de la RAND Corporation, Allen Newell, Cliff Shaw et Herbert Simon, ont imaginé cette structure.2 Elle servait de brique de base à leur langage IPL, employé pour des programmes d'intelligence artificielle.2 Les autres dates sont tentantes parce qu'on associe souvent les structures de données à des langages récents, mais celle-ci est bien plus ancienne.
-
Lisp vient de l'anglais « list processing », ce qui illustre l'importance de la liste comme type de données.3 Les autres propositions sonnent plausible, notamment « linked storage » à cause de notre sujet, mais elles ne correspondent pas à l'origine du nom.
-
C'est vrai : la liste regroupe des données de manière à pouvoir y accéder librement, alors que l'accès aux files se fait en mode FIFO et celui des piles en mode LIFO.3 On retient donc que la pile et la file sont des structures plus contraintes, qui seront étudiées juste après. La liste sert d'ailleurs de base à ces types plus complexes.3
-
Pour tester les postconditions d'une fonction, il faut envisager les cas particuliers : liste vide, liste unitaire, doublons, nombres négatifs, flottants.1 Pour une liste chaînée, la liste vide est le piège classique : il n'y a alors aucune première cellule vers laquelle pointer. Une liste de taille infinie n'est pas un cas à tester : la mémoire est finie, et c'est elle qui limite la taille.3
Les questions qu'on se pose
Quelle différence entre une liste chaînée et un tableau ?
Les données d'un tableau sont contiguës en mémoire, ce qui impose une taille fixe.3 Une liste chaînée est une suite de cellules reliées par des pointeurs, sa taille n'est limitée que par la mémoire disponible, et l'on l'agrandit en créant une cellule et en la reliant à la chaîne.3 En contrepartie, chaque cellule coûte un pointeur de plus.2
Que dois-je savoir pour le Bac sur les listes chaînées ?
Sache décrire une cellule (donnée et pointeur), distinguer liste simplement et doublement chaînée, expliquer pourquoi elle est adaptée quand les insertions et suppressions dominent, et justifier le choix d'une structure pour un exercice.12 Pense aussi à tester les cas particuliers, en premier lieu la liste vide.1
Sources
- Ressources IREM - Structures de données NSI, Académie de Lyon. Consulté le 7 novembre 2026.
- Liste chaînée, Wikipédia. Consulté le 7 novembre 2026.
- Liste (informatique), Wikipédia. Consulté le 7 novembre 2026.
Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.