Wann sollte ich eine Liste gegen eine LinkedList verwenden?

In den meisten Fällen ist List<T> nützlicher. LinkedList<T> wird weniger kosten, wenn Elemente in der Mitte der Liste hinzugefügt/entfernt werden, während List<T> nur am Ende der Liste kostengünstig hinzugefügt/entfernt werden kann.

LinkedList<T> ist nur dann am effizientesten, wenn Sie auf sequentielle Daten zugreifen (entweder vorwärts oder rückwärts) - der Direktzugriff ist relativ teuer, da er jedes Mal die Kette durchlaufen muss (weshalb er keinen Indexer hat). Da jedoch ein List<T> im Wesentlichen nur ein Array (mit einem Wrapper) ist, ist der Direktzugriff in Ordnung.

List<T> bietet auch viele Unterstützungsmethoden an - Find, ToArray usw .; diese stehen jedoch auch für LinkedList<T> mit .NET 3.5/C # 3.0 über Erweiterungsmethoden zur Verfügung - das ist weniger ein Faktor.

Das Gedanken an eine verknüpfte Liste als Liste kann etwas irreführend sein. Es ist eher eine Kette. In .NET implementiert LinkedList<T>IList<T> nicht einmal. Es gibt kein reales Konzept des Index in einer verknüpften Liste, auch wenn es so aussieht, als ob es existiert. Sicherlich akzeptiert keine der in der Klasse bereitgestellten Methoden Indizes.

Verknüpfte Listen können einzeln oder doppelt verknüpft sein. Dies bezieht sich darauf, ob jedes Element in der Kette nur eine Verknüpfung zu dem nächsten (einfach verknüpft) oder zu den vorherigen/nächsten Elementen (doppelt verbunden) hat. LinkedList<T> ist doppelt verlinkt.

Intern wird List<T> von einem Array unterstützt. Dies bietet eine sehr kompakte Darstellung im Speicher. Umgekehrt beinhaltet LinkedList<T> zusätzlichen Speicher zum Speichern der bidirektionalen Verbindungen zwischen aufeinanderfolgenden Elementen. Daher ist der Speicherbedarf eines LinkedList<T> im Allgemeinen größer als für List<T> (mit der Einschränkung, dass List<T> ungenutzte interne Array-Elemente haben kann, um die Leistung beim Anhängen zu verbessern.)

Sie haben auch unterschiedliche Leistungsmerkmale:

Anhängen

• LinkedList<T>.AddLast(item)konstante Zeit
• List<T>.Add(item)amortisierte konstante Zeit, linearer ungünstiger Fall

Voranstellen

• LinkedList<T>.AddFirst(item)konstante Zeit
• List<T>.Insert(0, item)lineare Zeit

Einfügung

• LinkedList<T>.AddBefore(node, item)konstante Zeit
• LinkedList<T>.AddAfter(node, item)konstante Zeit
• List<T>.Insert(index, item)lineare Zeit

Entfernung

• LinkedList<T>.Remove(item)lineare Zeit
• LinkedList<T>.Remove(node)konstante Zeit
• List<T>.Remove(item)lineare Zeit
• List<T>.RemoveAt(index)lineare Zeit

Anzahl

• LinkedList<T>.Countkonstante Zeit
• List<T>.Countkonstante Zeit

Enthält

• LinkedList<T>.Contains(item)lineare Zeit
• List<T>.Contains(item)lineare Zeit

Klar

• LinkedList<T>.Clear()lineare Zeit
• List<T>.Clear()lineare Zeit

Wie Sie sehen, sind sie meist gleichwertig. In der Praxis ist die Verwendung der API von LinkedList<T> etwas umständlicher, und Details der internen Anforderungen werden in Ihren Code übernommen.

Wenn Sie jedoch viele Einfügungen/Entfernungen aus einer Liste vornehmen müssen, bietet dies konstante Zeit. List<T> bietet lineare Zeit, da zusätzliche Elemente in der Liste nach dem Einfügen/Entfernen neu gemischt werden müssen.

Verknüpfte Listen ermöglichen das sehr schnelle Einfügen oder Löschen eines Listenmitglieds. Jedes Mitglied in einer verknüpften Liste enthält einen Zeiger auf das nächste Mitglied in der Liste, um ein Mitglied an Position i einzufügen:

• aktualisieren Sie den Zeiger in Member i-1, um auf das neue Member zu zeigen
• setzen Sie den Zeiger im neuen Element auf das Element i

Der Nachteil einer verknüpften Liste ist, dass kein Direktzugriff möglich ist. Um auf ein Mitglied zuzugreifen, muss die Liste so lange durchlaufen werden, bis das gewünschte Mitglied gefunden wurde.

Der Unterschied zwischen List und LinkedList liegt in der zugrunde liegenden Implementierung. Liste ist eine Array-basierte Sammlung (ArrayList). LinkedList ist eine auf Knotenzeiger basierende Auflistung (LinkedListNode). Auf der API-Ebene sind beide ziemlich gleich, da beide dieselbe Gruppe von Schnittstellen wie ICollection, IEnumerable usw. implementieren.

Der entscheidende Unterschied ist, wenn es auf die Leistung ankommt. Wenn Sie beispielsweise eine Liste implementieren, die eine umfangreiche Operation "INSERT" hat, übertrifft LinkedList List. Da LinkedList dies in O(1) - Zeit ausführen kann, muss List jedoch möglicherweise die Größe des zugrunde liegenden Arrays erweitern. Für weitere Informationen/Einzelheiten möchten Sie vielleicht den algorithmischen Unterschied zwischen LinkedList- und Array-Datenstrukturen nachlesen. http://en.wikipedia.org/wiki/Linked_list und Array

Ich hoffe das hilft,

Meine vorige Antwort war nicht genau genug .. __ Wie wirklich war es schrecklich: D __ __ Aber jetzt kann ich viel nützlichere und korrekte Antwort posten.

Ich habe einige zusätzliche Tests gemacht. Sie können den Quellcode unter folgendem Link finden und in Ihrer Umgebung selbst erneut prüfen: https://github.com/ukushu/DataStructuresTestsAndOther.git

Kurze Ergebnisse:

• Array muss verwenden:

  • So oft wie möglich. Es ist schnell und benötigt den kleinsten RAM - Bereich für die gleiche Menge an Informationen.
  • Wenn Sie genau wissen, wie viele Zellen benötigt werden
  • Wenn Daten in Array <85000 gespeichert sind b
  • Bei Bedarf hohe Geschwindigkeit des zufälligen Zugriffs

• Liste muss verwendet werden:

  • Wenn nötig, um Zellen am Ende der Liste hinzuzufügen (oft)
  • Wenn nötig, um Zellen am Anfang/in der Mitte der Liste hinzuzufügen (NOT OFTEN)
  • Wenn Daten in Array <85000 gespeichert sind b
  • Bei Bedarf hohe Geschwindigkeit des zufälligen Zugriffs

• LinkedList muss Folgendes verwenden:

  • Wenn nötig, um Zellen am Anfang/in der Mitte/am Ende der Liste hinzuzufügen (oft)
  • Bei Bedarf nur sequentieller Zugriff (vorwärts/rückwärts)
  • Wenn Sie große Artikel speichern müssen, ist die Anzahl der Elemente jedoch gering.
  • Besser nicht für große Mengen von Elementen verwenden, da zusätzlicher Speicher für Links verwendet wird.

Mehr Details:

  Interessant zu wissen:

1. LinkedList<T> ist intern keine Liste in .NET. Es implementiert sogar IList<T> nicht. Aus diesem Grund gibt es keine Indizes und Methoden, die sich auf Indizes beziehen.

2. LinkedList<T> ist eine auf Knotenzeiger basierende Auflistung. Bei .NET handelt es sich um eine doppelt verknüpfte Implementierung. Dies bedeutet, dass vorherige/nächste Elemente mit dem aktuellen Element verknüpft sind. Und Daten sind fragmentiert - verschiedene Listenobjekte können sich an verschiedenen Stellen des RAM befinden. Es wird auch mehr Speicher für LinkedList<T> als für List<T> oder Array verwendet.

3. List<T> in .Net ist Javas Alternative zu ArrayList<T>. Dies bedeutet, dass dies ein Array-Wrapper ist. Es wird also als zusammenhängender Datenblock im Speicher zugewiesen. Wenn die zugewiesene Datengröße 85000 Byte überschreitet, werden sie in den Large Object Heap verschoben. Abhängig von der Größe kann dies zu einer Haufenfragmentierung führen (eine leichte Form eines Speicherverlusts). Wenn jedoch die Größe <85000 Byte ist, bietet dies eine sehr kompakte und schnell zugreifbare Darstellung im Speicher. 

4. Ein einzelner zusammenhängender Block wird für die Direktzugriffsleistung und den Speicherverbrauch bevorzugt. Für Sammlungen, die regelmäßig ihre Größe ändern müssen, muss eine Struktur wie ein Array im Allgemeinen an einen neuen Speicherort kopiert werden, wohingegen eine verknüpfte Liste nur den Speicher für den neu eingefügten Speicher verwaltet/gelöschte Knoten. 

Der Hauptvorteil verknüpfter Listen gegenüber Arrays besteht darin, dass die Verknüpfungen uns die Möglichkeit geben, die Elemente effizient neu anzuordnen. 91

Ein häufiger Umstand bei der Verwendung von LinkedList ist wie folgt:

Angenommen, Sie möchten viele bestimmte Zeichenfolgen aus einer Liste großer Zeichenfolgen entfernen, beispielsweise 100.000. Die zu entfernenden Zeichenfolgen können in HashSet dic nachgeschlagen werden, und es wird angenommen, dass die Liste der Zeichenfolgen zwischen 30.000 und 60.000 zu entfernende Zeichenfolgen enthält. 

Was ist dann der beste Listentyp für das Speichern der 100.000 Strings? Die Antwort lautet LinkedList. Wenn sie in einer ArrayList gespeichert sind, werden Iterationen darüber durchgeführt und übereinstimmende Strings entfernt, um Milliarden von Operationen in Anspruch zu nehmen, während sie mit einem Iterator und der remove () -Methode nur etwa 100.000 Operationen benötigt.

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

Wenn Sie einen integrierten indizierten Zugriff, die Sortierung (und nach dieser binären Suche) und die Methode "ToArray ()" benötigen, sollten Sie List verwenden.

Dies entspricht der akzeptierten Antwort von Tono Nam , die einige falsche Messungen korrigiert.

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 können sehen, dass die Ergebnisse mit der theoretischen Leistung übereinstimmen, die andere hier dokumentiert haben. Ganz klar - LinkedList<T> gewinnt bei Einfügungen viel Zeit. Ich habe das Entfernen aus der Mitte der Liste nicht getestet, aber das Ergebnis sollte dasselbe sein. Natürlich hat List<T> andere Bereiche, in denen es viel besser funktioniert als der Direktzugriff O(1).

Im Wesentlichen ist ein List<> in .NET ein Wrapper über einem Array . Ein LinkedList<> ist eine verknüpfte Liste . Die Frage lautet also: Was ist der Unterschied zwischen einem Array und einer verknüpften Liste und wann sollte ein Array anstelle einer verknüpften Liste verwendet werden? Wahrscheinlich sind die zwei wichtigsten Faktoren für Ihre Entscheidung, zu verwenden:

• Verknüpfte Listen bieten eine viel bessere Leistung beim Einfügen/Entfernen, solange sich die Einfügungen/Entfernungen nicht auf dem letzten Element der Auflistung befinden. Dies liegt daran, dass ein Array alle verbleibenden Elemente verschieben muss, die sich nach dem Einfüge-/Entnahmepunkt befinden. Befindet sich das Einfügen/Entfernen jedoch am Ende der Liste, ist diese Verschiebung nicht erforderlich (obwohl die Größe des Arrays möglicherweise geändert werden muss, wenn seine Kapazität überschritten wird).
• Arrays haben viel bessere Zugriffsmöglichkeiten. Arrays können direkt (in konstanter Zeit) indiziert werden. Verknüpfte Listen müssen durchlaufen werden (lineare Zeit).

Verwenden Sie LinkedList<>, wenn

1. Sie wissen nicht, wie viele Objekte durch das Schleusentor kommen. Zum Beispiel Token Stream.
2. Wenn Sie NUR\löschen wollten, fügen Sie an den Enden ein.

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

Ich stimme den meisten der oben genannten Punkte zu. Ich stimme auch zu, dass List in den meisten Fällen eine naheliegendere Wahl darstellt.

Aber ich möchte nur hinzufügen, dass es viele Beispiele gibt, bei denen LinkedList eine bessere Wahl ist als List, um die Effizienz zu steigern.

1. Angenommen, Sie durchlaufen die Elemente und möchten viele Einfügungen/Löschungen durchführen. LinkedList führt es in linearer O(n) Zeit aus, wohingegen List es in quadratischem O (n ^ 2) tut.
2. Angenommen, Sie möchten immer wieder auf größere Objekte zugreifen, wird LinkedList sehr viel nützlicher.
3. Deque () und queue () werden besser mit LinkedList implementiert.
4. Das Vergrößern der LinkedList ist viel einfacher und besser, wenn Sie sich mit vielen und größeren Objekten befassen.

Hoffe, dass jemand diese Kommentare nützlich finden würde.