Implémentation de structures de données en C++ : listes chaînées, piles et files

En Terminale NSI, vous manipulez déjà les tableaux. Mais les tableaux ont une taille fixe et l'insertion au milieu coûte cher. Les listes chaînées, piles et files sont des structures linéaires dynamiques qui s'appuient sur l'allocation mémoire avec new et delete. Un pointeur stocke l'adresse d'une variable ou d'un objet. Grâce aux pointeurs, on peut chaîner des éléments entre eux sans les déplacer en mémoire. Comprendre ces mécanismes est essentiel pour implémenter des algorithmes efficaces.

Une liste chaînée est une suite de nœuds. Chaque nœud contient une valeur et un pointeur vers le nœud suivant. La liste est repérée par un pointeur vers sa tête ; le dernier nœud pointe vers nullptr. Pour insérer en tête, on crée un nœud, on fait pointer son suivant vers l'ancienne tête, puis on met à jour la tête. La suppression en tête consiste à avancer la tête puis libérer l'ancien nœud. Ces opérations sont en O(1), contrairement aux tableaux où il faut décaler les éléments.

Une pile est une structure où le dernier élément inséré est le premier retiré (LIFO). Les opérations fondamentales sont empiler (push), dépiler (pop) et consulter le sommet (top). On peut implémenter une pile avec un tableau ou une liste chaînée. Avec une liste chaînée, on insère et supprime toujours en tête : push ajoute en tête, pop retire la tête. Cela garantit des opérations en O(1). La pile sert par exemple à gérer l'historique des actions dans un éditeur.

Une file est une structure où le premier élément inséré est le premier retiré (FIFO). Les opérations sont enfiler (enqueue) en queue et défiler (dequeue) en tête. Avec une liste chaînée, on maintient deux pointeurs : tête et queue. Enfiler ajoute un nœud après la queue puis met à jour la queue ; défiler retire le nœud de tête et met à jour la tête. Ces deux opérations sont en O(1). Une file sert par exemple à gérer les impressions dans un spooler.