Programmation · concepts · structures de donnees

Qu'est-ce qu'une liste chainee ?

Par ColdwastMis a jour le 21 juil. 20268 min de lecture#data-structures#linked-list#concepts

Code de programmation sur un ecran — Une liste chainee est une chaine de noeuds : chacun porte une valeur et un lien vers le suivant, si bien que la sequence peut grandir et retrecir sans rien deplacer.

Une liste chainee (linked list) est une structure de donnees qui stocke une sequence de valeurs sous forme de chaine de noeuds. Chaque noeud contient deux choses : une valeur, et un pointeur (une reference) vers le noeud suivant de la chaine. Les noeuds ne sont pas disposes cote a cote dans un seul bloc de memoire comme le sont les elements d'un tableau ; a la place, chacun pointe simplement vers l'endroit ou vit le suivant. Suivez les pointeurs depuis le premier noeud, la tete, et vous pouvez parcourir toute la sequence un maillon a la fois.

Comment la chaine est construite

Voyez cela comme une chasse au tresor ou chaque indice vous dit ou trouver l'indice suivant. La liste garde une reference vers le noeud de tete. Le pointeur de ce noeud mene au deuxieme noeud, dont le pointeur mene au troisieme, et ainsi de suite jusqu'a ce que le pointeur d'un noeud soit vide (souvent appele null ou None), ce qui marque la fin de la liste.

[ valeur | suivant ] -> [ valeur | suivant ] -> [ valeur | null ]

Comme les connexions ne sont que des pointeurs, les noeuds peuvent se trouver n'importe ou en memoire. Pour agrandir la liste, vous allouez un nouveau noeud et reglez un pointeur vers lui ; rien d'autre n'a besoin de bouger.

Simplement vs doublement chainee

Il existe deux formes courantes, et la difference tient au nombre de pointeurs que porte chaque noeud :

Liste simplement chainee : chaque noeud pointe uniquement vers le noeud suivant. Vous pouvez avancer dans la liste mais pas reculer, et vous ne payez qu'un seul pointeur par noeud.
Liste doublement chainee : chaque noeud pointe a la fois vers le noeud suivant et le precedent. Cela permet de parcourir dans les deux sens et facilite certaines suppressions, au prix d'un pointeur supplementaire par noeud.

Maillons de chaine metallique assembles — Le nom est litteral : comme les maillons d'une chaine, chaque noeud est relie au suivant, et vous suivez ces liens pour vous deplacer dans la sequence.

Liste chainee vs tableau

La facon la plus claire de comprendre une liste chainee est de la placer a cote d'un tableau (array), car ils font des compromis opposes. Un tableau stocke ses elements dans un bloc contigu avec un index, si bien qu'il peut sauter a n'importe quelle position instantanement. Une liste chainee y renonce en echange de modifications peu couteuses aux extremites.

Acces aleatoire. Un tableau lit n'importe quel element par son index en O(1). Une liste chainee n'a pas d'index : pour atteindre le dixieme noeud, vous devez partir de la tete et suivre neuf pointeurs, donc l'acces est en O(n).
Insertion et suppression. Si vous detenez deja une reference vers le bon noeud, une liste chainee peut inserer ou supprimer la en re-cablant quelques pointeurs, une operation en O(1) - sans decaler les autres elements. Dans un tableau, inserer ou supprimer au milieu implique de decaler les elements suivants, ce qui est en O(n).
Memoire et cache. Un tableau regroupe ses valeurs, ce qui est favorable au cache du CPU. Une liste chainee disperse ses noeuds et stocke un pointeur supplementaire par noeud, elle utilise donc plus de memoire par element et tend a avoir une moins bonne localite de cache.

Aucune n'est "meilleure" ; elles conviennent a des taches differentes. Si vous avez besoin de recherches rapides par position, un tableau (ou un tableau dynamique comme une list ou un vector) l'emporte generalement. Si vos donnees changent beaucoup de taille et que vous ajoutez ou retirez surtout aux extremites, une liste chainee peut convenir. Pour une piqure de rappel sur la facon dont ces couts sont decrits, consultez notre guide sur la notation Big O.

Les complexites, honnetement

Voici les couts standard pour une liste chainee, avec la mise en garde qui compte toujours :

Acces et recherche : O(n). Il n'y a pas d'index, donc trouver une valeur signifie parcourir la chaine depuis la tete.
Insertion et suppression : O(1) quand vous avez deja une reference vers le noeud (par exemple, juste a la tete). Si vous devez d'abord trouver l'emplacement, cette recherche est en O(n), et le total reflete les deux parties.

Cette condition "quand vous avez le noeud" est la partie que l'on oublie souvent. Inserer en tete d'une liste simplement chainee est vraiment en temps constant ; inserer apres une valeur que vous devez encore localiser ne l'est pas.

Ou les listes chainees sont utilisees

Les listes chainees sont un element de construction plus qu'un conteneur du quotidien. Elles sont une facon naturelle d'implementer une pile (stack) ou une file (queue), puisque celles-ci n'ajoutent et ne retirent qu'aux extremites. Elles conviennent aux situations ou la taille de la collection change beaucoup et ou vous n'avez pas besoin d'un acces rapide par position. Certaines structures utilisent des noeuds chaines en interne ; par exemple, une facon courante de gerer les collisions dans une table de hachage est de chainer ensemble les entrees en collision dans une petite liste chainee par bucket.

Les compromis

Pas d'acces aleatoire. Atteindre une position arbitraire coute O(n) car vous suivez les pointeurs depuis la tete ; il n'y a pas d'index pour sauter directement.
Memoire supplementaire par element. Chaque noeud stocke au moins un pointeur (deux pour une liste doublement chainee) en plus de sa valeur.
Localite de cache plus faible. Des noeuds disperses sont moins favorables au cache qu'un tableau contigu, ce qui peut rendre le parcours plus lent en pratique meme quand le Big O est le meme.
Modifications peu couteuses a un noeud connu. L'avantage : inserer ou retirer a un noeud que vous detenez deja est en O(1), sans decaler le reste des donnees.

Recommande

Un endroit pour construire et executer votre code

Apprendre les structures de donnees est une chose ; deployer les programmes qui les utilisent en est une autre. Un VPS ou un serveur cloud vous donne un vrai environnement pour compiler, executer et heberger vos projets. Infomaniak - un fournisseur suisse respectueux de la vie privee - propose des VPS et serveurs cloud pour exactement cela.

Voir Infomaniak Cloud →

Lien affilie - il soutient ces guides gratuits.

FAQ

Quelle est la difference entre une liste chainee et un tableau ? Un tableau stocke les elements dans un bloc contigu avec un index, il lit donc n'importe quelle position en O(1) mais decaler des elements pour inserer ou supprimer au milieu coute O(n). Une liste chainee stocke des noeuds separes relies par des pointeurs, elle n'a donc pas d'acces aleatoire (O(n) pour atteindre une position) mais peut inserer ou supprimer a un noeud connu en O(1).

Pourquoi l'acces a un element est-il en O(n) ? Parce qu'une liste chainee n'a pas d'index. Pour atteindre le nieme noeud, vous partez de la tete et suivez la chaine de pointeurs n fois, donc le cout croit avec la position voulue.

Quelle est la difference entre simplement et doublement chainee ? Dans une liste simplement chainee, chaque noeud pointe uniquement vers le noeud suivant, vous ne pouvez donc avancer que vers l'avant. Dans une liste doublement chainee, chaque noeud pointe aussi vers le noeud precedent, vous pouvez donc vous deplacer dans les deux sens, au prix d'un pointeur supplementaire par noeud.

Quand devrais-je utiliser une liste chainee ? Quand la collection change beaucoup de taille et que vous ajoutez ou retirez surtout aux extremites, ou comme ossature d'une pile ou d'une file. Si vous avez besoin d'un acces rapide par position, un tableau est generalement le meilleur choix.

Guide independant, maintenu par la communaute. coldwa.st est un site de ressources de programmation ; cet article couvre les listes chainees a un niveau introductif. Les complexites et comportements decrits sont des resultats standard de l'informatique.