Structures linéaires : listes chaînées, piles et files — opérations et complexité

En 30 secondes

• Liste chaînée : nœuds reliés en chaîne, accès à un nœud quelconque en O(n) (parcours depuis le début).
• Pile (LIFO) : empiler/dépiler au sommet uniquement, en O(1). File (FIFO) : enfiler à la queue, défiler à la tête, en O(1).
• La complexité O(...) compte le nombre d'opérations élémentaires en fonction de n, dans le pire des cas.

Ce que tu sauras faire

• Décrire le fonctionnement d'une liste chaînée et de ses opérations de base.
• Distinguer le comportement d'une pile de celui d'une file, et connaître leurs opérations.
• Évaluer la complexité algorithmique des opérations sur ces trois structures linéaires.

Les mots à connaître

Liste chaînée

une structure de données linéaire où chaque élément (nœud) contient une valeur et un lien vers le nœud suivant ; l'accès à un nœud se fait en parcourant les liens un par un depuis le premier nœud.

Nœud

l'élément de base d'une liste chaînée ou d'un arbre, qui stocke une valeur et un ou plusieurs liens vers d'autres nœuds.

Pile

une structure linéaire où l'on n'ajoute et ne retire des éléments que par une seule extrémité, appelée le sommet ; le dernier élément empilé est le premier dépilé (comportement LIFO, « dernier entré, premier sorti »).

Le piège classique

Confondre le comportement LIFO d'une pile (dernier entré, premier sorti) avec le comportement FIFO d'une file (premier entré, premier sorti).

L'astuce

Pile = LIFO = pile d'assiettes : on pose et on retire toujours par le dessus (le sommet).