Wann sollte ich eine Liste vs. eine LinkedList verwenden?

Question

Wann ist es besser, eine Liste gegen ein LinkedList ?

Answer 1

Dies ist eine Anpassung von Tono Nam die akzeptierte Antwort und korrigiert darin einige falsche Messungen.

Der 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);
}

Und der 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();
        }
    }
}

---

Sie sehen, dass die Ergebnisse mit der theoretischen Leistung übereinstimmen, die andere hier dokumentiert haben. Ziemlich klar - LinkedList<T> gewinnt im Falle von Einfügungen erheblich. Ich habe die Entfernung aus der Mitte der Liste nicht getestet, aber das Ergebnis dürfte das gleiche sein. Natürlich List<T> hat andere Bereiche, in denen es weitaus besser abschneidet, wie z.B. O(1) random access.

Answer 2

Verwenden Sie LinkedList<> wenn

1. Sie wissen nicht, wie viele Objekte durch die Schleuse kommen. Zum Beispiel, Token Stream .
2. Wenn Sie NUR löschen wollten \insert an den Enden.

Für alles andere ist es besser, die List<> .

Answer 3

Ich stimme den meisten der oben angeführten Punkte zu. Und ich stimme auch zu, dass List in den meisten Fällen die naheliegendere Wahl zu sein scheint.

Aber, ich möchte nur hinzufügen, dass es viele Instanz, wo LinkedList sind weit bessere Wahl als Liste für bessere Effizienz.

1. Angenommen, Sie durchlaufen die Elemente und möchten viele Einfügungen/Löschungen vornehmen; LinkedList erledigt dies in linearer O(n)-Zeit, während List dies in quadratischer O(n^2)-Zeit erledigt.
2. Angenommen, Sie wollen immer wieder auf größere Objekte zugreifen, dann wird LinkedList sehr nützlich.
3. Deque() und queue() sind besser mit LinkedList implementiert.
4. Die Vergrößerung der LinkedList ist viel einfacher und besser, wenn man mit vielen und größeren Objekten zu tun hat.

Ich hoffe, dass jemand diese Kommentare nützlich findet.

Answer 4

In .NET werden Listen als Arrays dargestellt. Daher wäre die Verwendung einer normalen Liste im Vergleich zu LinkedList deutlich schneller, weshalb die oben genannten Personen die Ergebnisse sehen, die sie sehen.

Warum sollten Sie die Liste verwenden? Ich würde sagen, es kommt darauf an. List erstellt 4 Elemente, wenn Sie keine angegeben haben. Sobald Sie diese Grenze überschreiten, werden die Daten in ein neues Array kopiert, wobei das alte Array dem Garbage Collector überlassen wird. Es verdoppelt dann die Größe. In diesem Fall wird ein neues Array mit 8 Elementen erstellt. Stellen Sie sich vor, Sie haben eine Liste mit 1 Million Elementen und fügen 1 weiteres hinzu. Es wird ein ganz neues Array mit der doppelten Größe erstellt, die Sie benötigen. Das neue Array hätte dann eine Kapazität von 2 Millionen Elementen, obwohl man nur 1 Million und 1 Element benötigt. Im Grunde genommen bleibt in GEN2 etwas für den Garbage Collector usw. zurück. Es kann also tatsächlich zu einem großen Engpass werden. Damit sollte man vorsichtig sein.

Answer 5

Ich fragte einen ähnliche Frage bezüglich der Leistung der LinkedList-Sammlung und entdeckte Steven Clearys C#-Implementierung von Deque war eine Lösung. Anders als die Queue-Sammlung erlaubt Deque das Verschieben von Elementen nach vorne und hinten. Sie ist ähnlich wie eine verknüpfte Liste, aber mit verbesserter Leistung.