Quand dois-je utiliser une Liste vs une LinkedList

Quand est-il préférable d'utiliser un Liste vs un LinkedList?

  • Java q, ne devrait pas être très différent.
  • Veuillez envisager de modifier la accepté de répondre. La version actuelle est inexacte et extrêmement trompeur.
  • Veuillez envisager de modifier la accepté de répondre. La version actuelle est inexacte et extrêmement trompeur.
InformationsquelleAutor Jonathan Allen | 2008-10-04
  1. 96

    Modifier

    Veuillez lire les commentaires pour cette réponse. Les gens prétendent que je n'ai pas
    bon tests. Je suis d'accord cela ne doit pas être accepté de répondre. Comme je l'ai été
    l'apprentissage j'ai fait quelques tests et l'impression de les partager.

    Réponse originale à cette question...

    J'ai trouvé des résultats intéressants:

    //Temporary class to show the example
class Temp
{
    public decimal A, B, C, D;

    public Temp(decimal a, decimal b, decimal c, decimal d)
    {
        A = a;            B = b;            C = c;            D = d;
    }
}

    Liste chaînée (3,9 secondes)

            LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.AddLast(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

    Liste (2.4 secondes)

            List<Temp> list = new List<Temp>(); //2.4 seconds

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.Add(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

    Même si vous avez seulement accès à des données, essentiellement, il est beaucoup plus lent!! Je dis ne jamais utiliser une linkedList.

    Voici une autre comparaison effectuer un grand nombre de plaquettes (nous comptons sur l'insertion d'un élément au milieu de la liste)

    Liste chaînée (51 secondes)

            LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            var curNode = list.First;

            for (var k = 0; k < i/2; k++) //In order to insert a node at the middle of the list we need to find it
                curNode = curNode.Next;

            list.AddAfter(curNode, a); //Insert it after
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

    Liste (7.26 secondes)

            List<Temp> list = new List<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.Insert(i / 2, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

    Liste, après avoir tenu compte de l'emplacement où insérer (.04 secondes)

            list.AddLast(new Temp(1,1,1,1));
        var referenceNode = list.First;

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            list.AddBefore(referenceNode, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

    De sorte que si vous prévoyez sur l'insertion de plusieurs articles et vous aussi quelque part que la mention de l'endroit où vous prévoyez d'insérer l'élément, puis utiliser une liste chaînée. Juste parce que vous devez insérer un grand nombre d'éléments, qu'il ne veut pas en faire plus vite, car la recherche de l'emplacement où vous souhaitez insérer, il faut du temps.

    • Il y a un avantage pour les LinkedList sur la Liste (c'est .net spécifiques): étant donné que la Liste est soutenue par une batterie interne, il est affecté dans un bloc contigu. Si ce bloc alloué dépasse 85000 octets la taille, il sera alloué sur le Tas d'Objets Volumineux, non compactable génération. En fonction de la taille, cela peut conduire à la fragmentation de segment, d'une forme légère de fuite de mémoire.
    • Notez que si vous êtes ajoutant beaucoup (comme vous avez fait dans le dernier exemple) ou de la suppression de la première entrée, une liste chaînée sera presque toujours beaucoup plus rapide, car il n'y a pas de recherche ou de déplacement/copie de le faire. Une Liste nécessiterait le déplacement tout en place un endroit pour accueillir le nouveau poste, en faisant ajoutant un O(N) opérations.
    • Remarque: Cela semble tout à fait typique de TOUT lien de la liste de mise en œuvre, pas seulement .Net.
    • Ce qui est étrange. Pour les premiers résultats, il va à l'encontre de ce que @marc gravel et autres affiches mentionnées. par exemple: l'insertion et de l'avant de la traversée du temps doit être la même pour les deux LinkedList et de la Liste. des idées?
    • Je pense qu'il est intéressant de noter que la Liste est mis en œuvre à l'aide d'un tableau. Ce qui signifie que ce tableau doit être élargie une fois la liste dépasse la taille initiale. Qui est encore une fois un O(n) opérations. Contrairement à une linkedlist, il n'y a pas de storagemove nécessaires afin que nous n'ont pas cette coûteuse opération O(n). Alinked liste est principalement portée de main lors de l'ajout d'un grand nombre de données dans le début de la liste. Corrigez-moi si je me trompe.
    • Pourquoi la boucle list.AddLast(a); dans les deux dernières LinkedList exemples? - Je le faire une fois avant la boucle, comme avec list.AddLast(new Temp(1,1,1,1)); dans l'avant-dernier LinkedList, mais il semble (à moi) comme vous ajoutez deux fois autant de Temp objets dans les boucles elles-mêmes. (Et quand je double-vérifier moi-même avec une application de test, bien sûr, deux fois plus nombreux dans la LinkedList.)
    • la fragmentation du segment a rien en commun avec les fuites de mémoire
    • Strictement parlant, vrai - mais fragmentée LOH se présente de manière quasiment identique à une fuite de mémoire; la mémoire allouée va continuer à croître sans relâche.
    • Nam, si vous voulez ajouter un élément au début de la collection, puis LinkedList (O(1)) sera plus rapide que de dresser la Liste (O(n)), parce que la Liste aura pour décaler de n éléments à droite. C'est une honte que vous ne pouvez pas la chaîne ou de fusion d'une liste liée.
    • Il pourrait également être une bonne idée pour tester insérer au début de la liste, la LinkedList devrait être beaucoup plus rapide que la Liste à cette tâche.
    • N'est-ce pas normal de l'application, il tout à fait commun que vous avez seulement besoin de trouver "une fois"?? Sur le dessus de cela; la performance est assez biaisé, votre ajout de 2 éléments dans la liste liée, de sorte que la taille est 2 fois plus grand que la liste.
    • vous avez raison! Fondamentalement cHao fait la même remarque...
    • Je downvoted cette réponse. 1) votre conseil général I say never use a linkedList. est boiteuse, car votre post plus tard révèle. Vous pourriez voulez le modifier. 2) Quels sont vous un moment? L'instanciation, plus, et l'énumération complètement en une seule étape? Surtout, l'instanciation et l'énumération ne sont pas ce que ppl sont inquiets, ceux-ci sont un pas de temps. Plus précisément calendrier les inserts et les ajouts donnerait une meilleure idée. 3) le Plus important, vous êtes en train d'ajouter plus que nécessaire pour une linkedlist. C'est une mauvaise comparaison. Des écarts de fausse idée de linkedlist.
    • Désolé, mais Cette réponse est vraiment mauvais. S'il vous plaît ne PAS écouter cette réponse. la Raison en résumé: Il est complètement erronée de penser que la matrice soutenu la liste des implémentations sont assez stupides pour redimensionner le tableau sur chaque insertion. Les listes chaînées sont naturellement plus lent que le tableau adossés à des listes lors de la traversée ainsi que lors de l'insertion, à la fin, parce que seuls ils ont besoin pour créer de nouveaux objets, tandis que le tableau adossés à des listes d'utiliser un tampon (dans les deux sens, évidemment). La (mal fait) repères indiquent précisément que. La réponse ne parvient pas à vérifier les cas dans lesquels les listes chaînées sont préférables!
    • Downvoted cette "réponse" parce que tout d'abord, l'inexactitude flagrante de "nombre de secondes." Peut-être un type-o pour nanosecondes, mais flagrante et répétée, si mauvais. Aussi, l'API pour la Liste et LinkedList sont différents les uns des autres - ce qui fait que parfois on est correct et les autres est inapproprié. Donc, cette "réponse", qui affirme "ne jamais utiliser LinkedList" basée uniquement sur la performance pour une tâche donnée est inexacte. Je ne vais même pas regarder pour plus de défauts (qui, je suis sûr existent) dans cette réponse. Utiliser une réponse différente.
    • d'où la réponse allusion List<T> redimensionne tableau sur chaque insertion?
    • J'ai ajouté une réponse corriger OP mesures.
    • Je suis consterné de trouver la réponse choisie étant l'un entièrement donne sur la mise en œuvre d'une Liste/Tableau vs LinkedList à partir d'un ordinateur point de vue des sciences. C'est le parcours d'une Liste chaînée qui ralentit les choses!
    • C'est un complètement ignorant de réponse. Il ne devrait pas être la réponse choisie ou le résultat haut de la page!
    • Je me demande comment il obtient 101 upvotes...
    • Plupart du temps, je me demande pourquoi il n'a pas été supprimé, à la place. Étant donné que même SON auteur prétend que la réponse est fausse, il ne devrait pas avoir pris un mod trop de temps à se décider à le supprimer.

    InformationsquelleAutor Tono Nam
  2. 259

    Dans la plupart des cas, List<T> est plus utile. LinkedList<T> aura moins de coût lors de l'ajout/suppression d'éléments dans le milieu de la liste, alors que les List<T> ne peut à moindre coût ajouter/supprimer à la fin de la liste.

    LinkedList<T> est qu'il est plus efficace si vous accédez à des données séquentielles (soit en avant ou en arrière) à accès aléatoire est relativement cher, car il faut marcher sur la chaîne à chaque fois (donc pourquoi il n'a pas un indexeur). Toutefois, en raison du List<T> est essentiellement juste un tableau (avec un wrapper) à accès aléatoire est très bien.

    List<T> offre un grand nombre de méthodes de soutien - Find, ToArray, etc; cependant, ils sont également disponibles pour LinkedList<T> avec .NET 3.5/C# 3.0 via des méthodes d'extension - si c'est un facteur moins important.

    • Un des avantages de la Liste<> vs LinkedList<> que je n'y avais jamais pensé concerne la façon dont les microprocesseurs de mettre en œuvre la mise en cache de la mémoire. Bien que je ne comprends pas complètement, l'auteur de cet article de blog parle beaucoup de "localité de référence", ce qui rend la traversée d'un tableau beaucoup plus rapide que le parcours d'une liste liée, au moins si la liste chaînée est devenu quelque peu fragmentée en mémoire. kjellkod.wordpress.com/2012/02/25/...
    • La liste est mise en œuvre avec un tableau dynamique et les tableaux sont des blocs de mémoire contigus.
    • Depuis la Liste est un tableau dynamique, c'est pourquoi il est parfois bon de spécifier la capacité d'une Liste dans le constructeur si vous savez à l'avance.
    • pourquoi ce n'est pas la accepté de répondre?
    • Est-il possible que le C# de mise en œuvre de tous, array, List<T>, et LinkedList<T> est un peu sous-optimale pour une très importante affaire: Vous avez besoin d'une liste très importante, append (AddLast) et séquentielle de la traversée (dans un sens) sont tout à fait bien: je ne veux pas la matrice de redimensionnement pour obtenir des blocs continu (est-il garanti pour chaque tableau, même 20 GO tableaux?), et je ne sais pas à l'avance la taille, mais je peux deviner à l'avance la taille d'un bloc, par exemple, de 100 MO à réserver à chaque fois à l'avance. Ce serait une bonne mise en œuvre. Ou tableau/Liste de semblable à cela, et j'ai oublié un point ?
    • c'est le genre de scénario où vous écrivez votre propre cale sur votre bloc choisi la stratégie; List<T> et T[] échoue trop chunky (sur une dalle), LinkedList<T> gémiront d'être trop précis (la dalle par élément).
    • Oui. En attendant, je suis thinkig de la mise en œuvre d'une cale d'épaisseur de LinkedList<T> des tableaux de 10 mo ou quelque chose. La mise en œuvre pourrait être intéressant..
    • Si un Array réussit à l'allocation, il sera entièrement séquentielle; l'attribution faite dans Resize est new T[newSize]. tableau.cs. List en interne un Array, donc en est de même pour elle. LinkedList n'est pas ce que vous voulez quand vous avez un grand nombre d'éléments: il alloue un LinkedListNode par élément. Chaque LinkedListNode est d'une attribution distincte: il n'est pas un Array de quoi que ce soit. Pas de continuité. Un beaucoup de mémoire utilisée pour les boutons précédent/suivant les indicateurs. google c# LinkedList source code.

    InformationsquelleAutor Marc Gravell
  3. 202

    La pensée d'une liste, comme une liste peut être un peu trompeuse. C'est plus comme une chaîne. En fait, dans .NET, LinkedList<T> ne prend même pas la mettre en œuvre IList<T>. Il n'y a pas de véritable concept de l'index dans une liste liée, même si cela peut paraître, il est. Certainement pas les méthodes de la classe accepter index.

    Listes liées peuvent être individuellement liée, ou doublement chaînée. Cela signifie que chaque élément de la chaîne a un lien seulement à la prochaine (individuellement liée) ou à la fois à l'avant/à côté des éléments (doublement chaînée). LinkedList<T> est doublement chaînée.

    En interne, List<T> est soutenu par un tableau. Cela donne une très compact représentation en mémoire. À l'inverse, LinkedList<T> implique la mémoire supplémentaire pour stocker les liens bidirectionnels entre les éléments successifs. Donc, l'empreinte mémoire d'un LinkedList<T> sera généralement plus grande que pour List<T> (avec la réserve que List<T> peut avoir inutilisés interne des éléments d'un tableau afin d'améliorer les performances lors d'ajouter des opérations.)

    Ils ont différentes caractéristiques de performance trop:

    Ajouter

    • LinkedList<T>.AddLast(item) constante de temps
    • List<T>.Add(item) amorti à temps constant, linéaire pire des cas

    Ajouter

    • LinkedList<T>.AddFirst(item) constante de temps
    • List<T>.Insert(0, item) temps linéaire

    D'Insertion

    • LinkedList<T>.AddBefore(node, item) constante de temps
    • LinkedList<T>.AddAfter(node, item) constante de temps
    • List<T>.Insert(index, item) temps linéaire

    Suppression

    • LinkedList<T>.Remove(item) temps linéaire
    • LinkedList<T>.Remove(node) constante de temps
    • List<T>.Remove(item) temps linéaire
    • List<T>.RemoveAt(index) temps linéaire

    Compter

    • LinkedList<T>.Count constante de temps
    • List<T>.Count constante de temps

    Contient

    • LinkedList<T>.Contains(item) temps linéaire
    • List<T>.Contains(item) temps linéaire

    Clair

    • LinkedList<T>.Clear() temps linéaire
    • List<T>.Clear() temps linéaire

    Comme vous pouvez le voir, ils sont essentiellement équivalents. Dans la pratique, l'API de LinkedList<T> est de plus en plus lourde à utiliser, et les détails de ses besoins internes répandre dans votre code.

    Toutefois, si vous avez besoin de faire beaucoup d'insertions/retraits de l'intérieur d'une liste, il propose à temps constant. List<T> offre linéaire dans le temps, comme des éléments de la liste doivent être réorganisées après l'insertion/suppression.

    • C'est compter linkedlist constante? Je pensais que ce serait linéaire?
    • le comte est mis en cache à la fois de la liste des classes.
    • Vous avez écrit que "List<T>.Add(item) logarithmique du temps", mais il est en fait "Constante" si la capacité de la liste peut stocker le nouvel élément, et "Linéaire" si la liste n'ont pas assez d'espace et de nouveau à être réaffectés.
    • bien sûr, vous avez raison. Pas sûr de ce que je pensais dans l'au-dessus-peut-être que l'amorti, le cas normal, le temps est logarithmique, ce qui n'est pas. En fait, l'amorti, le temps est constante. Je n'ai pas dans le meilleur/pire des cas, des opérations visant à une simple comparaison. Je pense que l'opération d'ajout est suffisamment importante pour fournir ce détail cependant. Modifier la réponse. Merci.
    • Bonne réponse! Vous devez mentionner que l'accès indexé est de la constante de temps avec Liste mais linéaire avec LinkedList.
    • en fait LinkedList<T> n'ont pas de membre pour l'accès par index. Vous pouvez toujours le faire à l'aide d'un méthode d'extension basé sur la IEnumerable<T> qui propose bien entendu de temps linéaire de l'accès.
    • Qui n'a à l'évidence. :). Encore, c'est un avantage de Liste<T> que deservers mentionner.
    • Je suis complètement d'accord que c'est une touche de distinction. En fait, je pense que le nom de "liste" est trompeuse, même si bien sûr, c'est inclus dans le collectif de l'informatique conscience maintenant. Souhaitez-vous étendre sur le paragraphe d'ouverture, où je couvre ce que nous sommes en train de parler?
    • Je ne pense pas que le nom de la Liste est trompeuse dans le cas d'une liste liée. C'est trompeur dans le cas d'un tableau!
    • C'est de loin la meilleure réponse ici. Vous pouvez également ajouter Clear. Les deux sont des O(n). La charge de la mémoire pour LinkedList vaut la peine de noter. Déjà upvoted.
    • J'ai ajouté une section pour Clear. Le troisième paragraphe traite de l'utilisation de la mémoire. Souhaitez-vous ajouter?
    • Oui en effet vous avez discuté de l'utilisation de la mémoire, je viens de le dire. Légère correction, Clear est linéaire dans le temps, pas de temps constant pour les deux méthodes. Il est documenté dans msdn.
    • L'empreinte mémoire après le Clair est très différente, comme la Liste des<T> conserve sa taille, tandis que la LinkedList ne le fait pas.
    • Quelques réflexions sur l'ajout et ajoutant: 1. Liste<T>.AddItem(item) - faut-il être en O(1), depuis la Liste shoudn pas faire trop de calculs à la façon d'atteindre le dernier élément, non? 2.. Est une Liste<T>.Insert(0 point) pas fait en temps constant? considérant que l'Insertion en général serait O(n), en particulier de l'insert(0 point) aurait O(1) car la Liste n'a pas besoin de transpirer pour beaucoup de calculer où c'est l'indice 0 est, faut-il?
    • Si je comprends bien, Insert(0, élément) est en fait le pire des cas pour insérer depuis insérer à l'indice 0, la liste de la première est de déplacer tous les éléments d'un carré de côté avant d'insérer le nouvel élément. Je crois qu'il peut même être pire si elle a besoin de réaffecter le tableau par manque d'espace.
    • C'est le droit. Liste.Ajouter est considéré comme amorti à temps constant, parce que le coût de la croissance de ce tableau est répartie sur chacun de ses éléments N, en en faisant un facteur constant. Liste.Insérer est considéré comme linéaire parce que vous avez à déplacer les éléments pour faire de la place pour l'élément inséré. Techniquement, si vous insérez toujours à la fin, c'est la constante de temps, mais ensuite, vous pouvez simplement utiliser Ajouter de toute façon.
    • Je vois une contradiction dans quelques conclusions: étant Donné, que je ne se soucient de la vitesse d'Ajouter, ce qui est le mieux? Je veux remplir le récipient avec quelques millions de lignes de texte (ou tout autre cours d'eau), mais je ne m'inquiète pas pour la RAM: je n'ai plus besoin de se soucier de la vitesse Append (.Ajouter à la fin de la liste). C'est le plus important (canonique) de cas, des inserts au milieu, c'est autre chose: ----- Est-il préférable d'utiliser une LinkedList<T> oder List<T> ??
    • tu devrais peut-être commencer une nouvelle question, et vous ne dites pas comment vous allez utiliser cette structure de données une fois construit, mais si vous parlez d'un million de lignes que vous pourriez, comme une sorte d'hybride (liste liée de la matrice de morceaux ou similaire) pour réduire la fragmentation de segment, de réduire la surcharge de la mémoire, et en évitant un seul énorme objet sur la liturgie des heures.
    • votre commentaire ici "tout ce qui m'intéresse, c'est la vitesse Append" est en désaccord avec votre commentaire sur Marc Gravel de la réponse que vous avez besoin blocs continu. Soit vous pensez à deux usages très différents, ou si vous êtes confus au sujet de ce dont vous avez besoin. En cas de doute, utilisez List, et écrire un algorithme aussi simplement que vous le pouvez, sans préoccupation pour la performance. Une fois votre code fonctionne correctement dans tous les cas de test que vous pouvez penser, le temps que cela. Si assez vite, passer à une autre tâche.
    • Mes commentaires sont plus de l'intérêt principal de détails de la norme .NET et implémentations possibles des idées pour améliorer la sth. qu'un seul cas d'utilisation. Bien sûr, je suis conscient que chaque énoncé de rendement "dépend". Donc, ces deux remarques sur les deux réponses ne sont pas d'incidence sur le scénario identique. Mais généralement, il est bien sûr souhaitable à haute vitesse sur l'itération (localité de cache) comme pour les tableaux ainsi que pour l'insertion. L'insertion sur la fin d'un List (si le sous-jacent tableau est encore assez grande) devrait être assez rapide. L'insertion au début est bien sûr quelque chose d'autre.

    InformationsquelleAutor Drew Noakes
  4. 115

    Listes liées fournir très rapidement insertion ou la suppression d'un membre de la liste. Chaque membre dans une liste contient un pointeur vers le prochain membre de la liste de manière à insérer un membre à la position i:

    • mise à jour le pointeur de membre i-1 point pour le nouveau membre
    • définir le pointeur dans le nouveau membre à point à membre, je

    L'inconvénient d'une liste liée, c'est que l'accès aléatoire n'est pas possible. L'accès à un membre exige parcourant la liste jusqu'à ce que le membre est reconnu.

    • Je voudrais ajouter que les listes ont une surcharge par élément stocké implicite ci-dessus, via LinkedListNode qui fait référence à la précédente et le nœud suivant. Le paiement de ce qu'est un bloc contigu de mémoire n'est pas nécessaire pour stocker la liste, contrairement à un tableau en fonction de la liste.
    • N'est pas un bloc contigu de mémoire généralement préféraient?
    • Oui, un bloc contigu à l'est préféré pour un accès aléatoire de la performance et de la consommation de mémoire, mais pour les collections qui ont besoin de changer de taille régulièrement une structure telle qu'un Tableau général doivent être copiés vers un nouvel emplacement, alors qu'une liste liée seulement besoin de gérer la mémoire pour le nouvellement insérés ou supprimés nœuds.
    • Si vous avez déjà eu à travailler avec de très grands tableaux ou des listes (liste juste encapsule un tableau), vous allez commencer à courir dans des problèmes de mémoire, même si il semble y avoir suffisamment de mémoire disponible sur votre machine. La liste utilise une stratégie de doublement lorsqu'il alloue de nouveaux espaces sous-jacents du tableau. Ainsi, une 1000000 elemnt tableau complet sera copié dans un nouveau tableau avec 2000000 éléments. Ce nouveau tableau doit être créé dans une zone contiguë de l'espace mémoire qui est assez grand pour l'accueillir.
    • J'ai eu un cas précis où je n'ai fait que l'ajout et la suppression, et en boucle, un par un... ici la liste chaînée est de loin supérieure à la normale de la liste..
    • si combiner Double Liste chaînée avec un Dictionnaire, vous pouvez obtenir O(1) de la vitesse au moment de l'insertion, la suppression et l'accès trop.
    • Pour ajouter à @ALZ point: "fast" insertion de LinkedList aide seulement quand vous avez un référence à l'élément à insérer, avant ou après. si vous avez de recherche pour l'élément, alors le temps sera dominé par la recherche linéaire. Si chaque élément est associé à un clé unique, puis une Dictionary cartographie clé de l'élément vous donnera l'élément en O(1) fois. (E. g. si chaque élément a une int Id, et vous êtes de passage autour de ces Ids plutôt que de passer autour de références à des éléments, vous aurez envie cette Dictionary.)
    • re "random access n'est pas possible": que partiellement vrai. Si vous écrivez des algorithmes qui passent autour de références à les nœuds, puis LinkedList est supérieur à la Liste dans la manipulation de l' "aléatoire" éléments, si les insertions/suppressions sont fait n'importe où, mais à la fin de la collection. Dès que vous insérer/supprimer dans le milieu, toute la Liste des indices de devenir invalide, et l'avantage de la Liste est perdu. Tandis que si votre algorithme est la tenue d'un node, il peut encore examiner les éléments avant/après de manière efficace. Pour certains algorithmes, ce qui donne des performances supérieures.

    InformationsquelleAutor b3.
  5. 17

    La différence entre la Liste et le LinkedList réside dans leur implémentation sous-jacente. La liste est basé sur les tableau de la collection (ArrayList). LinkedList est le nœud du pointeur de la collection en fonction de (LinkedListNode). Sur le niveau de l'API d'utilisation, tous les deux sont à peu près la même depuis deux mettre en œuvre même ensemble d'interfaces telles que ICollection, IEnumerable, etc.

    La principale différence vient lorsque le rendement de la matière. Par exemple, si vous êtes à la mise en œuvre de la liste qui a de lourdes "INSÉRER" de l'opération, LinkedList surpasse la Liste. Depuis LinkedList pouvez le faire en O(1) fois, mais la Liste peut-être besoin d'élargir la taille des sous-jacents au tableau. Pour plus de renseignements/détails vous pouvez lire sur l'algorithmique différence entre LinkedList et structures de données de tableau. http://en.wikipedia.org/wiki/Linked_list et Tableau

    Espérons que cette aide,

    • Liste<T> est array (T []), pas d'un ArrayList base. Re insérer: le tableau de redimensionnement n'est pas le problème (le doublement de l'algorithme de signifie que, la plupart du temps, il n'a pas à faire ça): le problème, c'est qu'il doit bloc-copie de toutes les données existantes en premier, ce qui prend un peu de temps.
    • le "doubler" algorithme ne fait que O(logN), mais il est encore pire que O(1)
    • Mon point est qu'elle n'est pas la redimensionner ce qui provoque la douleur - c'est le blit. Tellement pire des cas, si nous ajoutons la première (zéro) de l'élément à chaque fois, puis le blit a pour tout déplacer à chaque fois.
    • vous envisagez le cas où Add est toujours à la fin du tableau existant. List est "assez bon" à qui, même si pas d'O(1). Le grave problème se produit si vous avez besoin de nombreuses Adds qui sont pas à la fin. Marc est de souligner que la nécessité de déplacer données existantes tous fois que vous insérez (et pas seulement lors de la redimensionner si nécessaire) est un plus considérable des performances du coût de List.
    • Le problème est Théorique Big O notations ne disent pas toute l'histoire. En informatique c'est tout ce que quiconque se soucie, mais il ya beaucoup plus à se préoccuper que ce, dans le monde réel.
    InformationsquelleAutor user23117
  6. 15

    Ma réponse précédente n'a pas été assez précis.
    Que vraiment c'était horrible 😀
    Mais maintenant je peux poster beaucoup plus utile et de bonne réponse.

    J'ai fait quelques tests supplémentaires. Vous pouvez le trouver à la source par le lien suivant et de les enregistrer sur votre environnement par votre propre: https://github.com/ukushu/DataStructuresTestsAndOther.git

    Courte résultats:

    • Tableau nécessité d'utiliser:

      • Aussi souvent que possible. C'est rapide et prend la plus petite de RAM gamme pour la même quantité d'information.
      • Si vous connaissez nombre exact de cellules nécessaires
      • Si les données enregistrées dans le tableau < 85000 b
      • Si besoin élevé d'Accès Aléatoire de la vitesse

    • Liste d'utilisation:

      • Si nécessaire pour ajouter des cellules à la fin de la liste (souvent)
      • Si nécessaire pour ajouter des cellules en début/milieu de la liste (PAS SOUVENT)
      • Si les données enregistrées dans le tableau < 85000 b
      • Si besoin élevé d'Accès Aléatoire de la vitesse

    • LinkedList besoin d'utiliser:

      • Si nécessaire pour ajouter des cellules en début/milieu/fin de la liste (souvent)
      • Si besoin seulement de l'accès séquentiel (avant/arrière)
      • Si vous avez besoin d'enregistrer des éléments de GRANDE taille, mais les éléments de comptage est faible.
      • Mieux ne pas utiliser pour un grand nombre d'éléments, comme c'est l'utilisation de la mémoire supplémentaire pour les liens.

    Plus de détails:

    Quand dois-je utiliser une Liste vs une LinkedList
    Intéressant de savoir:

    1. LinkedList<T> en interne n'est pas une Liste dans .NET. Il est même à ne pas mettre en œuvre IList<T>. Et c'est pourquoi il y a absence d'index et des méthodes liées à l'index.

    2. LinkedList<T> est le nœud du pointeur de la collection. Dans .NET il est en doublement chaînée de mise en œuvre. Cela signifie que suivant/précédent éléments en lien à l'élément courant. Et les données sont fragmentées -- les différents objets de la liste peuvent être situés dans différents endroits de la RAM. Il y aura aussi plus de mémoire utilisé pour LinkedList<T> que pour List<T> ou d'un Tableau.

    3. List<T> dans .Net est de Java alternative de ArrayList<T>. Cela signifie que ce est la matrice de wrapper. Il est donc alloué dans la mémoire comme un bloc contigu de données. Si les données allouées taille dépasse 85000 octets, il sera déplacé vers des Objets Volumineux. En fonction de la taille, cela peut conduire à la fragmentation du segment(une forme bénigne de la fuite de mémoire). Mais dans le même temps, si la taille de l' < 85000 octets -- très compact et rapide d'accès à la représentation dans la mémoire.

    4. Seul bloc contigu est préféré pour un accès aléatoire de la performance et de la consommation de mémoire, mais pour les collections qui ont besoin de changer de taille régulièrement une structure telle qu'un Tableau général doivent être copiés vers un nouvel emplacement, alors qu'une liste liée seulement besoin de gérer la mémoire pour le nouvellement insérés ou supprimés nœuds.

    • Question: "les données enregistrées dans le tableau < ou > 85.000 octet" tu veux dire que les données par matrice/ÉLÉMENT de liste en pensez-vous? Il pourrait être entendu que de vous dire la données. datasize de l'ensemble de la baie..
    • Les éléments du tableau situé de façon séquentielle dans la mémoire. Donc, par tableau. Je sais à propos de l'erreur dans le tableau, plus tard, je vais corriger ça 🙂 ( j'espère.... )
    • Avec les listes de la lenteur à inserts, si une liste a beaucoup de redressement (beaucoup d'insertions/suppressions) est la mémoire occupée par l'espace supprimé conservés et, si oui, est-ce que les "re"-inserts plus vite?
    InformationsquelleAutor Andrew
  7. 11

    Le principal avantage de listes liées au fil des tableaux, les liens nous fournir la capacité de réorganiser les éléments de manière efficace.
    Sedgewick, p. 91

    • De l'OMI, ce devrait être la réponse. LinkedList sont utilisés lors de la garantie de l'ordre est important.
    • Je ne suis pas d'accord. Cela dépend du niveau dont on parle. L'algorithmique est différente de la machine-niveau de mise en œuvre. Pour la vitesse de la considération que vous besoin de celui-ci aussi. Comme il est souligné, les tableaux sont mis en œuvre de "un gros morceau" de mémoire ce qui est une restriction, car cela peut conduire à de redimensionnement et de réorganisation de la mémoire, en particulier avec de très grands tableaux. Après réflexion, un spécial propre structure de données, une liste de tableaux serait une idée pour donner un meilleur contrôle sur la vitesse de remplissage linéaire et d'accéder à de très grandes structures de données.
    • Je upvoted votre commentaire, mais je tiens à souligner que vous décrivez une exigence différente. Quelle est la réponse de dire, c'est que la liste liée a avantage en termes de performances pour les algorithmes qui impliquent un grand nombre de réorganiser d'éléments. Étant donné que, je interpréter RBaarda commentaire comme se référant à la nécessité d'ajouter/supprimer des éléments tout en conservant une donnée de commande (critères de tri). Donc pas de "remplissage linéaire". Compte tenu de cela, la Liste des pertes, parce que les indices sont inutiles (change chaque fois que vous ajoutez un élément n'importe où, mais à la fin de la queue).
    InformationsquelleAutor Dr. Alrawi
  8. 2

    Quand vous en avez besoin intégrée de l'accès indexé, le tri (et d'après ce binaire de recherche), et "ToArray()" la méthode, vous devez utiliser la Liste.

    InformationsquelleAutor Michael Damatov
  9. 2

    Une circonstance commune à utiliser LinkedList est comme ceci:

    Supposons que vous souhaitez supprimer de nombreux de certaines chaînes de caractères à partir d'une liste de chaînes de caractères avec une grande taille, disons de 100 000. Les chaînes de caractères à supprimer peut être recherché dans HashSet dic, et la liste des chaînes est censé contenir entre 30 000 à 60 000 chaînes à supprimer.

    Alors quel est le meilleur type de Liste pour le stockage de 100 000 Chaînes? La réponse est LinkedList. S'ils sont stockés dans une liste de tableaux, puis en itérant sur elle et la suppression de Chaînes mises en correspondance devait prendre place
    pour des milliards d'opérations, alors qu'il faut juste autour de 100 000 opérations à l'aide d'un itérateur et la méthode remove ().

    LinkedList<String> strings = readStrings();
HashSet<String> dic = readDic();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){
    String string = iterator.next();
    if (dic.contains(string))
    iterator.remove();
}
    • Vous pouvez simplement utiliser RemoveAll pour supprimer les éléments d'une List sans déplacement d'un grand nombre d'articles autour de, ou de l'utilisation Where de LINQ pour créer une seconde liste. À l'aide d'un LinkedList ici, cependant, finit par consommer de de façon spectaculaire plus de mémoire que d'autres types de collections et de la perte de mémoire d'une localité signifie qu'il sera beaucoup plus lent que l'itération, ce qui en fait assez un peu de pire qu'un List.
    • notez que @Tom réponse de l'utilisation de Java. Je ne sais pas si il y a un RemoveAll équivalent en Java.
    • Ainsi la question précise qu'il s'agit .NET, de sorte que tout à fait la réponse que beaucoup moins approprié.
    • alors vous devriez avoir mentionné que, depuis le début.
    • Si RemoveAll n'est pas disponible pour List, vous pourriez faire un "compactage" de l'algorithme, ce qui pourrait ressembler à Tom boucle, mais avec deux indices et de la nécessité de déplacer des éléments à être conservés une à une vers le bas dans la liste du tableau interne. L'efficacité est O(n), le même que Tom algorithme de LinkedList. Dans les deux versions, le temps de calculer le HashSet clé pour les chaînes qui le domine. Ce n'est pas un bon exemple de cas d'utilisation LinkedList.
    InformationsquelleAutor Tom
  10. 1

    C'est adapté de Tono Nam's accepté de répondre à corriger de petites erreurs de mesures en elle.

    Le test: 

    static void Main()
{
    LinkedListPerformance.AddFirst_List(); //12028 ms
    LinkedListPerformance.AddFirst_LinkedList(); //33 ms

    LinkedListPerformance.AddLast_List(); //33 ms
    LinkedListPerformance.AddLast_LinkedList(); //32 ms

    LinkedListPerformance.Enumerate_List(); //1.08 ms
    LinkedListPerformance.Enumerate_LinkedList(); //3.4 ms

    //I tried below as fun exercise - not very meaningful, see code
    //sort of equivalent to insertion when having the reference to middle node

    LinkedListPerformance.AddMiddle_List(); //5724 ms
    LinkedListPerformance.AddMiddle_LinkedList1(); //36 ms
    LinkedListPerformance.AddMiddle_LinkedList2(); //32 ms
    LinkedListPerformance.AddMiddle_LinkedList3(); //454 ms

    Environment.Exit(-1);
}

    Et le code:

    using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace stackoverflow
{
static class LinkedListPerformance
{
class Temp
{
public decimal A, B, C, D;
public Temp(decimal a, decimal b, decimal c, decimal d)
{
A = a; B = b; C = c; D = d;
}
}
static readonly int start = 0;
static readonly int end = 123456;
static readonly IEnumerable<Temp> query = Enumerable.Range(start, end - start).Select(temp);
static Temp temp(int i)
{
return new Temp(i, i, i, i);
}
static void StopAndPrint(this Stopwatch watch)
{
watch.Stop();
Console.WriteLine(watch.Elapsed.TotalMilliseconds);
}
public static void AddFirst_List()
{
var list = new List<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
list.Insert(0, temp(i));
watch.StopAndPrint();
}
public static void AddFirst_LinkedList()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (int i = start; i < end; i++)
list.AddFirst(temp(i));
watch.StopAndPrint();
}
public static void AddLast_List()
{
var list = new List<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
list.Add(temp(i));
watch.StopAndPrint();
}
public static void AddLast_LinkedList()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (int i = start; i < end; i++)
list.AddLast(temp(i));
watch.StopAndPrint();
}
public static void Enumerate_List()
{
var list = new List<Temp>(query);
var watch = Stopwatch.StartNew();
foreach (var item in list)
{
}
watch.StopAndPrint();
}
public static void Enumerate_LinkedList()
{
var list = new LinkedList<Temp>(query);
var watch = Stopwatch.StartNew();
foreach (var item in list)
{
}
watch.StopAndPrint();
}
//for the fun of it, I tried to time inserting to the middle of 
//linked list - this is by no means a realistic scenario! or may be 
//these make sense if you assume you have the reference to middle node
//insertion to the middle of list
public static void AddMiddle_List()
{
var list = new List<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
list.Insert(list.Count / 2, temp(i));
watch.StopAndPrint();
}
//insertion in linked list in such a fashion that 
//it has the same effect as inserting into the middle of list
public static void AddMiddle_LinkedList1()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
LinkedListNode<Temp> evenNode = null, oddNode = null;
for (int i = start; i < end; i++)
{
if (list.Count == 0)
oddNode = evenNode = list.AddLast(temp(i));
else
if (list.Count % 2 == 1)
oddNode = list.AddBefore(evenNode, temp(i));
else
evenNode = list.AddAfter(oddNode, temp(i));
}
watch.StopAndPrint();
}
//another hacky way
public static void AddMiddle_LinkedList2()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start + 1; i < end; i += 2)
list.AddLast(temp(i));
for (int i = end - 2; i >= 0; i -= 2)
list.AddLast(temp(i));
watch.StopAndPrint();
}
//OP's original more sensible approach, but I tried to filter out
//the intermediate iteration cost in finding the middle node.
public static void AddMiddle_LinkedList3()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
{
if (list.Count == 0)
list.AddLast(temp(i));
else
{
watch.Stop();
var curNode = list.First;
for (var j = 0; j < list.Count / 2; j++)
curNode = curNode.Next;
watch.Start();
list.AddBefore(curNode, temp(i));
}
}
watch.StopAndPrint();
}
}
}

    Vous pouvez le voir, les résultats sont en conformité avec la performance théorique d'autres ont documenté ici. Tout à fait clair - LinkedList<T> gains gros temps dans le cas d'insertions. Je n'ai pas testé pour le retrait du milieu de la liste, mais le résultat devrait être le même. Bien sûr List<T> a d'autres domaines où il effectue une façon mieux comme O(1) à accès aléatoire.

    InformationsquelleAutor nawfal
  11. 1

    Essentiellement, un List<> dans .NET est un wrapper sur un tableau. Un LinkedList<> est une liste liée. Donc, la question revient à, quelle est la différence entre un tableau et une liste chaînée, et quand un tableau sera utilisé à la place d'une liste chaînée. Probablement les deux facteurs les plus importants dans votre décision d'utiliser allait descendre pour:

    • Listes liées bien meilleure insertion/retrait de la performance, tant que les insertions/suppressions ne sont pas sur le dernier élément de la collection. C'est parce qu'un tableau doit passer tous les autres éléments qui viennent après l'insertion/retrait de point. Si l'insertion/retrait est à la fin de la queue de la liste, cependant, ce changement n'est pas nécessaire (bien que le tableau peut avoir besoin d'être redimensionnée si sa capacité est dépassée).
    • Tableaux ont beaucoup mieux accéder aux fonctionnalités. Les tableaux peuvent être indexé directement (en temps constant). Les listes liées doivent être parcourus (temps linéaire).
    InformationsquelleAutor iliketocode
  12. 0

    Je suis d'accord avec la plupart de la remarque faite ci-dessus. Et je suis aussi d'accord que la Liste ressemble à un choix plus évident, dans la plupart des cas.

    Mais, je veux juste ajouter qu'il y a de nombreux cas où LinkedList sont un bien meilleur choix que de Liste, pour une meilleure efficacité.

    1. Supposons que vous traversez à travers les éléments et que vous voulez effectuer beaucoup d'insertions et des suppressions; LinkedList est-il linéaire O(n), tandis que la Liste ne quadratique O(n^2).
    2. Supposons que vous souhaitez accéder à des objets plus grands, encore et encore, LinkedList devenir plus très utile.
    3. Deque() et file() sont mieux mises en œuvre à l'aide de LinkedList.
    4. L'augmentation de la taille de la LinkedList est beaucoup mieux et plus facile une fois que vous faites affaire avec de nombreux et des objets plus grands.

    Espère que quelqu'un aurait trouver ces commentaires utiles.

    • Noter que cet avis est pour .NET, pas de Java. En Java de la liste liée de mise en œuvre, vous n'avez pas le concept d'un "nœud", de sorte que vous avez à parcourir la liste pour chaque et chaque insertion.
    • Cette réponse n'est que partiellement correcte: 2) si des éléments sont grandes, puis faire le type d'élément à une Classe et non un Struct, de sorte que la Liste tient simplement une référence. Ensuite, la taille de l'élément devient hors de propos. 3) Deque et la file d'attente peut d'intervenir efficacement dans une Liste si vous utiliser la Liste comme un "tampon circulaire", au lieu de faire d'insérer ou de retirer à démarrer. StephenCleary de la Deque. 4) partiellement vrai: quand beaucoup les objets, les pro de LL n'avez pas besoin énorme de mémoire contiguë; la baisse est de la mémoire supplémentaire pour le nœud de pointeurs.
    InformationsquelleAutor Abhishek Kumar Singh
  13. -1

    Utilisation LinkedList<> quand

    1. Vous ne savez pas combien d'objets sont à venir par l'inondation porte. Par exemple, Token Stream.
    2. Quand vous avez SEULEMENT envie de supprimer\insérez les extrémités.

    Pour tout le reste, il est préférable d'utiliser List<>.

    • Je ne vois pas pourquoi le point 2 du sens. Les listes chaînées sont grands quand vous êtes en train de faire de nombreuses insertions/délétions tout au long de l'ensemble de la liste.
    • En raison du fait que LinkedLists ne sont pas basées sur l'Indice, vous avez vraiment besoin de numériser la totalité de la liste de l'insertion ou de la suppression qui engage un O(n) pénalité. Liste<> d'autre part, souffre d'un Tableau de redimensionnement, mais encore,OMI, est une meilleure option lorsque comparé à LinkedLists.
    • Vous n'avez pas à parcourir la liste pour les insertions/délétions si vous gardez une trace de la LinkedListNode<T> objets dans votre code. Si vous pouvez faire cela, alors c'est beaucoup mieux que d'utiliser List<T>, en particulier pour les très longues listes où les insertions/suppressions sont fréquentes.
    • Tu veux dire à travers une table de hachage? Si c'est le cas, ce serait l'espace typique\time compromis que chaque programmeur doit faire un choix basé sur le domaine du problème 🙂 Mais oui, ce serait le rendre plus rapide.
    • Non, il veut dire en passant autour de références à des nœuds au lieu de les passer autour de des références à des éléments. Si vous ne disposez que d'un élément, puis sur deux Liste et LinkedList ont de mauvaises performances, parce que vous avez à la recherche. Si vous pensez "mais avec la Liste je peux juste passer un index": c'est uniquement valide lorsque vous ne jamais insérer un nouvel élément dans le milieu de la Liste. LinkedList n'a pas cette limitation, si vous tenez sur un node (et l'utilisation de node.Value chaque fois que vous le souhaitez à l'élément d'origine). Afin de vous réécrire l'algorithme de travailler avec des nœuds, pas les valeurs brutes.
    • Le Point 1) est parfois vrai, parfois non. Le baisse de LinkedList, où il pourrait être la beaucoup objets, et les objets sont de petite taille, est que chaque objet nécessite une allocation supplémentaire - le LinkedListNode qui est créé lorsque vous l'Ajoutez à la LinkedList. Le envers est que vous n'avez pas à acquérir un seul espace contigu de mémoire, de manière à éviter un éventuel problème de fragmentation de la mémoire. (Je n'ai jamais trouvé le coût de performances de Listinternes Redimensionner à être importante; son comment la mémoire est utilisée dans la pratique.)
    • Comme Drew points, Point 2) est discutable. L'habituel argument en faveur de la LinkedList est quand vous avez besoin de supprimer/insérer un n'importe où sauf à la queue. La liste a pour déplacer des données existantes. LinkedList ne le fait pas. Votre argument dans un commentaire que "vous avez vraiment besoin de numériser l'ensemble de la liste" signifie que vous êtes réflexion à propos des algorithmes où les indices ne change pas. En effet, la Liste est bon dans ces cas -, mais dès que vous supprimer/insérer dans le milieu d'une liste, les indices actuels sont inutiles. Si la Liste n'est pas bon dans ces cas. Vous avez à l'envers; "au milieu de la liste", c'est quand LinkedList victoires sur la Liste.

    InformationsquelleAutor Antony Thomas
  14. -1

    Donc beaucoup de la moyenne des réponses ici...

    Certains sont liés liste des implémentations d'utiliser des blocs de pré alloué nœuds. Si ils ne font pas ce que la constante de temps /temps linéaire est moins pertinent que les performances de la mémoire seront pauvres et les performances du cache encore pire.

    Utiliser les listes chaînées quand

    1) Vous voulez la sécurité des threads. Vous pouvez construire mieux "thread-safe" algos. Verrouillage des coûts de dominer en même temps une liste de style.

    2) Si vous avez une grande file d'attente comme des structures et souhaitez supprimer ou ajouter n'importe où, mais à la fin tout le temps . >100K listes existent mais ne sont pas courantes.

    • Cette question a été sur les deux C# implémentations, pas de listes liées en général.
    • Même dans toutes les langues
    InformationsquelleAutor user1496062
  15. -1

    J'ai demandé à un même question liée à la performance de la LinkedList collection, et découvert Steven Cleary C# en œuvre de Deque était une solution. Contrairement à la File d'attente de la collection, Deque permet de déplacer les éléments sur/hors tension avant et à l'arrière. Il est similaire à la liste chaînée, mais avec l'amélioration des performances.

    • Re de votre déclaration que Deque est "semblable à une liste chaînée, mais avec l'amélioration des performances". Merci de nuancer cette affirmation: Deque est de meilleures performances que LinkedList, pour votre code. En suivant votre lien, je ne vois que deux jours plus tard que vous avez appris de Ivan Stoev que ce n'était pas une inefficacité de la LinkedList, mais d'une inefficacité dans votre code. (Et même si elle avait été d'une inefficacité de la LinkedList, qui ne serait pas justifier un énoncé général qui Deque est plus efficace; dans certains cas seulement.)
    InformationsquelleAutor Adam Cox