Dans quelles circonstances sont liés listes utiles ?

Question

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

Idéalement, les réponses à exposer sur les critères utilisés dans la sélection d'une structure de données, et dont les structures de données sont susceptibles de travailler mieux, dans des circonstances précises.

Edit: je dois dire que je suis assez impressionné, non seulement par le nombre, mais la qualité des réponses. Je ne peux que l'accepter, mais il y a deux ou trois de plus, je dirais aurait été utile d'accepter si quelque chose d'un peu mieux n'avais pas été là. Seulement un couple (surtout celui que j'ai fini par accepter) a fait état de situations où une liste liée fourni un réel avantage. Je pense que Steve Jessop mérite une sorte de mention honorable pour venir avec non pas une, mais trois différentes réponses, tout ce que j'ai trouvé assez impressionnant. Bien sûr, même s'il a été publié uniquement comme un commentaire, pas une réponse, je pense que Neil est une entrée de blog est bien la peine de lire ainsi, non seulement instructif, mais assez divertissant aussi bien.

Answer 1

Les listes chaînées sont très utiles lorsque vous avez besoin de faire beaucoup d'insertions et de suppressions, mais pas trop de recherche, sur une liste de l'arbitraire (inconnu au moment de la compilation) de longueur.

Le fractionnement et l'adhésion (bidirectionnelle) la liste est très efficace.

Vous pouvez également combiner des listes liées - par exemple, les structures en arbre peut être mis en œuvre "verticale" des listes liées (relations parent/enfant) de la connexion, ensemble, horizontal listes chaînées (frères et sœurs).

L'utilisation d'un tableau en fonction de la liste, à ces fins, a de sérieuses limites:

• L'ajout d'un nouvel élément de la matrice doivent être transférés (ou vous devez allouer plus d'espace que vous avez besoin pour permettre la croissance future et de réduire le nombre de réaffectations)
• Suppression d'éléments de feuilles de l'espace perdu ou nécessite une réaffectation
• l'insertion d'éléments de n'importe où à l'exception de la fin implique (éventuellement, la réaffectation et l') la copie de beaucoup de données jusqu'à une position

Answer 2

Ils peuvent être utiles pour simultanés des structures de données. (Il y a maintenant un non-simultanées de l'usage du monde réel de l'échantillon ci - dessous-qui n'en seraient pas là si @Neil n'avait pas mentionné le FORTRAN. ;-)

Par exemple, ConcurrentDictionary<TKey, TValue> .NET 4.0 RC utilisation des listes liées à la chaîne des éléments de hachage pour le même seau.

Les données sous-jacentes de la structure pour ConcurrentStack<T> est également une liste liée.

ConcurrentStack<T> est l'une des structures de données qui servira de base pour le nouveau Pool de Threads, (avec la section locale de "files d'attente", mis en œuvre sous la forme de piles, essentiellement). (L'autre principale structure porteuse, ConcurrentQueue<T>.)

Le nouveau Pool de Threads à son tour, fournit la base pour la planification du travail de la nouvelle Task Parallel Library.

Donc ils peuvent certainement être utile - une liste chaînée est actuellement l'une des principales structures de support d'au moins une nouvelle technologie.

(Une liste liée individuellement fait une convaincante lock-gratuit - mais pas d'attente libre de choix dans ces cas, parce que les principales opérations peuvent être réalisées avec un seul CAS(+de tentatives). Dans un cadre moderne GC-d de l'environnement, tels que Java et .NET - l' ABA problème peut facilement être évité. Juste emballer les articles que vous ajoutez dans fraîchement créé nœuds et de ne pas réutiliser ces nœuds - laissez-le GC à faire son travail. La page sur l'ABA problème prévoit également la mise en œuvre d'une serrure sans pile qui fonctionne réellement .Net (&Java) avec un (GC-ed) Nœud de la tenue de la éléments.)

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

Pas un, mais plusieurs listes sont stockées dans un tableau.

• Il évite de faire de nombreuses petites (de)dotations sur les insertions/suppressions.
• Le chargement Initial de la table de hachage est assez rapide, parce que le tableau est rempli de manière séquentielle (joue très agréable avec de cache du PROCESSEUR).
• Pour ne pas mentionner que d'un chaînage de la table de hachage est cher en termes de mémoire et de ce "truc" coupes "pointeur tailles" dans la moitié sur x64.

Essentiellement, de nombreux listes chaînées sont stockées dans un tableau. (un pour chaque seau utilisé.) Une liste gratuite de réutilisables nœuds est "imbriqués" entre eux (comme si il y avait des suppressions). Un tableau est alloué à la start/sur le réchauffé, et les nœuds de chaînes sont conservés. Il est également libre de l'aiguille d'un index dans le tableau qui suit supprime. ;-) Alors, - croyez-le ou pas - le FORTRAN technique vit toujours. (...et nulle part ailleurs, que dans l'un des plus couramment utilisé .NET des structures de données ;-).

Answer 3

Listes chaînées sont très flexibles : avec la modification d’un seul pointeur, vous pouvez faire un changement massif, où la même opération serait très inefficace dans une liste de tableaux.

Answer 4

Les tableaux sont des structures de données à laquelle les Listes chaînées sont généralement comparés.

Normalement lié listes sont utiles lorsque vous devez faire beaucoup de modification à la liste elle-même, tandis que les tableaux se comporte mieux que les listes direct sur l'accès à l'élément.

Voici une liste d'opérations qui peuvent être effectuées sur les listes et les tableaux, en comparaison avec les coûts de fonctionnement (n = liste/longueur du tableau):

• L'ajout d'un élément:
  • sur les listes, vous avez juste besoin d'allouer de la mémoire pour le nouvel élément et la redirection de pointeurs. O(1)
  • sur les tableaux que vous avez à déplacer le tableau. O(n)
• Suppression d'un élément
  • sur la liste que vous venez de redirection de pointeurs. O(1).
  • sur les tableaux que vous passez O(n) le temps de 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 de la diminution de la longueur du tableau
• L'obtention d'un élément dans une position connue:
  • sur les listes, vous devez marcher sur la liste à partir du premier élément de l'élément dans la position spécifique. Pire cas: O(n)
  • sur les tableaux, vous pouvez accéder à l'élément immédiatement. O(1)

C'est un très faible niveau de comparaison de ces deux populaires et les structures de base de données et vous pouvez voir que les listes de meilleures performances dans les situations où vous devez faire beaucoup de modifications à la liste elle-même (ajout ou la suppression d'éléments). D'autre part les tableaux se comporte mieux que les listes quand vous avez un accès direct aux éléments de la matrice.

Du point de vue de l'allocation de mémoire, les listes sont mieux car il n'y a pas besoin d'avoir tous les éléments les uns à côté des autres. De l'autre côté il y a (un peu) les frais généraux de stocker les pointeurs à l'autre (ou même à la précédente) de l'élément.

La connaissance de ces différences est importante pour les développeurs à choisir entre des listes et des tableaux dans leur mise en œuvre.

Notez que c'est une comparaison des listes et des tableaux. Il y a de bonnes solutions pour les problèmes signalés (par exemple: SkipLists, Tableaux Dynamiques, etc...). Dans cette réponse, j'ai pris en compte la structure de base de données chaque programmeur doit connaître.

Answer 5

Liste liée individuellement est un bon choix pour la liste libre dans une cellule d'allocation ou de l'objet de la piscine:

1. Vous avez seulement besoin d'une pile, de sorte que une liste liée individuellement est suffisant.
2. Tout est divisé en nœuds déjà. Il n'y a pas d'attribution de frais généraux pour les intrusive liste nœud, à condition que les cellules sont assez grand pour contenir un pointeur.
3. Un vecteur ou deque imposerait une charge d'un pointeur par bloc. Ce qui est important étant donné que lorsque vous commencez à créer le tas, toutes les cellules sont libres, donc c'est un coût initial. Dans le pire des cas, il double la mémoire requise par cellule.