Quand dois-je utiliser une liste par rapport à une liste chaînée

Question

Quand est-il préférable d'utiliser List(Of T) vs LinkedList(Of T) ?

Answer 1

Dans la plupart des cas, List<T> est plus utile. LinkedList<T> auront moins de coût lors de l'ajout/suppression d'éléments dans le milieu de la liste, alors qu' 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 d'un 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.

Answer 2

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 oeuvre 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.

Les 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 de 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 les List<T> (avec la mise en garde que List<T> peut avoir inutilisés interne des éléments d'un tableau afin d'améliorer les performances lors de append.)

Ils ont différentes caractéristiques de performance:

Ajouter

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

Ajouter

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

Insertion

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

La suppression

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

Le comte

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

Contient

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

Claire

• LinkedList<T>.Clear() du temps linéaire
• List<T>.Clear() du 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.

Answer 3

Les 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.

Answer 4

Je sais que cette réponse est tardive, mais j'ai trouvé des résultats intéressants

// temp class to show 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 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 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 en tenant 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;

Donc, si vous envisagez 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.

Answer 5

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,