Wann sollte ich eine Liste gegen eine LinkedList verwenden?

Wann ist es besser, eine Liste gegen eine LinkedList zu verwenden ?

Bearbeiten

Bitte lesen Sie die Kommentare zu dieser Antwort. Die Leute behaupten, ich hätte keine richtigen Tests gemacht. Ich bin damit einverstanden, dass dies keine akzeptierte Antwort sein sollte. Während ich lernte, machte ich einige Tests 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;

Selbst wenn Sie nur auf Daten zugreifen, ist dies wesentlich langsamer !! Ich sage, benutze niemals eine linkedList.

Hier ist ein weiterer Vergleich, bei dem viele Einfügungen durchgeführt werden (wir planen, ein Element in die 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 Verweis auf den Ort, an dem 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;

Also nur , wenn Sie auf das Einfügen mehrerer Elemente planen und Sie auch irgendwo die Referenz von dem Sie das Element dann eine verkettete Liste verwenden , um einzufügen. Nur weil Sie viele Elemente einfügen müssen, wird dies nicht schneller, da die Suche nach dem Ort, an dem Sie sie einfügen möchten, einige Zeit in Anspruch nimmt.

In den meisten Fällen List<T>ist dies nützlicher. LinkedList<T>Das Hinzufügen / Entfernen von Elementen in der Mitte der Liste List<T>ist kostengünstiger , während das Hinzufügen / Entfernen von Elementen am Ende der Liste nur kostengünstig möglich ist .

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 (daher gibt es keinen Indexer). Da a List<T>jedoch im Wesentlichen nur ein Array (mit einem Wrapper) ist, ist der Direktzugriff in Ordnung.

List<T>bietet auch eine Menge Unterstützung Methoden - Find, ToArrayusw; Diese sind jedoch auch für LinkedList<T>.NET 3.5 / C # 3.0 über Erweiterungsmethoden verfügbar - das ist also weniger ein Faktor.

Eine verknüpfte Liste als Liste zu betrachten, kann etwas irreführend sein. Es ist eher wie eine Kette. Tatsächlich wird in .NET LinkedList<T>nicht einmal implementiert IList<T>. Es gibt kein wirkliches Konzept des Index in einer verknüpften Liste, auch wenn es so scheint. Sicherlich akzeptiert keine der in der Klasse bereitgestellten Methoden Indizes.

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

Intern List<T>wird durch ein Array gesichert. Dies bietet eine sehr kompakte Darstellung im Speicher. Umgekehrt wird LinkedList<T>zusätzlicher Speicher zum Speichern der bidirektionalen Verknüpfungen zwischen aufeinanderfolgenden Elementen verwendet. Daher ist der Speicherbedarf von a LinkedList<T>im Allgemeinen größer als für List<T>(mit der Einschränkung, List<T>dass nicht verwendete interne Array-Elemente zur Verbesserung der Leistung während des Anhängens verwendet werden können).

Sie haben auch unterschiedliche Leistungsmerkmale:

Anhängen

• LinkedList<T>.AddLast(item) konstante Zeit
• List<T>.Add(item) amortisierte konstante Zeit, linearer Worst-Case

Vorbereiten

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

Einfügen

• 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>.Count konstante Zeit
• List<T>.Count konstante 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 können, sind sie meistens gleichwertig. In der Praxis ist die LinkedList<T>Verwendung der API von umständlicher, und Details zu den internen Anforderungen werden in Ihren Code übernommen.

Wenn Sie jedoch viele Einfügungen / Entfernungen innerhalb einer Liste vornehmen müssen, bietet dies eine konstante Zeit. List<T>bietet lineare Zeit, da zusätzliche Elemente in der Liste nach dem Einfügen / Entfernen 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 Mitglied i-1, um auf das neue Mitglied zu zeigen
• Setzen Sie den Zeiger im neuen Element so, dass er auf Mitglied i zeigt

Der Nachteil einer verknüpften Liste besteht darin, dass kein wahlfreier Zugriff möglich ist. Um auf ein Mitglied zugreifen zu können, muss die Liste durchlaufen werden, bis das gewünschte Mitglied gefunden wurde.

Meine vorherige Antwort war nicht genau genug. Es war wirklich schrecklich: D Aber jetzt kann ich eine viel nützlichere und korrektere Antwort posten.

Ich habe einige zusätzliche Tests durchgeführt. Sie können die Quelle über den folgenden Link finden und sie in Ihrer Umgebung erneut überprü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 die genaue Anzahl der benötigten Zellen kennen
  • Wenn Daten in Array <85000 b gespeichert sind (85000/32 = 2656 Elemente für ganzzahlige Daten)
  • Bei Bedarf hohe Direktzugriffsgeschwindigkeit

• Liste muss verwendet werden:

  • Falls erforderlich, um Zellen am Ende der Liste hinzuzufügen (häufig)
  • Falls erforderlich, um Zellen am Anfang / in der Mitte der Liste hinzuzufügen (NICHT HÄUFIG)
  • Wenn Daten in Array <85000 b gespeichert sind (85000/32 = 2656 Elemente für ganzzahlige Daten)
  • Bei Bedarf hohe Direktzugriffsgeschwindigkeit

• LinkedList muss Folgendes verwenden:

  • Bei Bedarf Zellen am Anfang / Mitte / Ende der Liste hinzufügen (häufig)
  • Bei Bedarf nur sequentieller Zugriff (vorwärts / rückwärts)
  • Wenn Sie GROSSE Elemente speichern müssen, die Anzahl der Elemente jedoch niedrig ist.
  • Verwenden Sie es besser nicht für eine große Anzahl von Elementen, da es zusätzlichen Speicher für Links verwendet.

Mehr Details:

Interessant zu wissen:

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

2. LinkedList<T>ist eine auf Knotenzeigern basierende Sammlung. In .NET ist die Implementierung doppelt verknüpft. Dies bedeutet, dass vorherige / nächste Elemente eine Verknüpfung zum aktuellen Element haben. Und Daten sind fragmentiert - verschiedene Listenobjekte können sich an verschiedenen Stellen des RAM befinden. Außerdem wird mehr Speicher 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 im Speicher als ein zusammenhängender Datenblock zugewiesen. Wenn die zugewiesene Datengröße 85000 Byte überschreitet, wird sie in den Heap für große Objekte verschoben. Abhängig von der Größe kann dies zu einer Fragmentierung des Heapspeichers führen (eine leichte Form des Speicherverlusts). Bei einer Größe <85000 Byte bietet dies gleichzeitig eine sehr kompakte und schnell zugängliche Darstellung im Speicher.

4. Ein einzelner zusammenhängender Block wird für die Direktzugriffsleistung und den Speicherverbrauch bevorzugt, aber für Sammlungen, deren Größe regelmäßig geändert werden muss, muss eine Struktur wie ein Array im Allgemeinen an einen neuen Speicherort kopiert werden, während eine verknüpfte Liste nur den Speicher für den neu eingefügten Speicher verwalten muss / gelöschte Knoten.

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

Der Hauptunterschied kommt, wenn Leistung wichtig ist. Wenn Sie beispielsweise die Liste implementieren, die eine schwere "INSERT" -Operation aufweist, übertrifft LinkedList List. Da LinkedList dies in O (1) -Zeit tun kann, muss List möglicherweise die Größe des zugrunde liegenden Arrays erweitern. Für weitere Informationen / Details möchten Sie möglicherweise den algorithmischen Unterschied zwischen LinkedList- und Array-Datenstrukturen nachlesen. http://en.wikipedia.org/wiki/Linked_list and Array

Ich hoffe das hilft,

Der Hauptvorteil von verknüpften Listen gegenüber Arrays besteht darin, dass die Verknüpfungen uns die Möglichkeit bieten, die Elemente effizient neu anzuordnen. Sedgewick, p. 91

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

Angenommen, Sie möchten viele bestimmte Zeichenfolgen aus einer Liste von Zeichenfolgen mit einer großen Größe entfernen, z. B. 100.000. Die zu entfernenden Zeichenfolgen können in HashSet dic nachgeschlagen werden, und es wird angenommen, dass die Liste der zu entfernenden Zeichenfolgen zwischen 30.000 und 60.000 solcher zu entfernenden Zeichenfolgen enthält.

Was ist dann die beste Art von Liste zum Speichern der 100.000 Zeichenfolgen? Die Antwort lautet LinkedList. Wenn sie in einer ArrayList gespeichert sind, würde das Durchlaufen und Entfernen von übereinstimmenden Strings bis zu Milliarden von Operationen erfordern, während mit einem Iterator und der remove () -Methode nur etwa 100.000 Operationen erforderlich sind.

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, eine Sortierung (und nach dieser binären Suche) und die Methode "ToArray ()" benötigen, sollten Sie List verwenden.

Im Wesentlichen ist ein List<>in .NET ein Wrapper über ein Array . A LinkedList<> ist eine verknüpfte Liste . Es stellt sich also die Frage, was der Unterschied zwischen einem Array und einer verknüpften Liste ist und wann ein Array anstelle einer verknüpften Liste verwendet werden sollte. Wahrscheinlich sind die beiden wichtigsten Faktoren bei Ihrer Entscheidung, welche Sie verwenden möchten, folgende:

• Verknüpfte Listen bieten eine viel bessere Leistung beim Einfügen / Entfernen, solange sich die Einfügungen / Entfernungen nicht auf dem letzten Element in der Sammlung befinden. Dies liegt daran, dass ein Array alle verbleibenden Elemente verschieben muss, die nach dem Einfüge- / Entfernungspunkt kommen. 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).

Dies ist von Tono Nam angepasst akzeptierter Antwort übernommen, die einige falsche Messungen korrigiert.

Die Prüfung:

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 nicht getestet, ob sie aus der Mitte der Liste entfernt wurden, aber das Ergebnis sollte das gleiche sein. Natürlich List<T>hat andere Bereiche, in denen es viel besser funktioniert, wie O (1) Direktzugriff.

Verwenden Sie, LinkedList<>wenn

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

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

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

Aber ich möchte nur hinzufügen, dass es viele Fälle gibt, in denen LinkedList für eine bessere Effizienz eine weitaus bessere Wahl ist als List.

1. Angenommen, Sie durchlaufen die Elemente und möchten viele Einfügungen / Löschungen durchführen. LinkedList macht es in linearer O (n) Zeit, während List es in quadratischer O (n ^ 2) Zeit macht.
2. Angenommen, Sie möchten immer wieder auf größere Objekte zugreifen, wird LinkedList sehr nützlich.
3. Deque () und queue () werden besser mit LinkedList implementiert.
4. Das Vergrößern von LinkedList ist viel einfacher und besser, wenn Sie mit vielen und größeren Objekten arbeiten.

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

So viele durchschnittliche Antworten hier ...

Einige Implementierungen von verknüpften Listen verwenden zugrunde liegende Blöcke von vorab zugewiesenen Knoten. Wenn sie dies nicht tun, ist die konstante Zeit / lineare Zeit weniger relevant, da die Speicherleistung schlecht und die Cache-Leistung noch schlechter ist.

Verwenden Sie verknüpfte Listen, wenn

1) Sie möchten Gewindesicherheit. Sie können bessere thread-sichere Algen erstellen. Sperrkosten dominieren eine Liste gleichzeitiger Stile.

2) Wenn Sie eine große Warteschlange wie Strukturen haben und die ganze Zeit irgendwo anders als am Ende entfernen oder hinzufügen möchten. > 100K-Listen existieren, sind aber nicht so häufig.

Ich stellte eine ähnliche Frage zur Leistung der LinkedList-Sammlung und stellte fest, dass Steven Clearys C # -Implement von Deque eine Lösung war. Im Gegensatz zur Warteschlangensammlung ermöglicht Deque das Ein- und Ausschalten von Elementen vorne und hinten. Es ähnelt der verknüpften Liste, bietet jedoch eine verbesserte Leistung.