🧠
Bases et allocation dynamiqueEn 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.
📢 Rappel
En C++, int* p = new int; alloue un entier et p contient son adresse ; delete p libère la mémoire.
📖 Définition
Une structure de données linéaire organise les éléments en séquence : chaque élément a au plus un prédécesseur et un successeur.
⭐ À retenir
Toujours libérer la mémoire allouée dynamiquement pour éviter les fuites mémoire.
💡 À retenir : Un pointeur permet de relier dynamiquement des éléments en mémoire.
🔗
Nœuds et chaînageUne 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.
📖 Définition
Un nœud est une structure contenant une donnée et un pointeur vers le nœud suivant (struct Noeud { int valeur; Noeud* suivant; };).
🔍 Exemple
Une playlist de musique : chaque morceau pointe vers le suivant, on peut insérer un morceau sans réécrire toute la liste.
⭐ À retenir
On parcourt une liste chaînée avec une boucle while (courant != nullptr).
💡 À retenir : L'insertion et la suppression en tête d'une liste chaînée se font en temps constant O(1).
🥞
LIFO : Last In, First OutUne 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.
🔍 Exemple
Une pile d'assiettes : on pose et on retire toujours celle du dessus.
📢 Rappel
Une fonction récursive utilise la pile d'appels pour mémoriser les contextes.
⭐ À retenir
Vérifier si la pile est vide avant de dépiler pour éviter de déréférencer nullptr.
💡 À retenir : Dans une pile, toutes les opérations se font au sommet, en O(1) avec une liste chaînée.
🚶
FIFO : First In, First OutUne 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.
🔍 Exemple
Une file d'attente à la cantine : le premier arrivé est le premier servi.
📢 Rappel
Dans une file, on insère uniquement en queue et on supprime uniquement en tête.
⭐ À retenir
Si la file devient vide, tête et queue doivent être mis à nullptr.
💡 À retenir : Une file utilise deux pointeurs (tête et queue) pour des opérations en O(1).