Listes chaînées, piles et files

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