Numérique et sciences informatiques (NSI) · Terminale

Fiche de révision : listes, piles, files et dictionnaires

L’essentiel à connaître, sur une seule page. Imprime-la ou enregistre-la en PDF.

ULUMINE · Numérique et sciences informatiques (NSI) · Terminale

Listes, piles, files et dictionnaires

Les structures linéaires se distinguent par leur interface : où l’on ajoute, où l’on retire, comment on accède aux éléments.

Piles et files

  • Pile (LIFO) : empiler, dépiler au sommet. En Python : append et pop().
  • File (FIFO) : enfiler à la fin, défiler au début. Éviter pop(0) ; utiliser deux piles ou deque.
  • Pile : annuler, appels de fonctions, parenthèses. File : impression, parcours en largeur.

Listes chaînées

  • Maillon = valeur + référence vers le suivant (None à la fin).
  • Ajout en tête en temps constant ; accès au k-ième élément en parcourant k maillons.

Dictionnaires

  • Couples clé → valeur, clés uniques et non modifiables.
  • d[cle], cle in d, d.get(cle, defaut), for cle in d.
  • Recherche par clé en temps constant en moyenne.

Pièges à éviter

  • Confondre l’ordre de sortie d’une pile et d’une file.
  • Dépiler une pile vide (IndexError).
  • Lire d[cle] pour une clé absente (KeyError) : tester avant ou utiliser get.
  • Utiliser une liste comme clé de dictionnaire.

À découvrir aussi