Quand dois-je utiliser une liste par rapport à une LinkedList

Quand est-il préférable d'utiliser une liste par rapport à une LinkedList ?

Éditer

Veuillez lire les commentaires de cette réponse. Les gens prétendent que je n'ai pas fait de tests appropriés. Je suis d'accord que cela ne devrait pas être une réponse acceptée. Pendant que j'apprenais, j'ai fait des tests et j'avais envie de les partager.

Réponse originale ...

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 lié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 accédez uniquement aux données, c'est beaucoup plus lent !! Je dis de ne jamais utiliser une LinkedList.

Voici une autre comparaison effectuant beaucoup d'insertions (nous prévoyons d'insérer un élément au milieu de la liste)

Liste lié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 liée avec référence de l'emplacement où insérer (0,04 seconde)

        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;

Donc, seulement si vous prévoyez d'insérer plusieurs éléments et que vous avez également quelque part la référence de l'endroit où vous prévoyez d'insérer l'élément, utilisez une liste liée. Tout simplement parce que vous devez insérer beaucoup d'éléments, cela ne le rend pas plus rapide, car la recherche de l'emplacement où vous souhaitez l'insérer prend du temps.

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 au milieu de la liste, alors que vous List<T>pouvez seulement ajouter / supprimer à moindre coût à la fin de la liste.

LinkedList<T>n'est efficace que si vous accédez à des données séquentielles (en avant ou en arrière) - l'accès aléatoire est relativement cher car il doit parcourir la chaîne à chaque fois (d'où la raison pour laquelle il n'a pas d'indexeur). Cependant, comme a List<T>n'est essentiellement qu'un tableau (avec un wrapper), l'accès aléatoire est correct.

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

Penser une liste chaînée comme une liste peut être un peu trompeur. C'est plus comme une chaîne. En fait, dans .NET, LinkedList<T>ne met même pas en œuvre IList<T>. Il n'y a pas de véritable concept d'index dans une liste chaînée, même si cela peut sembler être le cas. Certes, aucune des méthodes fournies dans la classe n'accepte les index.

Les listes liées peuvent être liées individuellement ou doublement liées. Il s'agit de savoir si chaque élément de la chaîne a un lien uniquement avec le suivant (lié individuellement) ou avec les deux éléments antérieurs / suivants (liés deux fois). LinkedList<T>est doublement lié.

En interne, List<T>est soutenu par un tableau. Cela fournit une représentation très compacte en mémoire. Inversement, LinkedList<T>implique une mémoire supplémentaire pour stocker les liens bidirectionnels entre les éléments successifs. Ainsi, l'empreinte mémoire d'un LinkedList<T>sera généralement plus grande que pour List<T>(avec la mise en garde qui List<T>peut avoir des éléments de tableau interne inutilisés pour améliorer les performances lors des opérations d'ajout.)

Ils ont également des caractéristiques de performance différentes:

Ajouter

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

Prepend

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

Insertion

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

Suppression

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

Compter

• LinkedList<T>.Count temps constant
• List<T>.Count temps constant

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 pour la plupart équivalents. En pratique, l'API de LinkedList<T>est plus lourde à utiliser et les détails de ses besoins internes se répandent dans votre code.

Cependant, si vous devez effectuer de nombreuses insertions / suppressions à partir d'une liste, elle offre un temps constant. List<T>offre un temps linéaire, car les éléments supplémentaires de la liste doivent être mélangés après l'insertion / la suppression.

Les listes liées permettent l'insertion ou la suppression très rapide d'un membre de liste. Chaque membre d'une liste chaînée contient un pointeur sur le membre suivant de la liste afin d'insérer un membre à la position i:

• mettre à jour le pointeur du membre i-1 pour pointer vers le nouveau membre
• définir le pointeur dans le nouveau membre pour pointer vers le membre i

L'inconvénient d'une liste chaînée est qu'un accès aléatoire n'est pas possible. L'accès à un membre nécessite de parcourir la liste jusqu'à ce que le membre souhaité soit trouvé.

Ma réponse précédente n'était pas assez précise. C'était vraiment horrible: D Mais maintenant je peux poster une réponse beaucoup plus utile et correcte.

J'ai fait quelques tests supplémentaires. Vous pouvez trouver sa source par le lien suivant et la vérifier à nouveau dans votre environnement: https://github.com/ukushu/DataStructuresTestsAndOther.git

Résultats courts:

• Le tableau doit utiliser:

  • Aussi souvent que possible. Il est rapide et prend la plus petite plage de RAM pour les mêmes informations.
  • Si vous connaissez le nombre exact de cellules nécessaires
  • Si les données enregistrées dans le tableau <85000 b (85000/32 = 2656 éléments pour les données entières)
  • Si nécessaire, vitesse d'accès aléatoire élevée

• La liste doit utiliser:

  • Si nécessaire pour ajouter des cellules à la fin de la liste (souvent)
  • Si nécessaire pour ajouter des cellules au début / au milieu de la liste (PAS SOUVENT)
  • Si les données enregistrées dans le tableau <85000 b (85000/32 = 2656 éléments pour les données entières)
  • Si nécessaire, vitesse d'accès aléatoire élevée

• LinkedList doit utiliser:

  • Si nécessaire pour ajouter des cellules au début / au milieu / à la fin de la liste (souvent)
  • Si nécessaire uniquement un accès séquentiel (avant / arrière)
  • Si vous devez enregistrer de GRANDS articles, mais le nombre d'articles est faible.
  • Mieux vaut ne pas utiliser pour une grande quantité d'éléments, car il utilise de la mémoire supplémentaire pour les liens.

Plus de détails:

Intéressant à savoir:

1. LinkedList<T>en interne n'est pas une liste dans .NET. Il n'est même pas implémenté IList<T>. Et c'est pourquoi il existe des index et des méthodes absents liés aux index.

2. LinkedList<T>est une collection basée sur un pointeur de nœud. Dans .NET, il s'agit d'une implémentation doublement liée. Cela signifie que les éléments antérieurs / suivants ont un lien avec l'élément actuel. Et les données sont fragmentées - différents objets de liste peuvent être situés à différents endroits de la RAM. Il y aura également plus de mémoire utilisée pour LinkedList<T>que pour List<T>ou Array.

3. List<T>in .Net est l'alternative de Java à ArrayList<T>. Cela signifie qu'il s'agit d'un wrapper de tableau. Il est donc alloué en mémoire comme un bloc de données contigu. Si la taille des données allouées dépasse 85 000 octets, elles seront déplacées vers le grand segment d'objets. Selon la taille, cela peut entraîner une fragmentation du tas (une forme légère de fuite de mémoire). Mais en même temps, si la taille est <85000 octets - cela fournit une représentation très compacte et à accès rapide en mémoire.

4. Un bloc contigu unique est préféré pour les performances d'accès aléatoire et la consommation de mémoire, mais pour les collections qui doivent changer régulièrement de taille, une structure telle qu'un tableau doit généralement être copiée vers un nouvel emplacement, tandis qu'une liste liée ne doit gérer la mémoire que pour la nouvelle insertion. / noeuds supprimés.

La différence entre List et LinkedList réside dans leur implémentation sous-jacente. La liste est une collection basée sur un tableau (ArrayList). LinkedList est une collection basée sur un pointeur de nœud (LinkedListNode). Sur l'utilisation au niveau de l'API, les deux sont à peu près les mêmes, car les deux implémentent le même ensemble d'interfaces telles que ICollection, IEnumerable, etc.

La principale différence survient lorsque les performances sont importantes. Par exemple, si vous implémentez la liste qui comporte une opération lourde "INSERT", LinkedList surpasse la liste. Étant donné que LinkedList peut le faire en temps O (1), mais List peut avoir besoin d'étendre la taille du tableau sous-jacent. Pour plus d'informations / détails, vous voudrez peut-être lire la différence algorithmique entre LinkedList et les structures de données de tableau. http://en.wikipedia.org/wiki/Linked_list et Array

J'espère que cette aide,

Le principal avantage des listes liées par rapport aux tableaux est que les liens nous permettent de réorganiser efficacement les éléments. Sedgewick, p. 91

Une circonstance courante pour utiliser LinkedList est comme ceci:

Supposons que vous souhaitiez supprimer plusieurs chaînes de caractères d'une liste de chaînes de grande taille, disons 100 000. Les chaînes à supprimer peuvent être consultées dans le dic HashSet, et la liste des chaînes contient entre 30 000 et 60 000 chaînes à supprimer.

Alors, quel est le meilleur type de liste pour stocker les 100 000 cordes? La réponse est LinkedList. Si elles sont stockées dans une liste de tableaux, itérer dessus et supprimer les chaînes correspondantes devrait prendre jusqu'à des milliards d'opérations, alors qu'il ne faut que 100000 opérations en utilisant 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();
}

Lorsque vous avez besoin d'un accès indexé intégré, d'un tri (et après cette recherche binaire) et d'une méthode "ToArray ()", vous devez utiliser List.

Essentiellement, un List<>dans .NET est un wrapper sur un tableau . A LinkedList<> est une liste chaînée . Donc, la question se résume à, quelle est la différence entre un tableau et une liste liée, et quand un tableau doit-il être utilisé à la place d'une liste liée. Probablement les deux facteurs les plus importants dans votre décision à utiliser se résumeraient à:

• Les listes liées ont des performances d'insertion / suppression bien meilleures, tant que les insertions / suppressions ne sont pas sur le dernier élément de la collection. En effet, un tableau doit décaler tous les éléments restants qui viennent après le point d'insertion / suppression. Cependant, si l'insertion / suppression se trouve à la fin de la liste, ce décalage n'est pas nécessaire (bien que la matrice doive être redimensionnée si sa capacité est dépassée).
• Les baies ont de bien meilleures capacités d'accès. Les tableaux peuvent être indexés directement (en temps constant). Les listes liées doivent être parcourues (temps linéaire).

Ceci est adapté de la réponse acceptée de Tono Nam en y corrigeant quelques mesures erronées.

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 voir que les résultats sont conformes aux performances théoriques que d'autres ont documentées ici. Assez clair - LinkedList<T>gagne beaucoup de temps en cas d'insertions. Je n'ai pas testé la suppression du milieu de la liste, mais le résultat devrait être le même. Bien sûr, il List<T>existe d'autres domaines où il fonctionne bien mieux comme l'accès aléatoire O (1).

Utiliser LinkedList<>quand

1. Vous ne savez pas combien d'objets traversent la barrière anti-inondation. Par exemple Token Stream,.
2. Lorsque vous souhaitez UNIQUEMENT supprimer \ insert aux extrémités.

Pour tout le reste, il vaut mieux l'utiliser List<>.

Je suis d'accord avec la plupart des arguments avancés ci-dessus. Et je suis également d'accord que List semble être un choix plus évident dans la plupart des cas.

Mais, je veux juste ajouter qu'il existe de nombreux cas où LinkedList est un bien meilleur choix que List pour une meilleure efficacité.

1. Supposons que vous parcouriez les éléments et que vous souhaitiez effectuer beaucoup d'insertions / suppressions; LinkedList le fait en temps O (n) linéaire, alors que List le fait en temps O quadratique (n ^ 2).
2. Supposons que vous souhaitiez accéder à de plus gros objets encore et encore, LinkedList devient très utile.
3. Deque () et queue () sont mieux implémentées à l'aide de LinkedList.
4. L'augmentation de la taille de LinkedList est beaucoup plus facile et meilleure une fois que vous avez affaire à de nombreux objets plus gros.

J'espère que quelqu'un trouverait ces commentaires utiles.

Tant de réponses moyennes ici ...

Certaines implémentations de liste chaînée utilisent des blocs sous-jacents de nœuds préalloués. S'ils ne le font pas, le temps constant / temps linéaire est moins pertinent car les performances de la mémoire seront médiocres et les performances du cache seront encore pires.

Utilisez des listes chaînées lorsque

1) Vous voulez la sécurité des fils. Vous pouvez créer de meilleurs algos sûrs pour les threads. Les coûts de verrouillage domineront une liste de styles simultanés.

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

J'ai posé une question similaire concernant les performances de la collection LinkedList et j'ai découvert que l'implémentation C # de Steven Cleary de Deque était une solution. Contrairement à la collection Queue, Deque permet de déplacer des éléments vers l'avant et l'arrière. Il est similaire à la liste chaînée, mais avec des performances améliorées.