wake-up-neo.com

Wann sollte ich eine Liste gegen eine LinkedList verwenden?

Wann ist es besser, eine List vs a LinkedList zu verwenden?

355
Jonathan Allen

Bearbeiten

Bitte lesen Sie die Kommentare zu dieser Antwort. Die Leute behaupten, ich hätte es nicht getan. richtige Tests. Ich stimme zu, dass dies keine akzeptierte Antwort sein sollte. Wie ich war Beim Lernen habe ich einige Tests gemacht und wollte sie teilen.

Ursprüngliche Antwort ...

Ich habe interessante Ergebnisse gefunden:

// 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;
    }
}

Verknüpfte Liste (3,9 Sekunden)

        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 Sekunden)

        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;

Auch wenn Sie im Wesentlichen nur auf Daten zugreifen, sind sie wesentlich langsamer !! Ich sage niemals eine LinkedList.




Hier ist ein weiterer Vergleich, der viele Einfügungen durchführt (wir planen, einen Artikel in der Mitte der Liste einzufügen)

Verknüpfte Liste (51 Sekunden)

        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 Sekunden)

        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;

Verknüpfte Liste mit Referenz der Position, an der eingefügt werden soll (0,04 Sekunden)

        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;

Wenn Sie also vorhaben, mehrere Artikel einzufügen und Sie auch irgendwo die Referenz haben, wo Sie den Artikel einfügen möchten, verwenden Sie eine verknüpfte Liste. Nur weil Sie sehr viele Elemente einfügen müssen, ist dies nicht schneller, da die Suche nach dem Ort, an dem Sie einfügen möchten, Zeit braucht.

98
Tono Nam

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.

254
Marc Gravell

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.

197
Drew Noakes

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.

113
b3.

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,

17
user23117

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. 

14
Andrew

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

11
Dr. Alrawi

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

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

2
Michael Damatov

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

1
nawfal

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).
1
iliketocode

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.

0
Antony Thomas

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.