Liste liée

—

En informatique , une liste chaînée est une collection linéaire d’éléments de données dont l’ordre n’est pas donné par leur placement physique en mémoire. Au lieu de cela, chaque élément pointe vers le suivant. Il s’agit d’une structure de données constituée d’un ensemble de nœuds qui représentent ensemble une séquence . Dans sa forme la plus basique, chaque nœud contient : data , et une référence (en d’autres termes, un lien) au nœud suivant dans la séquence. Cette structure permet une insertion ou une suppression efficace d’éléments à partir de n’importe quelle position dans la séquence pendant l’itération. Des variantes plus complexes ajoutent des liens supplémentaires, permettant une insertion ou une suppression plus efficace des nœuds à des positions arbitraires. Un inconvénient des listes chaînées est que le temps d’accès est linéaire (et difficile à canaliser ). Un accès plus rapide, tel qu’un accès aléatoire, n’est pas possible. Les tableaux ont une meilleure localité de cache par rapport aux listes chaînées.

Une liste chaînée dont les nœuds contiennent deux champs : une valeur entière et un lien vers le nœud suivant. Le dernier nœud est lié à un terminateur utilisé pour signifier la fin de la liste.

Les listes chaînées font partie des structures de données les plus simples et les plus courantes. Ils peuvent être utilisés pour implémenter plusieurs autres types de données abstraits courants , y compris les listes , les piles , les files d’attente , les tableaux associatifs et les expressions S , bien qu’il ne soit pas rare d’implémenter ces structures de données directement sans utiliser une liste chaînée comme base.

Le principal avantage d’une liste chaînée par rapport à un tableau conventionnel est que les éléments de la liste peuvent être facilement insérés ou supprimés sans réaffectation ou réorganisation de l’ensemble de la structure car les éléments de données n’ont pas besoin d’être stockés de manière contiguë en mémoire ou sur disque, tout en restructurant un tableau à l’exécution est une opération beaucoup plus coûteuse. Les listes chaînées permettent l’insertion et la suppression de nœuds à n’importe quel point de la liste, et permettent de le faire avec un nombre constant d’opérations en gardant le lien précédent le lien ajouté ou supprimé en mémoire pendant le parcours de la liste.

D’autre part, comme les listes chaînées simples ne permettent pas à elles seules un accès aléatoire aux données ou toute forme d’indexation efficace, de nombreuses opérations de base, telles que l’obtention du dernier nœud de la liste, la recherche d’un nœud contenant une donnée donnée ou localiser l’endroit où un nouveau nœud doit être inséré – peut nécessiter une itération à travers la plupart ou la totalité des éléments de la liste. Les avantages et les inconvénients de l’utilisation de listes chaînées sont indiqués ci-dessous.

Histoire

Les listes liées ont été développées en 1955–1956 par Allen Newell , Cliff Shaw et Herbert A. Simon de RAND Corporation comme structure de données principale pour leur langage de traitement de l’information . IPL a été utilisé par les auteurs pour développer plusieurs premiers programmes d’intelligence artificielle , notamment la Logic Theory Machine, le General Problem Solver et un programme d’échecs informatique. Des rapports sur leurs travaux sont parus dans IRE Transactions on Information Theory en 1956, et dans plusieurs actes de conférence de 1957 à 1959, dont les Actes de la Western Joint Computer Conference en 1957 et 1958, et Information Processing (Actes du premierConférence internationale de l’UNESCO sur le traitement de l’information) en 1959. Le diagramme désormais classique composé de blocs représentant des nœuds de liste avec des flèches pointant vers des nœuds de liste successifs apparaît dans “Programming the Logic Theory Machine” de Newell et Shaw dans Proc. WJCC, février 1957. Newell et Simon ont reçu le prix ACM Turing en 1975 pour avoir “apporté des contributions fondamentales à l’intelligence artificielle, à la psychologie de la cognition humaine et au traitement des listes”. Le problème de la traduction automatique pour le traitement du langage naturel a conduit Victor Yngve au Massachusetts Institute of Technology(MIT) pour utiliser des listes chaînées comme structures de données dans son langage de programmation COMIT pour la recherche informatique dans le domaine de la linguistique . Un rapport sur ce langage intitulé “Un langage de programmation pour la traduction mécanique” est paru dans Mechanical Translation en 1958. [ citation nécessaire ]

Une autre apparition précoce des listes liées a été celle de Hans Peter Luhn qui a écrit un mémorandum interne d’ IBM en janvier 1953 qui suggérait l’utilisation de listes liées dans des tables de hachage chaînées. [1]

LISP , pour list processor, a été créé par John McCarthy en 1958 alors qu’il était au MIT et en 1960, il a publié sa conception dans un article dans les Communications de l’ACM , intitulé “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part JE”. L’une des principales structures de données de LISP est la liste chaînée.

Au début des années 1960, l’utilité des listes chaînées et des langages qui utilisent ces structures comme représentation primaire des données était bien établie. Bert Green du MIT Lincoln Laboratory a publié un article de synthèse intitulé “Langages informatiques pour la manipulation de symboles” dans IRE Transactions on Human Factors in Electronics en mars 1961 qui résumait les avantages de l’approche des listes chaînées. Un article de revue ultérieur, “Une comparaison des langages informatiques de traitement de liste” par Bobrow et Raphael, est paru dans Communications of the ACM en avril 1964.

Plusieurs systèmes d’exploitation développés par Technical Systems Consultants (à l’origine de West Lafayette Indiana, et plus tard de Chapel Hill, Caroline du Nord) utilisaient des listes liées individuellement comme structures de fichiers. Une entrée de répertoire pointait vers le premier secteur d’un fichier et les parties suivantes du fichier étaient localisées en traversant des pointeurs. Les systèmes utilisant cette technique comprenaient Flex (pour le processeur Motorola 6800 ), mini-Flex (même processeur) et Flex9 (pour le processeur Motorola 6809). Une variante développée par TSC pour et commercialisée par Smoke Signal Broadcasting en Californie, utilisait des listes à double liaison de la même manière.

Le système d’exploitation TSS/360, développé par IBM pour les machines System 360/370, utilisait une double liste chaînée pour son catalogue de système de fichiers. La structure des répertoires était similaire à Unix, où un répertoire pouvait contenir des fichiers et d’autres répertoires et s’étendre à n’importe quelle profondeur.

Concepts de base et nomenclature

Chaque enregistrement d’une liste chaînée est souvent appelé ‘élément’ ou ‘ nœud ‘.

Le champ de chaque nœud qui contient l’adresse du nœud suivant est généralement appelé ‘lien suivant’ ou ‘pointeur suivant’. Les champs restants sont appelés champs « données », « informations », « valeur », « cargaison » ou « charge utile ».

La « tête » d’une liste est son premier nœud. La “queue” d’une liste peut faire référence soit au reste de la liste après la tête, soit au dernier nœud de la liste. En Lisp et dans certains langages dérivés, le nœud suivant peut être appelé le « cdr » (prononcé could-er ) de la liste, tandis que la charge utile du nœud principal peut être appelée la « voiture ».

Liste liée individuellement

Les listes chaînées simples contiennent des nœuds qui ont un champ de données ainsi qu’un champ « suivant », qui pointe vers le nœud suivant dans la ligne de nœuds. Les opérations pouvant être effectuées sur des listes à liaison simple incluent l’insertion, la suppression et le parcours.

Une liste chaînée dont les nœuds contiennent deux champs : une valeur entière et un lien vers le nœud suivant

Le code suivant montre comment ajouter un nouveau nœud avec une “valeur” de données à la fin d’une liste à liaison simple :

node addNode ( tête de nœud , valeur int ) { température du nœud , p ; // déclarer deux noeuds temp et p temp = createNode (); // suppose que createNode crée un nouveau nœud avec data = 0 et suivant pointant vers NULL. temp -> données = valeur ; // ajoute la valeur de l’élément à la partie données du nœud if ( head == NULL ) { tête = temp ; // lorsque la liste chaînée est vide } sinon { p = tête ; // assigne la tête à p while ( p -> next != NULL ) { p = p -> suivant ; // parcourt la liste jusqu’à ce que p soit le dernier nœud. Le dernier nœud pointe toujours vers NULL. } p -> suivant = temp ; // Pointez le dernier nœud précédent vers le nouveau nœud créé. } tête de retour ; }

Liste doublement liée

Dans une ‘liste doublement liée’, chaque nœud contient, en plus du lien du nœud suivant, un deuxième champ de lien pointant vers le nœud ‘précédent’ dans la séquence. Les deux liens peuvent être appelés ‘forward(‘s’) et ‘backwards’, ou ‘next’ et ‘prev'(‘previous’).

Une liste doublement liée dont les nœuds contiennent trois champs : une valeur entière, le lien vers le nœud suivant et le lien vers le nœud précédent

Une technique connue sous le nom de liaison XOR permet d’implémenter une liste doublement liée à l’aide d’un seul champ de lien dans chaque nœud. Cependant, cette technique nécessite la capacité d’effectuer des opérations sur les bits sur les adresses et peut donc ne pas être disponible dans certains langages de haut niveau.

De nombreux systèmes d’exploitation modernes utilisent des listes à double liaison pour conserver les références aux processus actifs, aux threads et à d’autres objets dynamiques. [2] Une stratégie commune pour les Rootkits pour échapper à la détection est de se dissocier de ces listes. [3]

Multiplier la liste chaînée

Dans une « liste à liens multiples », chaque nœud contient deux ou plusieurs champs de lien, chaque champ étant utilisé pour connecter le même ensemble d’enregistrements de données dans un ordre différent du même ensemble (par exemple, par nom, par département, par date de naissance, etc.). Alors que les listes doublement chaînées peuvent être considérées comme des cas particuliers de liste chaînée multiple, le fait que les deux ordres et plus soient opposés l’un à l’autre conduit à des algorithmes plus simples et plus efficaces, ils sont donc généralement traités comme un cas distinct.

Liste chaînée circulaire

Dans le dernier nœud d’une liste, le champ de lien contient souvent une référence nulle , une valeur spéciale est utilisée pour indiquer l’absence d’autres nœuds. Une convention moins courante consiste à le faire pointer vers le premier nœud de la liste ; dans ce cas, la liste est dite « circulaire » ou « circulairement liée » ; sinon, il est dit « ouvert » ou « linéaire ». C’est une liste où le dernier pointeur pointe vers le premier nœud.

Une liste chaînée circulaire

Dans le cas d’une liste circulaire doublement chaînée, le premier nœud pointe également vers le dernier nœud de la liste.

Nœuds sentinelles

Dans certaines implémentations, un nœud “sentinelle” ou “factice” supplémentaire peut être ajouté avant le premier enregistrement de données ou après le dernier. Cette convention simplifie et accélère certains algorithmes de gestion de liste, en garantissant que tous les liens peuvent être déréférencés en toute sécurité et que chaque liste (même celle qui ne contient aucun élément de données) a toujours un “premier” et un “dernier” nœud.

Listes vides

Une liste vide est une liste qui ne contient aucun enregistrement de données. Cela revient généralement à dire qu’il n’a aucun nœud. Si des nœuds sentinelles sont utilisés, la liste est généralement dite vide lorsqu’elle ne contient que des nœuds sentinelles.

Lien de hachage

Les champs de lien n’ont pas besoin de faire physiquement partie des nœuds. Si les enregistrements de données sont stockés dans un tableau et référencés par leurs indices, le champ de lien peut être stocké dans un tableau séparé avec les mêmes indices que les enregistrements de données.

Poignées de liste

Puisqu’une référence au premier nœud donne accès à toute la liste, cette référence est souvent appelée « adresse », « pointeur » ou « descripteur » de la liste. Les algorithmes qui manipulent les listes chaînées obtiennent généralement de tels descripteurs sur les listes d’entrée et renvoient les descripteurs aux listes résultantes. En fait, dans le contexte de tels algorithmes, le mot « liste » signifie souvent « descripteur de liste ». Dans certaines situations, cependant, il peut être pratique de faire référence à une liste par un descripteur composé de deux liens, pointant vers ses premier et dernier nœuds.

Combiner des alternatives

Les alternatives énumérées ci-dessus peuvent être arbitrairement combinées de presque toutes les manières, de sorte que l’on peut avoir des listes circulaires à double lien sans sentinelles, des listes circulaires à simple lien avec des sentinelles, etc.

Compromis

Comme pour la plupart des choix en matière de programmation et de conception informatiques, aucune méthode n’est bien adaptée à toutes les circonstances. Une structure de données de liste chaînée peut bien fonctionner dans un cas, mais causer des problèmes dans un autre. Voici une liste de certains des compromis courants impliquant des structures de liste chaînée.

Listes liées vs tableaux dynamiques

Comparaison des structures de données de liste

Aperçu
(indice)		 Muter (insérer ou supprimer) à … Espace excédentaire,
moyen
Début Finir Milieu
Liste liée Θ( n ) Θ(1) Θ(1), élément d’extrémité connu ;
Θ( n ), élément terminal inconnu		 Temps de crête +
Θ(1) [4] [5]		 Θ( n )
Déployer Θ(1) N / A N / A N / A 0
Tableau dynamique Θ(1) Θ( n ) Θ(1) amorti Θ( n ) Θ( n ) [6]
Arbre équilibré Θ(log n) Θ(log n) Θ(log n ) Θ(log n ) Θ( n )
Liste d’accès aléatoire Θ(log n) [7] Θ(1) S/O [7] S/O [7] Θ( n )
Arbre de tableau haché Θ(1) Θ( n ) Θ(1) amorti Θ( n ) Θ(√ n )

Un tableau dynamique est une structure de données qui alloue tous les éléments de manière contiguë en mémoire et conserve un décompte du nombre actuel d’éléments. Si l’espace réservé au tableau dynamique est dépassé, il est réalloué et (éventuellement) copié, ce qui est une opération coûteuse.

Les listes chaînées présentent plusieurs avantages par rapport aux tableaux dynamiques. L’insertion ou la suppression d’un élément à un point précis d’une liste, en supposant que nous avons déjà indexé un pointeur sur le nœud (avant celui à supprimer, ou avant le point d’insertion), est une opération à temps constant (sinon sans cela la référence est O(n)), alors que l’insertion dans un tableau dynamique à des emplacements aléatoires nécessitera le déplacement de la moitié des éléments en moyenne, et de tous les éléments dans le pire des cas. Alors que l’on peut “supprimer” un élément d’un tableau en temps constant en marquant d’une manière ou d’une autre son emplacement comme “vacant”, cela provoque une fragmentation qui entrave les performances de l’itération.

De plus, de nombreux éléments arbitrairement peuvent être insérés dans une liste chaînée, limitée uniquement par la mémoire totale disponible ; tandis qu’un tableau dynamique finira par remplir sa structure de données de tableau sous-jacente et devra réallouer – une opération coûteuse, qui peut même ne pas être possible si la mémoire est fragmentée, bien que le coût de la réallocation puisse être moyenné sur les insertions, et le coût de une insertion due à une réallocation serait encore amortie O(1). Cela facilite l’ajout d’éléments à la fin du tableau, mais l’insertion (ou la suppression) des positions intermédiaires entraîne toujours des coûts prohibitifs en raison du déplacement des données pour maintenir la contiguïté. Un tableau dont de nombreux éléments sont supprimés peut également devoir être redimensionné afin d’éviter de perdre trop d’espace.

D’autre part, les tableaux dynamiques (ainsi que les structures de données de tableau de taille fixe) permettent un accès aléatoire à temps constant , tandis que les listes chaînées ne permettent qu’un accès séquentiel aux éléments. En fait, les listes chaînées peuvent être facilement parcourues dans une seule direction. Cela rend les listes chaînées inadaptées aux applications où il est utile de rechercher rapidement un élément par son index, comme heapsort . L’accès séquentiel sur les tableaux et les tableaux dynamiques est également plus rapide que sur les listes chaînées sur de nombreuses machines, car ils ont une localité de référence optimale et font donc bon usage de la mise en cache des données.

Un autre inconvénient des listes liées est le stockage supplémentaire nécessaire pour les références, ce qui les rend souvent peu pratiques pour les listes de petits éléments de données tels que les caractères ou les valeurs booléennes , car la surcharge de stockage des liens peut dépasser d’un facteur deux ou plus la taille de les données. En revanche, un tableau dynamique ne nécessite que l’espace pour les données elles-mêmes (et une très petite quantité de données de contrôle). [note 1] Il peut aussi être lent, et avec un répartiteur naïf, inutile, d’allouer de la mémoire séparément pour chaque nouvel élément, un problème généralement résolu en utilisant des pools de mémoire .

Certaines solutions hybrides tentent de combiner les avantages des deux représentations. Les listes liées déroulées stockent plusieurs éléments dans chaque nœud de liste, augmentant les performances du cache tout en réduisant la surcharge de mémoire pour les références. Le codage CDR fait également ces deux choses, en remplaçant les références par les données réelles référencées, qui s’étendent à la fin de l’enregistrement de référence.

Un bon exemple qui met en évidence les avantages et les inconvénients de l’utilisation de tableaux dynamiques par rapport aux listes chaînées consiste à implémenter un programme qui résout le problème de Josephus . Le problème Josèphe est une méthode d’élection qui fonctionne en ayant un groupe de personnes debout en cercle. A partir d’une personne prédéterminée, on peut compter autour du cercle n fois. Une fois le nème personne est atteinte, il faut la retirer du cercle et demander aux membres de fermer le cercle. Le processus est répété jusqu’à ce qu’il ne reste qu’une seule personne. Cette personne remporte l’élection. Cela montre les forces et les faiblesses d’une liste chaînée par rapport à un tableau dynamique, car si les personnes sont considérées comme des nœuds connectés dans une liste chaînée circulaire, cela montre à quel point la liste chaînée peut facilement supprimer des nœuds (car elle n’a qu’à réorganiser les liens vers les différents nœuds). Cependant, la liste liée ne trouvera pas la prochaine personne à supprimer et devra parcourir la liste jusqu’à ce qu’elle trouve cette personne. Un tableau dynamique, en revanche, sera médiocre pour supprimer des nœuds (ou des éléments) car il ne peut pas supprimer un nœud sans déplacer individuellement tous les éléments vers le haut de la liste d’un. Cependant, il est exceptionnellement facile de trouver len ième personne du cercle en les référençant directement par leur position dans le tableau.

Le problème de classement de liste concerne la conversion efficace d’une représentation de liste chaînée en un tableau. Bien que triviale pour un ordinateur classique, la résolution de ce problème par un algorithme parallèle est compliquée et a fait l’objet de nombreuses recherches.

Un arbre équilibré a des modèles d’accès mémoire et une surcharge d’espace similaires à une liste chaînée tout en permettant une indexation beaucoup plus efficace, prenant un temps O (log n) au lieu de O (n) pour un accès aléatoire. Cependant, les opérations d’insertion et de suppression sont plus coûteuses en raison de la surcharge des manipulations d’arbres pour maintenir l’équilibre. Des schémas existent pour que les arbres se maintiennent automatiquement dans un état d’équilibre : arbres AVL ou arbres rouge-noir .

Listes linéaires à liaison unique par rapport aux autres listes

Alors que les listes à double liaison et circulaires présentent des avantages par rapport aux listes linéaires à simple liaison, les listes linéaires offrent certains avantages qui les rendent préférables dans certaines situations.

Une liste linéaire à liens simples est une structure de données récursive , car elle contient un pointeur vers un objet plus petit du même type. Pour cette raison, de nombreuses opérations sur des listes linéaires liées de manière simple (telles que la fusion de deux listes ou l’énumération des éléments dans l’ordre inverse) ont souvent des algorithmes récursifs très simples, beaucoup plus simples que toute solution utilisant des commandes itératives . Bien que ces solutions récursives puissent être adaptées aux listes à double liaison et à liaison circulaire, les procédures nécessitent généralement des arguments supplémentaires et des cas de base plus compliqués.

Les listes linéaires à liaison simple permettent également le partage de queue , l’utilisation d’une partie finale commune de sous-liste comme partie terminale de deux listes différentes. En particulier, si un nouveau nœud est ajouté au début d’une liste, l’ancienne liste reste disponible comme queue de la nouvelle — un exemple simple de structure de données persistante . Encore une fois, ce n’est pas vrai avec les autres variantes : un nœud ne peut jamais appartenir à deux listes circulaires ou doublement chaînées différentes.

En particulier, les nœuds sentinelles d’extrémité peuvent être partagés entre des listes non circulaires à liaison unique. Le même nœud sentinelle d’extrémité peut être utilisé pour chacune de ces listes. En Lisp , par exemple, chaque liste propre se termine par un lien vers un nœud spécial, noté nilou (), dont les liens CARet pointent vers lui-même. CDRAinsi, une procédure Lisp peut prendre en toute sécurité le CARou CDRde n’importe quelle liste.

Les avantages des variantes sophistiquées se limitent souvent à la complexité des algorithmes, et non à leur efficacité. Une liste circulaire, en particulier, peut généralement être émulée par une liste linéaire avec deux variables qui pointent vers les premier et dernier nœuds, sans frais supplémentaires.

Doublement lié vs. simplement lié

Les listes à double liaison nécessitent plus d’espace par nœud (sauf si l’on utilise la liaison XOR ), et leurs opérations élémentaires sont plus coûteuses ; mais ils sont souvent plus faciles à manipuler car ils permettent un accès séquentiel rapide et facile à la liste dans les deux sens. Dans une liste doublement chaînée, on peut insérer ou supprimer un nœud dans un nombre constant d’opérations étant donné uniquement l’adresse de ce nœud. Pour faire la même chose dans une liste liée individuellement, il faut avoir l’ adresse du pointeur vers ce nœud, qui est soit le descripteur de la liste entière (dans le cas du premier nœud), soit le champ de lien dans le nœud précédent . Certains algorithmes nécessitent un accès dans les deux sens. D’autre part, les listes doublement liées ne permettent pas le partage de queue et ne peuvent pas être utilisées comme structures de données persistantes..

Circulairement lié vs linéairement lié

Une liste liée circulairement peut être une option naturelle pour représenter des tableaux qui sont naturellement circulaires, par exemple les coins d’un polygone , un pool de tampons qui sont utilisés et libérés dans l’ordre FIFO (“premier entré, premier sorti”), ou un ensemble de processus qui doivent être partagés en temps partagé dans l’ordre du tourniquet . Dans ces applications, un pointeur vers n’importe quel nœud sert de descripteur pour toute la liste.

Avec une liste circulaire, un pointeur vers le dernier nœud permet également d’accéder facilement au premier nœud, en suivant un lien. Ainsi, dans les applications qui nécessitent un accès aux deux extrémités de la liste (par exemple, dans la mise en œuvre d’une file d’attente), une structure circulaire permet de manipuler la structure par un seul pointeur, au lieu de deux.

Une liste circulaire peut être scindée en deux listes circulaires, en temps constant, en donnant les adresses du dernier nœud de chaque morceau. L’opération consiste à échanger le contenu des champs de liens de ces deux nœuds. L’application de la même opération à deux nœuds quelconques dans deux listes distinctes joint les deux listes en une seule. Cette propriété simplifie grandement certains algorithmes et structures de données, tels que le quad-edge et le face-edge .

La représentation la plus simple d’une liste circulaire vide (lorsqu’une telle chose a du sens) est un pointeur nul, indiquant que la liste n’a pas de nœuds. Sans ce choix, de nombreux algorithmes doivent tester ce cas particulier et le traiter séparément. En revanche, l’utilisation de null pour désigner une liste linéaire vide est plus naturelle et crée souvent moins de cas particuliers.

Pour certaines applications, il peut être utile d’utiliser des listes chaînées simples qui peuvent varier entre être circulaires et linéaires, voire circulaires avec un segment initial linéaire. Les algorithmes de recherche ou d’opération sur ceux-ci doivent prendre des précautions pour éviter d’entrer accidentellement dans une boucle sans fin. Une méthode habituelle consiste à avoir un deuxième pointeur parcourant la liste à la moitié ou au double de la vitesse, et si les deux pointeurs se rencontrent au même nœud, vous savez que vous avez trouvé un cycle.

Utilisation des nœuds sentinelles

Le nœud sentinelle peut simplifier certaines opérations de liste, en s’assurant que les nœuds suivants ou précédents existent pour chaque élément, et que même les listes vides ont au moins un nœud. On peut également utiliser un nœud sentinelle en fin de liste, avec un champ de données approprié, pour éliminer certains tests de fin de liste. Par exemple, lors de l’analyse de la liste à la recherche d’un nœud avec une valeur x donnée , la définition du champ de données de la sentinelle sur x rend inutile le test de fin de liste à l’intérieur de la boucle. Un autre exemple est la fusion de deux listes triées : si leurs sentinelles ont des champs de données définis sur +∞, le choix du nœud de sortie suivant ne nécessite pas de traitement particulier pour les listes vides.

Cependant, les nœuds sentinelles consomment de l’espace supplémentaire (en particulier dans les applications qui utilisent de nombreuses listes courtes) et peuvent compliquer d’autres opérations (telles que la création d’une nouvelle liste vide).

Cependant, si la liste circulaire est utilisée simplement pour simuler une liste linéaire, on peut éviter une partie de cette complexité en ajoutant un seul nœud sentinelle à chaque liste, entre le dernier et le premier nœud de données. Avec cette convention, une liste vide se compose du nœud sentinelle seul, pointant vers lui-même via le lien du nœud suivant. Le descripteur de liste doit alors être un pointeur vers le dernier nœud de données, avant la sentinelle, si la liste n’est pas vide ; ou à la sentinelle elle-même, si la liste est vide.

La même astuce peut être utilisée pour simplifier la gestion d’une liste linéaire doublement liée, en la transformant en une liste circulaire doublement liée avec un seul nœud sentinelle. Cependant, dans ce cas, le handle doit être un pointeur unique vers le nœud factice lui-même. [8]

Opérations de liste chaînée

Lors de la manipulation de listes liées sur place, veillez à ne pas utiliser de valeurs que vous avez invalidées dans des affectations précédentes. Cela rend les algorithmes d’insertion ou de suppression de nœuds de liste chaînée quelque peu subtils. Cette section donne le pseudocode pour ajouter ou supprimer des nœuds de listes à liens simples, doubles et circulaires sur place. Tout au long, nous utiliserons null pour faire référence à un marqueur de fin de liste ou sentinelle , qui peut être implémenté de plusieurs façons.

Listes liées linéairement

Listes à liens simples

Notre structure de données de nœud aura deux champs. Nous gardons également une variable firstNode qui pointe toujours vers le premier nœud de la liste, ou est nulle pour une liste vide.

nœud d’ enregistrement { Les données; // Les données sont stockées dans le nœud Node next // Une référence [2] au nœud suivant, null pour le dernier nœud } liste d’ enregistrements { Node firstNode // pointe vers le premier nœud de la liste ; null pour une liste vide }

La traversée d’une liste à liens simples est simple, en commençant par le premier nœud et en suivant chaque lien suivant jusqu’à ce que nous arrivions à la fin :

node := list.firstNode while node not null (faire quelque chose avec node.data) node := node.next

Le code suivant insère un nœud après un nœud existant dans une liste à liaison simple. Le diagramme montre comment cela fonctionne. L’insertion d’un nœud avant un nœud existant ne peut pas se faire directement ; au lieu de cela, il faut garder une trace du nœud précédent et insérer un nœud après celui-ci.

Schéma d’insertion d’un nœud dans une liste à liaison simple function insertAfter( Node node, Node newNode) // insère newNode après le nœud newNode.next := node.next node.next := nouveauNoeud

L’insertion au début de la liste nécessite une fonction distincte. Cela nécessite la mise à jour de firstNode .

function insertBeginning( List list, Node newNode) // insère un nœud avant le premier nœud actuel newNode.next := list.firstNode list.firstNode := nouveauNoeud

De même, nous avons des fonctions pour supprimer le nœud après un nœud donné et pour supprimer un nœud du début de la liste. Le schéma illustre le premier. Pour trouver et supprimer un nœud particulier, il faut à nouveau garder une trace de l’élément précédent.

Schéma de suppression d’un nœud d’une liste à liaison simple function removeAfter( Node node) // supprime le nœud après celui-ci obsoleteNode := node.next node.next := node.next.next détruire obsoleteNode fonction removeBeginning( List list) // supprime le premier nœud obsoleteNode := list.firstNode list.firstNode := list.firstNode.next // pointe après le nœud supprimé détruire obsoleteNode

Notez que removeBeginning()définit list.firstNodesur nulllors de la suppression du dernier nœud de la liste.

insertBeforeComme nous ne pouvons pas itérer en arrière, les opérations ou efficaces removeBeforene sont pas possibles. L’insertion dans une liste avant un nœud spécifique nécessite de parcourir la liste, ce qui aurait dans le pire des cas un temps d’exécution de O (n).

L’ajout d’une liste liée à une autre peut être inefficace à moins qu’une référence à la queue ne soit conservée dans la structure de la liste, car nous devons parcourir toute la première liste afin de trouver la queue, puis y ajouter la deuxième liste. Ainsi, si deux listes liées linéairement sont chacune de longueur n {displaystyle n} n n, l’ajout de liste a une Complexité temporelle asymptotique de O ( n ) {displaystyle O(n)} O(n) O(n). Dans la famille de langages Lisp, l’ajout de liste est fourni par la appendprocédure.

De nombreux cas particuliers d’opérations de liste chaînée peuvent être éliminés en incluant un élément factice au début de la liste. Cela garantit qu’il n’y a pas de cas particuliers pour le début de la liste et rend les deux insertBeginning()et removeBeginning()inutiles. Dans ce cas, les premières données utiles de la liste se trouveront à .list.firstNode.next

Liste liée circulairement

Dans une liste liée circulairement, tous les nœuds sont liés dans un cercle continu, sans utiliser null. Pour les listes avec un avant et un arrière (comme une file d’attente), on stocke une référence au dernier nœud de la liste. Le nœud suivant après le dernier nœud est le premier nœud. Des éléments peuvent être ajoutés à l’arrière de la liste et supprimés de l’avant en temps constant.

Les listes liées de manière circulaire peuvent être liées de manière simple ou double.

Les deux types de listes liées circulairement bénéficient de la possibilité de parcourir la liste complète en commençant à n’importe quel nœud donné. Cela nous permet souvent d’éviter de stocker firstNode et lastNode , bien que si la liste peut être vide, nous avons besoin d’une représentation spéciale pour la liste vide, comme une variable lastNode qui pointe vers un nœud dans la liste ou est nulle si elle est vide ; nous utilisons un tel lastNode ici. Cette représentation simplifie considérablement l’ajout et la suppression de nœuds avec une liste non vide, mais les listes vides sont alors un cas particulier.

Algorithmes

En supposant que someNode est un nœud dans une liste circulaire non vide à liaison simple, ce code parcourt cette liste en commençant par someNode :

fonction itérer(someNode) si someNode ≠ null noeud := unNoeud faire faire quelque chose avec node.value node := node.next tant que nœud ≠ unNœud

Notez que le test ” while node ≠ someNode” doit être à la fin de la boucle. Si le test était déplacé au début de la boucle, la procédure échouait chaque fois que la liste n’avait qu’un seul nœud.

Cette fonction insère un nœud “newNode” dans une liste chaînée circulaire après un nœud “node” donné. Si “node” est nul, il suppose que la liste est vide.

function insertAfter( Node node, Node newNode) if node = null // suppose que la liste est vide nouveauNoeud.suivant := nouveauNoeud autre newNode.next := node.next node.next := nouveauNoeud mettre à jour la variable lastNode si nécessaire

Supposons que “L” est une variable pointant vers le dernier nœud d’une liste chaînée circulaire (ou nulle si la liste est vide). Pour ajouter “newNode” à la fin de la liste, on peut faire

insertAprès(L, nouveauNoeud) L := nouveauNoeud

Pour insérer “newNode” au début de la liste, on peut faire

insertAfter(L, newNode) si L = null L := nouveauNoeud

Cette fonction insère une valeur “newVal” avant un noeud “node” donné en temps O(1). Nous créons un nouveau nœud entre “nœud” et le nœud suivant, puis mettons la valeur de “nœud” dans ce nouveau nœud, et mettons “newVal” dans “nœud”. Ainsi, une liste liée circulairement à liaison simple avec seulement une variable firstNode peut à la fois s’insérer à l’avant et à l’arrière en temps O(1).

function insertBefore( Node node, newVal) if node = null // suppose que la liste est vide newNode := new Node(data:=newVal, next:=newNode) else newNode := new Node(data:=node.data, next:=node.next) node.data := newVal node.next := nouveauNoeud mettre à jour la variable firstNode si nécessaire

Cette fonction supprime un nœud non nul d’une liste de taille supérieure à 1 en temps O(1). Il copie les données du nœud suivant dans le nœud, puis définit le pointeur suivant du nœud pour ignorer le nœud suivant.

fonction remove( Node node) si node ≠ null et size of list > 1 données supprimées := nœud.données node.data := node.next.data node.next = node.next.next retour données supprimées

Listes chaînées utilisant des tableaux de nœuds

Les langages qui ne prennent en charge aucun type de référence peuvent toujours créer des liens en remplaçant les pointeurs par des indices de tableau. L’approche consiste à conserver un tableau d’ enregistrements , où chaque enregistrement a des champs entiers indiquant l’index du nœud suivant (et éventuellement précédent) dans le tableau. Tous les nœuds du tableau n’ont pas besoin d’être utilisés. Si les enregistrements ne sont pas non plus pris en charge, des tableaux parallèles peuvent souvent être utilisés à la place.

Par exemple, considérez l’enregistrement de liste chaînée suivant qui utilise des tableaux au lieu de pointeurs :

record Entry { entier suivant ; // index de l’entrée suivante dans le tableau entier prev ; // nom de chaîne de l’entrée précédente (si elle est liée en double) ; véritable équilibre; }

Une liste chaînée peut être construite en créant un tableau de ces structures et une variable entière pour stocker l’index du premier élément.

nombre entier listHead Entry Records[1000]

Les liens entre les éléments sont formés en plaçant l’indice de tableau de la cellule suivante (ou précédente) dans le champ Suivant ou Précédent d’un élément donné. Par example:

Indice Suivant Précédent Nom Solde
0 1 4 Jones, Jean 123,45
1 −1 0 Smith, Joseph 234,56
2 (tête de liste) 4 −1 Adam, Adam 0,00
3 Ignore, Ignace 999,99
4 0 2 Une autre, Anita 876.54
5
6
7

Dans l’exemple ci-dessus, ListHeadserait défini sur 2, l’emplacement de la première entrée de la liste. Notez que les entrées 3 et 5 à 7 ne font pas partie de la liste. Ces cellules sont disponibles pour tout ajout à la liste. En créant une ListFreevariable entière, une liste libre pourrait être créée pour garder une trace des cellules disponibles. Si toutes les entrées sont utilisées, la taille du tableau devra être augmentée ou certains éléments devront être supprimés avant que de nouvelles entrées puissent être stockées dans la liste.

Le code suivant parcourt la liste et affiche les noms et le solde du compte :

i := listHead while i ≥ 0 // boucle dans la liste print i, Records[i].name, Records[i].balance // affiche l’entrée i := Enregistrements[i].suivant

Face à un choix, les avantages de cette approche incluent :

  • La liste liée est relocalisable, ce qui signifie qu’elle peut être déplacée en mémoire à volonté, et elle peut également être rapidement et directement sérialisée pour être stockée sur disque ou transférée sur un réseau.
  • Surtout pour une petite liste, les index de tableau peuvent occuper beaucoup moins d’espace qu’un pointeur complet sur de nombreuses architectures.
  • La localité de référence peut être améliorée en gardant les nœuds ensemble en mémoire et en les réorganisant périodiquement, bien que cela puisse également être fait dans un magasin général.
  • Les alloueurs de mémoire dynamiques naïfs peuvent produire une quantité excessive de stockage supplémentaire pour chaque nœud alloué ; presque aucune surcharge d’allocation n’est encourue par nœud dans cette approche.
  • La saisie d’une entrée à partir d’un tableau pré-alloué est plus rapide que l’utilisation de l’Allocation de mémoire dynamique pour chaque nœud, car l’Allocation de mémoire dynamique nécessite généralement une recherche d’un bloc de mémoire libre de la taille souhaitée.

Cette approche a cependant un inconvénient majeur : elle crée et gère un espace mémoire privé pour ses nœuds. Cela conduit aux problèmes suivants :

  • Cela augmente la complexité de la mise en œuvre.
  • Développer un grand tableau lorsqu’il est plein peut être difficile, voire impossible, alors que trouver de l’espace pour un nouveau nœud de liste chaînée dans un grand pool de mémoire général peut être plus facile.
  • L’ajout d’éléments à un tableau dynamique prendra occasionnellement (lorsqu’il est plein) de manière inattendue linéaire ( O (n)) au lieu d’un temps constant (bien qu’il s’agisse toujours d’une constante amortie ).
  • L’utilisation d’un pool de mémoire général laisse plus de mémoire pour d’autres données si la liste est plus petite que prévu ou si de nombreux nœuds sont libérés.

Pour ces raisons, cette approche est principalement utilisée pour les langages qui ne prennent pas en charge l’allocation dynamique de mémoire. Ces inconvénients sont également atténués si la taille maximale de la liste est connue au moment de la création du tableau.

Support linguistique

De nombreux langages de programmation tels que Lisp et Scheme ont des listes chaînées intégrées. Dans de nombreux langages fonctionnels , ces listes sont construites à partir de nœuds, chacun appelé cellule contre ou contre . Le contre a deux champs : le car , une référence aux données de ce nœud, et le cdr , une référence au nœud suivant. Bien que les cellules contre puissent être utilisées pour construire d’autres structures de données, c’est leur objectif principal.

Dans les langages qui prennent en charge les types de données abstraits ou les modèles, des ADT ou des modèles de listes chaînées sont disponibles pour créer des listes chaînées. Dans d’autres langages, les listes liées sont généralement construites à l’aide de références et d’ enregistrements .

Stockage interne et externe

Lors de la construction d’une liste chaînée, on est confronté au choix de stocker les données de la liste directement dans les nœuds de la liste chaînée, appelée mémoire interne , ou simplement de stocker une référence aux données, appelée mémoire externe . Le stockage interne a l’avantage de rendre l’accès aux données plus efficace, nécessitant globalement moins de stockage, ayant une meilleure localité de référence et simplifiant la gestion de la mémoire pour la liste (ses données sont allouées et désallouées en même temps que les nœuds de la liste).

Le stockage externe, en revanche, a l’avantage d’être plus générique, en ce sens que la même structure de données et le même code machine peuvent être utilisés pour une liste chaînée, quelle que soit la taille des données. Cela facilite également le placement des mêmes données dans plusieurs listes liées. Bien qu’avec le stockage interne, les mêmes données puissent être placées dans plusieurs listes en incluant plusieurs références suivantes dans la structure de données du nœud, il serait alors nécessaire de créer des routines distinctes pour ajouter ou supprimer des cellules en fonction de chaque champ. Il est possible de créer des listes chaînées supplémentaires d’éléments qui utilisent un stockage interne en utilisant un stockage externe, et de faire en sorte que les cellules des listes chaînées supplémentaires stockent des références aux nœuds de la liste chaînée contenant les données.

En général, si un ensemble de structures de données doit être inclus dans des listes chaînées, le stockage externe est la meilleure approche. Si un ensemble de structures de données doit être inclus dans une seule liste liée, le stockage interne est légèrement meilleur, à moins qu’un package de liste liée générique utilisant un stockage externe ne soit disponible. De même, si différents ensembles de données pouvant être stockés dans la même structure de données doivent être inclus dans une seule liste chaînée, le stockage interne conviendrait.

Une autre approche qui peut être utilisée avec certains langages implique d’avoir des structures de données différentes, mais toutes ont les champs initiaux, y compris le suivant (et le précédentsi liste à double lien) références au même endroit. Après avoir défini des structures distinctes pour chaque type de données, une structure générique peut être définie qui contient la quantité minimale de données partagées par toutes les autres structures et contenues au sommet (début) des structures. Ensuite, des routines génériques peuvent être créées qui utilisent la structure minimale pour effectuer des opérations de type liste chaînée, mais des routines distinctes peuvent alors gérer les données spécifiques. Cette approche est souvent utilisée dans les routines d’analyse de messages, où plusieurs types de messages sont reçus, mais tous commencent par le même ensemble de champs, comprenant généralement un champ pour le type de message. Les routines génériques sont utilisées pour ajouter de nouveaux messages à une file d’attente lorsqu’ils sont reçus et les supprimer de la file d’attente afin de traiter le message.

Exemple de stockage interne et externe

Supposons que vous souhaitiez créer une liste chaînée de familles et de leurs membres. En utilisant le stockage interne, la structure peut ressembler à ceci :

record member { // membre d’un membre de la famille suivant ; chaîne firstName ; âge entier ; } record family { // la famille elle-même family next; chaîne lastName ; adresse de chaîne ; membre membres // tête de liste des membres de cette famille }

Pour imprimer une liste complète des familles et de leurs membres utilisant le stockage interne, nous pourrions écrire :

aFamily := Families // commence à la tête de la liste des familles tandis que aFamily ≠ null // boucle dans la liste des familles imprimer des informations sur la famille aMember := aFamily.members // obtient la tête de liste des membres de cette famille tandis que aMember ≠ null // boucle dans la liste des membres imprimer les informations sur le membre aMembre := aMembre.suivant uneFamille := uneFamille.suivant

En utilisant le stockage externe, nous créerions les structures suivantes :

noeud d’ enregistrement { // nœud de structure de lien générique suivant ; données de pointeur // pointeur générique pour les données au nœud } membre record { // structure pour le membre de la famille string firstName ; âge entier } record family { // structure for family string lastName ; corde ; node members // tête de liste des membres de cette famille }

Pour imprimer une liste complète des familles et de leurs membres utilisant un stockage externe, nous pourrions écrire :

famNode := Familles // commence à la tête de la liste des familles tandis que famNode ≠ null // boucle dans la liste des familles aFamily := (famille) famNode.data // extrait la famille du nœud imprimer des informations sur la famille memNode := aFamily.members // obtient la liste des membres de la famille tandis que memNode ≠ null // boucle dans la liste des membres aMember := (member)memNode.data // extrait le membre du nœud imprimer les informations sur le membre memNode := memNode.suivant famNode := famNode.suivant

Notez que lors de l’utilisation d’un stockage externe, une étape supplémentaire est nécessaire pour extraire l’enregistrement du nœud et le transtyper dans le type de données approprié. En effet, la liste des familles et la liste des membres de la famille sont stockées dans deux listes liées utilisant la même structure de données ( node ), et ce langage n’a pas de types paramétriques.

Tant que le nombre de familles auxquelles un membre peut appartenir est connu au moment de la compilation, le stockage interne fonctionne correctement. Si, toutefois, un membre devait être inclus dans un nombre arbitraire de familles, avec le nombre spécifique connu uniquement au moment de l’exécution, un stockage externe serait nécessaire.

Accélérer la recherche

Trouver un élément spécifique dans une liste chaînée, même s’il est trié, nécessite normalement un temps O( n ) ( recherche linéaire ). C’est l’un des principaux inconvénients des listes chaînées par rapport aux autres structures de données. En plus des variantes décrites ci-dessus, voici deux façons simples d’améliorer le temps de recherche.

Dans une liste non ordonnée, une heuristique simple pour diminuer le temps de recherche moyen est l’ heuristique de déplacement vers l’avant , qui déplace simplement un élément au début de la liste une fois qu’il est trouvé. Ce schéma, pratique pour créer des caches simples, garantit que les éléments les plus récemment utilisés sont également les plus rapides à retrouver.

Une autre approche courante consiste à ” indexer ” une liste chaînée en utilisant une structure de données externe plus efficace. Par exemple, on peut construire un arbre rouge-noir ou une table de hachage dont les éléments sont des références aux nœuds de la liste chaînée. Plusieurs de ces index peuvent être construits sur une seule liste. L’inconvénient est que ces index peuvent devoir être mis à jour chaque fois qu’un nœud est ajouté ou supprimé (ou du moins, avant que cet index ne soit réutilisé).

Listes à accès aléatoire

Une liste à accès aléatoire est une liste prenant en charge un accès aléatoire rapide pour lire ou modifier n’importe quel élément de la liste. [9] Une implémentation possible est une liste d’accès aléatoire binaire biaisée utilisant le système de nombres binaires biaisés , qui implique une liste d’arbres avec des propriétés spéciales; cela permet des opérations tête / contre en temps constant dans le pire des cas et un accès aléatoire en temps logarithmique dans le pire des cas à un élément par index. [9] Les listes à accès aléatoire peuvent être implémentées en tant que structures de données persistantes . [9]

Les listes à accès aléatoire peuvent être considérées comme des listes liées immuables en ce sens qu’elles prennent également en charge les mêmes opérations de tête et de queue O (1). [9]

Une extension simple aux listes à accès aléatoire est la min-list , qui fournit une opération supplémentaire qui produit l’élément minimum dans la liste entière en temps constant (sans [ clarification nécessaire ] complexités de mutation). [9]

Structures de données associées

Piles et files d’attente sont souvent implémentées à l’aide de listes liées et limitent simplement le type d’opérations prises en charge.

La liste de saut est une liste liée augmentée de couches de pointeurs pour sauter rapidement sur un grand nombre d’éléments, puis descendre à la couche suivante. Ce processus se poursuit jusqu’à la couche inférieure, qui est la liste réelle.

Un arbre binaire peut être vu comme un type de liste chaînée où les éléments sont eux-mêmes des listes chaînées de même nature. Le résultat est que chaque nœud peut inclure une référence au premier nœud d’une ou deux autres listes chaînées, qui, avec leur contenu, forment les sous-arbres sous ce nœud.

Une liste chaînée déroulée est une liste chaînée dans laquelle chaque nœud contient un tableau de valeurs de données. Cela améliore les performances du cache , car davantage d’éléments de liste sont contigus en mémoire, et réduit la surcharge de mémoire, car moins de métadonnées doivent être stockées pour chaque élément de la liste.

Une table de hachage peut utiliser des listes chaînées pour stocker les chaînes d’éléments qui se hachent à la même position dans la table de hachage.

Un tas partage certaines des propriétés d’ordre d’une liste chaînée, mais est presque toujours implémenté à l’aide d’un tableau. Au lieu de références d’un nœud à l’autre, les index de données suivant et précédent sont calculés à l’aide de l’index des données actuelles.

Une liste auto-organisée réorganise ses nœuds en fonction d’une heuristique qui réduit les temps de recherche pour la récupération des données en gardant les nœuds couramment consultés en tête de liste.

Remarques

  1. ^ La quantité de données de contrôle requises pour un tableau dynamique est généralement de la forme K + B ∗ n {displaystyle K+B*n} K+B*n K+B*n, où K {displaystyle K} K Kest une constante par tableau, B {displaystyle B} B Best une constante par dimension, et n {displaystyle n} n nest le nombre de dimensions. K {displaystyle K} K Ket B {displaystyle B} B Bsont généralement de l’ordre de 10 octets.

Références

  1. ^ Knuth, Donald (1998). L’art de la programmation informatique . Vol. 3 : Trier et rechercher (2e éd.). Addison-Wesley. p. 547.ISBN _ 978-0-201-89685-5.
  2. ^ un b “Copie archivée” . Archivé de l’original le 2015-09-23 . Récupéré le 31/07/2015 . {{cite web}}: Maint CS1 : copie archivée comme titre ( lien )
  3. ^ “Copie archivée” (PDF) . Archivé de l’original (PDF) le 2016-10-01 . Récupéré le 31/08/2021 . {{cite web}}: Maint CS1 : copie archivée comme titre ( lien )
  4. ^ Keynote du jour 1 – Bjarne Stroustrup : Style C++11 à GoingNative 2012 sur channel9.msdn.com à partir de la minute 45 ou de la feuille 44
  5. ^ Calcul des nombres : pourquoi vous ne devriez jamais, jamais, JAMAIS utiliser à nouveau la liste liée dans votre code sur kjellkod.wordpress.com
  6. ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert ; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Rapport technique CS-99-09) (PDF) , Département d’informatique, Université de Waterloo
  7. ^ un bc Chris Okasaki (1995). “Listes d’accès aléatoire purement fonctionnelles”. Actes de la septième conférence internationale sur les langages de programmation fonctionnels et l’architecture informatique : 86–95. doi : 10.1145/224164.224187 .
  8. ^ Ford, Guillaume; Topp, William (2002). Structures de données avec C ++ utilisant STL (deuxième éd.). Prentice Hall. p. 466–467. ISBN 0-13-085850-1.
  9. ^ un bcd Okasaki , Chris (1995). Listes d’accès aléatoire (PS) purement fonctionnelles . En langages de programmation fonctionnels et architecture informatique . Presse ACM. p. 86–95 . Consulté le 7 mai 2015 .

Lectures complémentaires

  • Juan, Ange (2006). “Ch20 – Structures de données ; ID06 – PROGRAMMATION avec JAVA (partie transparente du livre ‘Big Java’, par CayS. Horstmann)” (PDF) . p. 3. Archivé de l’original (PDF) le 2012-01-06 . Récupéré le 10/07/2011 .
  • Noir, Paul E. (2004-08-16). Pieterse, Vreda; Noir, Paul E. (éd.). “liste liée” . Dictionnaire des algorithmes et des structures de données . Institut national des normes et de la technologie . Récupéré le 14/12/2004 .
  • Antonakos, James L.; Mansfield, Kenneth C., Jr. (1999). Structures de données pratiques en C/C++ . Prentice Hall. p. 165–190 . ISBN 0-13-280843-9.
  • Collins, William J. (2005) [2002]. Structures de données et framework de collections Java . New York : McGraw Hill. p. 239–303. ISBN 0-07-282379-8.
  • Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2003). Introduction aux algorithmes . Presse du MIT. pp. 205–213, 501–505. ISBN 0-262-03293-7.
  • Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). “10.2 : Listes liées”. Introduction aux algorithmes (2e éd.). Presse du MIT. p. 204–209. ISBN 0-262-03293-7.
  • Vert, Bert F., Jr. (1961). “Langages informatiques pour la manipulation de symboles”. Transactions IRE sur les facteurs humains dans l’électronique (2): 3–8. doi : 10.1109/THFE2.1961.4503292 .
  • McCarthy, John (1960). “Fonctions récursives d’expressions symboliques et leur calcul par machine, partie I” . Communications de l’ACM . 3 (4): 184. doi : 10.1145/367177.367199 .
  • Knuth, Donald (1997). “2.2.3-2.2.5”. Algorithmes fondamentaux (3e éd.). Addison-Wesley. p. 254–298. ISBN 0-201-89683-4.
  • Newell, Allen ; Shaw, FC (1957). “Programmation de la machine de théorie logique”. Actes de la Western Joint Computer Conference : 230–240.
  • Parlante, Nick (2001). “Bases de la liste chaînée” (PDF) . Université Stanford . Récupéré le 21/09/2009 .
  • Sedgewick, Robert (1998). Algorithmes en C . Addison Wesley. p. 90–109 . ISBN 0-201-31452-5.
  • Shaffer, Clifford A. (1998). Une introduction pratique aux structures de données et à l’analyse d’algorithmes . New Jersey : Prentice Hall. p. 77–102. ISBN 0-13-660911-2.
  • Wilkes, Maurice Vincent (1964). “Une expérience avec un compilateur auto-compilant pour un langage de traitement de liste simple”. Bilan annuel en programmation automatique . Presse de Pergame. 4 (1) : 1. doi : 10.1016/0066-4138(64)90013-8 .
  • Wilkes, Maurice Vincent (1964). “Les listes et pourquoi elles sont utiles”. Produit de la conférence nationale ACM, Philadelphie 1964 . MCA (P–64) : F1–1.
  • Shanmugasundaram, Kulesh (2005-04-04). “Liste liée du noyau Linux expliquée” . Récupéré le 21/09/2009 .

Liens externes

Wikimedia Commons a des médias liés aux listes liées .
  • Description tirée du Dictionnaire des algorithmes et des structures de données
  • Introduction aux listes chaînées , Bibliothèque d’informatique de l’Université de Stanford
  • Problèmes de liste chaînée , Bibliothèque d’informatique de l’Université de Stanford
  • Structures de données ouvertes – Chapitre 3 – Listes chaînées , Pat Morin
  • Brevet pour l’idée d’avoir des nœuds qui sont dans plusieurs listes liées simultanément (notez que cette technique a été largement utilisée pendant de nombreuses décennies avant que le brevet ne soit accordé)

Plus