Listes chaînées et piles
Au-delà des tableaux - Données dynamiques
Les tableaux sont excellents quand on connaît la taille des données à l'avance. Mais que se passe-t-il quand les données arrivent de façon imprévisible - un flux de mesures de capteurs, une file de tâches à traiter par une IA, ou un historique de conversation qui grandit à chaque message ? Il faut des structures qui s'adaptent.
Voici les listes chaînées, les piles et les files d'attente - le trio dynamique.
Listes chaînées - Nœuds et pointeurs
Une liste chaînée stocke les éléments sous forme de chaîne de nœuds. Chaque nœud contient deux choses : la donnée et un pointeur vers le nœud suivant.
[data: "A" | next: →] → [data: "B" | next: →] → [data: "C" | next: null]
Contrairement aux tableaux, les nœuds ne sont pas contigus en mémoire. Ils peuvent être éparpillés - le pointeur indique simplement où trouver le suivant.
Listes chaînées vs Tableaux
| Opération | Tableau | Liste chaînée | |-----------|---------|---------------| | Accès par index | O(1) ⚡ | O(n) 🐢 | | Insertion au début | O(n) 🐢 | O(1) ⚡ | | Insertion au milieu | O(n) 🐢 | O(1)* ⚡ | | Suppression au milieu | O(n) 🐢 | O(1)* ⚡ | | Utilisation mémoire | Compacte | Surcoût (pointeurs) |
*Une fois la position trouvée - la trouver reste O(n).
Quand les listes chaînées gagnent
- Insertions et suppressions fréquentes : si vous ajoutez et retirez constamment des éléments au milieu, les listes chaînées évitent le décalage coûteux des tableaux.
- Taille inconnue : quand on ne sait pas combien d'éléments stocker, la liste chaînée grandit nœud par nœud sans redimensionnement.
- Base d'autres structures : piles, files d'attente et structures plus complexes reposent souvent sur des listes chaînées.
La barre d'onglets de votre navigateur permet d'ouvrir, fermer et réorganiser librement. Un tableau ou une liste chaînée serait-il mieux adapté pour gérer les onglets ouverts ? Pensez à ce qui se passe quand on ferme un onglet au milieu.
Piles - Dernier entré, premier sorti (LIFO)
Discussion
Se connecter pour rejoindre la discussion