Vous n'utilisez pas de listes chaînées. Pourtant, elles font tourner la moitié de vos logiciels.
Il est probable que vous n'écriviez jamais de liste chaînée dans un projet JavaScript de production. Les tableaux intégrés de votre langage gèrent la mise à l'échelle dynamique plus rapidement. Les recruteurs vous apprennent à les construire sur des tableaux blancs, mais cela crée un modèle mental erroné.
Vous ne devriez pas apprendre les listes chaînées pour les implémenter. Vous les apprenez pour comprendre les outils que vous utilisez quotidiennement.
Elles sont partout : • Les boutons précédent et suivant du navigateur. • L'historique d'annulation des éditeurs de texte. • Les caches LRU dans les serveurs web et les bases de données. • Les commandes de listes Redis. • L'ordonnanceur de processus du noyau Linux.
Ce ne sont pas des reliques. Ce sont des infrastructures.
La véritable raison pour laquelle les listes chaînées sont pénalisées est la localité du cache. Votre processeur ne lit pas la RAM un octet à la fois. Il récupère un bloc de 64 octets appelé « cache line » (ligne de cache).
Les tableaux sont rapides car ils sont contigus en mémoire. Le processeur lit le premier élément et récupère gratuitement les 15 suivants.
Les listes chaînées détruisent cet avantage. Chaque nœud se trouve à un endroit différent en mémoire. Suivre un pointeur force le processeur à sauter vers une nouvelle adresse. Cela déclenche une nouvelle lecture en RAM. Cela coûte des centaines de cycles CPU.
Sur le matériel moderne, le parcours d'un tableau peut être 10 à 100 fois plus rapide que le parcours d'une liste chaînée. La notation Big-O ignore ce coût constant.
Alors, quand les utiliser ?
Utilisez une liste simplement chaînée pour les piles ou les files d'attente de tâches simples où vous n'ajoutez ou ne supprimez que d'une seule extrémité.
Utilisez une liste doublement chaînée lorsque vous avez besoin d'une suppression en O(1) avec une référence directe au nœud. C'est le secret du cache LRU.
Un cache LRU nécessite :
- Une recherche en O(1).
- Une insertion en O(1).
- Une éviction en O(1).
- Une promotion en O(1).
Un tableau ne peut pas faire cela car le déplacement d'éléments nécessite de décaler tout le reste. Une table de hachage seule ne peut pas non plus le faire car elle n'a pas d'ordre.
La solution est une combinaison. Une table de hachage assure la recherche. Une liste doublement chaînée maintient l'ordre. La table de hachage stocke la référence du nœud. Lorsque vous accédez à une clé, vous extrayez le nœud directement de la liste et vous le déplacez au début. Pas de recherche. Pas de décalage.
Arrêtez d'apprendre les structures de données uniquement pour réussir des entretiens. Apprenez-les pour comprendre comment le logiciel interagit avec le matériel.
Source : https://dev.to/islamhafez0/you-dont-use-linked-lists-but-theyre-running-half-your-software-4b37