Dans quelles circonstances les listes chaînées sont-elles utiles?

La plupart du temps, je vois des gens essayer d'utiliser des listes chaînées, cela me semble être un mauvais (ou très mauvais) choix. Il serait peut-être utile d'explorer les circonstances dans lesquelles une liste chaînée est ou n'est pas un bon choix de structure de données.

Idéalement, les réponses expliqueraient les critères à utiliser pour sélectionner une structure de données et quelles structures de données sont susceptibles de fonctionner le mieux dans des circonstances spécifiques.

Edit: Je dois dire que je suis assez impressionné non seulement par le nombre, mais par la qualité des réponses. Je ne peux en accepter qu'un, mais il y en a deux ou trois de plus que j'aurais à dire qui auraient valu la peine d'être acceptés si quelque chose d'un peu mieux n'avait pas été là. Seul un couple (surtout celui que j'ai fini par accepter) a signalé des situations où une liste chaînée offrait un réel avantage. Je pense que Steve Jessop mérite une sorte de mention honorable pour avoir fourni non pas une, mais trois réponses différentes, que j'ai toutes trouvées assez impressionnantes. Bien sûr, même s'il n'a été publié que sous forme de commentaire, pas de réponse, je pense que l'article de blog de Neil vaut également la peine d'être lu - non seulement informatif, mais aussi très divertissant.

Ils peuvent être utiles pour les structures de données simultanées. (Il existe maintenant un exemple d'utilisation du monde réel non simultané ci-dessous - qui ne serait pas là si @Neil n'avait pas mentionné FORTRAN. ;-)

Par exemple, ConcurrentDictionary<TKey, TValue>dans .NET 4.0 RC, utilisez des listes liées pour chaîner les éléments hachés dans le même compartiment.

La structure de données sous-jacente pour ConcurrentStack<T>est également une liste chaînée.

ConcurrentStack<T>est l'une des structures de données qui servent de base au nouveau Thread Pool (avec les "files d'attente" locales implémentées sous forme de piles, essentiellement). (L'autre structure de support principale étant ConcurrentQueue<T>.)

Le nouveau pool de threads fournit à son tour la base de la planification du travail de la nouvelle bibliothèque parallèle de tâches .

Ils peuvent donc certainement être utiles - une liste chaînée sert actuellement de l'une des principales structures de soutien d'au moins une grande nouvelle technologie.

(Une liste à un seul lien fait un choix convaincant sans verrouillage - mais pas sans attente - dans ces cas, car les opérations principales peuvent être effectuées avec un seul CAS (+ tentatives). Dans un environnement GC-d moderne - tel que Java et .NET - le problème ABA peut facilement être évité. Enveloppez simplement les éléments que vous ajoutez dans des nœuds fraîchement créés et ne réutilisez pas ces nœuds - laissez le GC faire son travail. La page sur le problème ABA fournit également l'implémentation d'un verrou- Free stack - qui fonctionne réellement en .Net (& Java) avec un nœud (GC-ed) contenant les éléments.)

Edit : @Neil: en fait, ce que vous avez mentionné à propos de FORTRAN m'a rappelé que le même type de listes liées peut être trouvé dans la structure de données probablement la plus utilisée et la plus abusée de .NET: le générique .NET ordinaire Dictionary<TKey, TValue>.

Pas une, mais de nombreuses listes liées sont stockées dans un tableau.

• Cela évite de faire de nombreuses petites (dé) allocations sur les insertions / suppressions.
• Le chargement initial de la table de hachage est assez rapide, car le tableau est rempli séquentiellement (joue très bien avec le cache du processeur).
• Sans oublier qu'une table de hachage de chaînage est chère en termes de mémoire - et cette "astuce" réduit de moitié les "tailles de pointeurs" sur x64.

Essentiellement, de nombreuses listes liées sont stockées dans un tableau. (un pour chaque compartiment utilisé.) Une liste gratuite de nœuds réutilisables est "entrelacée" entre eux (s'il y a eu des suppressions). Un tableau est alloué au début / à la reprise et les nœuds de chaînes y sont conservés. Il existe également un pointeur libre - un index dans le tableau - qui suit les suppressions. ;-) Alors - croyez-le ou non - la technique FORTRAN est toujours d'actualité. (... et nulle part ailleurs, que dans l'une des structures de données .NET les plus couramment utilisées ;-).

Les listes liées sont très utiles lorsque vous devez faire beaucoup d'insertions et de suppressions, mais pas trop de recherche, sur une liste de longueur arbitraire (inconnue à la compilation).

Le fractionnement et la jonction de listes (liées de manière bidirectionnelle) sont très efficaces.

Vous pouvez également combiner des listes liées - par exemple, les structures arborescentes peuvent être implémentées sous forme de listes liées "verticales" (relations parent / enfant) reliant ensemble des listes liées horizontales (frères et sœurs).

L'utilisation d'une liste basée sur un tableau à ces fins présente de graves limitations:

• L'ajout d'un nouvel élément signifie que le tableau doit être réalloué (ou vous devez allouer plus d'espace que nécessaire pour permettre une croissance future et réduire le nombre de réaffectations)
• La suppression d'articles laisse de l'espace perdu ou nécessite une réallocation
• insérer des éléments n'importe où sauf la fin implique (éventuellement de réallouer et) de copier beaucoup de données d'une position vers le haut

Les listes liées sont très flexibles: avec la modification d'un pointeur, vous pouvez effectuer un changement massif, où la même opération serait très inefficace dans une liste de tableaux.

Les tableaux sont les structures de données auxquelles les listes liées sont généralement comparées.

Normalement, les listes liées sont utiles lorsque vous devez apporter beaucoup de modifications à la liste elle-même alors que les tableaux fonctionnent mieux que les listes sur l'accès direct aux éléments.

Voici une liste des opérations qui peuvent être effectuées sur les listes et les tableaux, par rapport au coût d'opération relatif (n = longueur de la liste / tableau):

• Ajout d'un élément:
  • sur les listes, il vous suffit d'allouer de la mémoire pour le nouvel élément et de rediriger les pointeurs. O (1)
  • sur les tableaux, vous devez déplacer le tableau. Sur)
• Supprimer un élément
  • sur les listes, vous ne faites que rediriger les pointeurs. O (1).
  • sur les tableaux, vous passez O (n) temps à déplacer le tableau si l'élément à supprimer n'est pas le premier ou le dernier élément du tableau; sinon vous pouvez simplement déplacer le pointeur vers le début du tableau ou diminuer la longueur du tableau
• Obtenir un élément dans une position connue:
  • sur les listes, vous devez parcourir la liste du premier élément à l'élément dans la position spécifique. Pire cas: O (n)
  • sur les tableaux, vous pouvez accéder immédiatement à l'élément. O (1)

Il s'agit d'une comparaison de très bas niveau de ces deux structures de données populaires et de base et vous pouvez voir que les listes fonctionnent mieux dans les situations où vous devez apporter beaucoup de modifications à la liste elle-même (suppression ou ajout d'éléments). En revanche, les tableaux fonctionnent mieux que les listes lorsque vous devez accéder directement aux éléments du tableau.

Du point de vue de l'allocation de mémoire, les listes sont meilleures car il n'est pas nécessaire d'avoir tous les éléments les uns à côté des autres. D'un autre côté, il y a le (petit) surcoût de stockage des pointeurs vers l'élément suivant (ou même vers l'élément précédent).

Il est important que les développeurs connaissent ces différences pour choisir entre des listes et des tableaux dans leurs implémentations.

Notez qu'il s'agit d'une comparaison de listes et de tableaux. Il existe de bonnes solutions aux problèmes signalés ici (par exemple: SkipLists, Dynamic Arrays, etc ...). Dans cette réponse, j'ai pris en compte la structure de données de base que tout programmeur devrait connaître.

La liste à liaison unique est un bon choix pour la liste gratuite dans un allocateur de cellules ou un pool d'objets:

1. Vous n'avez besoin que d'une pile, donc une liste à un seul lien suffit.
2. Tout est déjà divisé en nœuds. Il n'y a pas de surcharge d'allocation pour un nœud de liste intrusif, à condition que les cellules soient suffisamment grandes pour contenir un pointeur.
3. Un vecteur ou deque imposerait une surcharge d'un pointeur par bloc. Ceci est important étant donné que lorsque vous créez le tas pour la première fois, toutes les cellules sont gratuites, donc c'est un coût initial. Dans le pire des cas, il double le besoin de mémoire par cellule.

La liste doublement chaînée est un bon choix pour définir l'ordre d'un hashmap qui définit également un ordre sur les éléments (LinkedHashMap en Java), surtout lorsqu'il est ordonné par le dernier accès:

1. Plus de surcharge mémoire qu'un vecteur ou deque associé (2 pointeurs au lieu de 1), mais de meilleures performances d'insertion / suppression.
2. Pas de surcharge d'allocation, car vous avez de toute façon besoin d'un nœud pour une entrée de hachage.
3. La localité de référence n'est pas un problème supplémentaire par rapport à un vecteur ou à un deque de pointeurs, car vous devrez tirer chaque objet en mémoire de toute façon.

Bien sûr, vous pouvez vous demander si un cache LRU est une bonne idée en premier lieu, par rapport à quelque chose de plus sophistiqué et réglable, mais si vous allez en avoir un, c'est une implémentation assez décente. Vous ne voulez pas effectuer une suppression du milieu et un ajout à la fin sur un vecteur ou deque à chaque accès en lecture, mais déplacer un nœud vers la queue est généralement bien.

Les listes liées sont l'un des choix naturels lorsque vous ne pouvez pas contrôler où vos données sont stockées, mais que vous devez toujours passer d'un objet à l'autre.

Par exemple, lors de l'implémentation du suivi de la mémoire en C ++ (remplacement nouveau / suppression), vous avez besoin soit d'une structure de données de contrôle qui garde la trace des pointeurs qui ont été libérés, que vous devez entièrement implémenter vous-même. L'alternative consiste à surallouer et à ajouter une liste liée au début de chaque bloc de données.

Parce que vous savez toujours immédiatement où vous vous trouvez dans la liste lorsque la suppression est appelée, vous pouvez facilement abandonner la mémoire dans O (1). L'ajout d'un nouveau morceau qui vient d'être malaxé est également en O (1). Parcourir la liste est très rarement nécessaire dans ce cas, donc le coût O (n) n'est pas un problème ici (marcher une structure est de toute façon O (n)).

Ils sont utiles lorsque vous avez besoin d'une poussée, d'un pop et d'une rotation à grande vitesse, sans vous soucier de l'indexation O (n).

Les listes à liaison unique sont l'implémentation évidente du type de données commun «liste» dans les langages de programmation fonctionnelle:

1. L'ajout à la tête est rapide, et (append (list x) (L))et(append (list y) (L)) permet de partager presque toutes leurs données. Pas besoin de copier sur écriture dans une langue sans écriture. Les programmeurs fonctionnels savent comment en profiter.
2. L'ajout à la queue est malheureusement lent, mais il en serait de même pour toute autre implémentation.

Par comparaison, un vecteur ou deque serait généralement lent à ajouter à l'une ou l'autre extrémité, nécessitant (au moins dans mon exemple de deux appendices distincts) qu'une copie soit prise de la liste entière (vecteur), ou du bloc d'index et du bloc de données étant ajouté à (deque). En fait, il y a peut-être quelque chose à dire là-bas à propos de grandes listes qui doivent être ajoutées à la fin pour une raison quelconque, je ne suis pas suffisamment informé sur la programmation fonctionnelle pour juger.

Un exemple de bonne utilisation pour une liste chaînée est lorsque les éléments de la liste sont très volumineux. suffisamment grand pour qu'un ou deux seulement puissent tenir dans le cache du processeur en même temps. À ce stade, l'avantage des conteneurs de blocs contigus tels que les vecteurs ou les tableaux d'itération est plus ou moins annulé, et un avantage de performance peut être possible si de nombreuses insertions et suppressions se produisent en temps réel.

D'après mon expérience, la mise en œuvre de matrices clairsemées et de tas de fibonacci. Les listes liées vous permettent de mieux contrôler la structure globale de ces structures de données. Bien que je ne sois pas sûr que les matrices clairsemées soient mieux implémentées à l'aide de listes liées - il existe probablement un meilleur moyen, mais cela a vraiment aidé à apprendre les tenants et les aboutissants des matrices clairsemées à l'aide de listes liées dans CS de premier cycle :)

Il y a deux opérations complémentaires qui sont trivialement O (1) sur les listes et très difficiles à implémenter en O (1) dans d'autres structures de données - supprimer et insérer un élément à partir d'une position arbitraire, en supposant que vous devez maintenir l'ordre des éléments.

Les cartes de hachage peuvent évidemment faire l'insertion et la suppression dans O (1), mais vous ne pouvez pas parcourir les éléments dans l'ordre.

Compte tenu du fait ci-dessus, la carte de hachage peut être combinée avec une liste liée pour créer un cache LRU astucieux: une carte qui stocke un nombre fixe de paires clé-valeur et supprime la clé la moins récemment accédée pour faire de la place pour de nouvelles.

Les entrées de la mappe de hachage doivent avoir des pointeurs vers les nœuds de la liste liée. Lors de l'accès à la carte de hachage, le nœud de la liste liée est dissocié de sa position actuelle et déplacé vers la tête de la liste (O (1), oui pour les listes liées!). Lorsqu'il est nécessaire de supprimer l'élément le moins récemment utilisé, celui de la queue de la liste doit être supprimé (encore une fois O (1) en supposant que vous gardez le pointeur vers le nœud de queue) avec l'entrée de la carte de hachage associée (donc les backlinks de la liste de la carte de hachage sont nécessaires.)

Considérez qu'une liste chaînée peut être très utile dans une implémentation de style Domain Driven Design d'un système qui comprend des parties qui s'imbriquent avec la répétition.

Un exemple qui me vient à l'esprit pourrait être si vous deviez modéliser une chaîne suspendue. Si vous vouliez savoir quelle était la tension sur un lien particulier, votre interface pourrait inclure un getter pour le poids "apparent". La mise en œuvre de ce qui inclurait un lien demandant son prochain lien pour son poids apparent, puis ajoutant son propre poids au résultat. De cette façon, toute la longueur jusqu'en bas serait évaluée avec un seul appel du client de la chaîne.

Étant un partisan d'un code qui se lit comme un langage naturel, j'aime comment cela permettrait au programmeur de demander à un maillon de chaîne combien de poids il porte. Il garde également le souci de calculer ces enfants de propriétés dans les limites de l'implémentation du lien, supprimant ainsi le besoin d'un service de calcul de poids de chaîne ".

L'un des cas les plus utiles que je trouve pour les listes liées travaillant dans des domaines critiques pour les performances tels que le traitement de maillage et d'image, les moteurs physiques et le lancer de rayons est lorsque l'utilisation de listes liées améliore réellement la localité de référence et réduit les allocations de tas et parfois même réduit l'utilisation de la mémoire par rapport à les alternatives simples.

Maintenant, cela peut sembler être un oxymore complet que les listes liées pourraient faire tout cela car elles sont connues pour faire souvent le contraire, mais elles ont une propriété unique en ce que chaque nœud de liste a une taille et des exigences d'alignement fixes que nous pouvons exploiter pour permettre ils doivent être stockés de manière contiguë et supprimés en temps constant d'une manière que les choses de taille variable ne peuvent pas.

En conséquence, prenons un cas où nous voulons faire l'équivalent analogique de stocker une séquence de longueur variable qui contient un million de sous-séquences de longueur variable imbriquées. Un exemple concret est un maillage indexé stockant un million de polygones (certains triangles, certains quads, certains pentagones, certains hexagones, etc.) et parfois des polygones sont supprimés de n'importe où dans le maillage et parfois des polygones sont reconstruits pour insérer un sommet dans un polygone existant ou supprimer un. Dans ce cas, si nous stockons un million de minuscules std::vectors, nous nous retrouvons face à une allocation de tas pour chaque vecteur unique ainsi qu'à une utilisation de la mémoire potentiellement explosive. Un million de minuscules SmallVectorspeuvent ne pas souffrir autant de ce problème dans les cas courants, mais leur tampon préalloué qui n'est pas alloué séparément en tas peut toujours provoquer une utilisation explosive de la mémoire.

Le problème ici est qu'un million d' std::vectorinstances essaieraient de stocker un million de choses de longueur variable. Les objets de longueur variable ont tendance à vouloir une allocation de tas car ils ne peuvent pas très efficacement être stockés de manière contiguë et supprimés en temps constant (au moins de manière simple sans allocateur très complexe) s'ils ne stockent pas leur contenu ailleurs sur le tas.

Si, à la place, nous faisons ceci:

struct FaceVertex
{
    // Points to next vertex in polygon or -1
    // if we're at the end of the polygon.
    int next;
    ...
};

struct Polygon
{
     // Points to first vertex in polygon.
    int first_vertex;
    ...
};

struct Mesh
{
    // Stores all the face vertices for all polygons.
    std::vector<FaceVertex> fvs;

    // Stores all the polygons.
    std::vector<Polygon> polys;
};

... alors nous avons considérablement réduit le nombre d'allocations de tas et d'erreurs de cache. Au lieu d'exiger une allocation de tas et des échecs de cache potentiellement obligatoires pour chaque polygone auquel nous accédons, nous n'exigeons désormais cette allocation de tas que lorsque l'un des deux vecteurs stockés dans le maillage entier dépasse leur capacité (un coût amorti). Et bien que la foulée pour passer d'un sommet à l'autre puisse toujours causer sa part de ratés dans le cache, c'est encore souvent moins que si chaque polygone stockait un tableau dynamique séparé car les nœuds sont stockés de manière contiguë et il y a une probabilité qu'un sommet voisin puisse accessible avant l'expulsion (d'autant plus que de nombreux polygones ajouteront leurs sommets en même temps, ce qui rend la part du lion des sommets de polygones parfaitement contigus).

Voici un autre exemple:

... où les cellules de la grille sont utilisées pour accélérer la collision particule-particule pour, par exemple, 16 millions de particules se déplaçant à chaque image. Dans cet exemple de grille de particules, en utilisant des listes liées, nous pouvons déplacer une particule d'une cellule de la grille à une autre en changeant simplement 3 indices. L'effacement d'un vecteur et le repoussement vers un autre peuvent être considérablement plus coûteux et introduire plus d'allocations de tas. Les listes chaînées réduisent également la mémoire d'une cellule à 32 bits. Un vecteur, selon l'implémentation, peut préallouer son tableau dynamique au point où il peut prendre 32 octets pour un vecteur vide. Si nous avons environ un million de cellules de grille, c'est toute une différence.

... et c'est là que je trouve les listes chaînées les plus utiles de nos jours, et je trouve spécifiquement la variété «liste chaînée indexée» utile puisque les indices 32 bits divisent par deux les besoins en mémoire des liens sur les machines 64 bits et ils impliquent que le les nœuds sont stockés de manière contiguë dans un tableau.

Souvent, je les combine également avec des listes gratuites indexées pour permettre des suppressions et des insertions à temps constant n'importe où:

Dans ce cas, l' nextindex pointe vers le prochain index libre si le nœud a été supprimé ou vers le prochain index utilisé si le nœud n'a pas été supprimé.

Et c'est le cas d'utilisation numéro un que je trouve pour les listes liées de nos jours. Lorsque nous voulons stocker, par exemple, un million de sous-séquences de longueur variable faisant en moyenne, par exemple, 4 éléments chacun (mais parfois avec des éléments supprimés et ajoutés à l'une de ces sous-séquences), la liste chaînée nous permet de stocker 4 millions nœuds de liste chaînée contigus au lieu de 1 million de conteneurs qui sont chacun alloués individuellement par tas: un vecteur géant, c'est-à-dire pas un million de petits.

J'ai utilisé des listes liées (même des listes doublement liées) dans le passé dans une application C / C ++. C'était avant .NET et même stl.

Je n'utiliserais probablement pas de liste chaînée maintenant dans un langage .NET car tout le code de traversée dont vous avez besoin vous est fourni via les méthodes d'extension Linq.