Wann sollte ich eine Liste gegen eine verknüpfte Liste verwenden?

https://stackoverflow.com/questions/169973

05-07-2019
|

Frage

Wann ist es besser, a zu verwenden Aufführen vs a LinkedList?

Lösung

Bearbeiten

Bitte lesen Sie die Kommentare zu dieser Antwort. Die Leute behaupten, ich habe keine richtigen Tests durchgeführt. Ich bin damit einverstanden, dass dies keine akzeptierte Antwort sein sollte. Als ich lernte, machte ich einige Tests und wollte sie teilen.

Ursprüngliche Antwort ...

Ich fand interessante Ergebnisse:

// 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 nur auf Daten zugreifen, ist es im Wesentlichen viel langsamer !! Ich sage, ich benutze niemals eine LinkedList.

Hier ist ein weiterer Vergleich, der viele Einsätze 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;

Verbindete Liste mit Referenz auf den Ort, an dem einfügen (.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 vorhaben, mehrere Gegenstände und Sie einzuführen Auch Irgendwo haben Sie die Referenz, wo Sie das Element einfügen möchten und dann eine verknüpfte Liste verwenden. Nur weil Sie viele Elemente einfügen müssen, wird es nicht schneller, da die Suche nach dem Ort, an dem Sie einfügen möchten, Zeit dauert.

Andere Tipps

In den meisten Fällen, List<T> ist nützlicher. LinkedList<T> hat beim Hinzufügen/Entfernen von Elementen in der Mitte der Liste weniger Kosten List<T> kann nur billig hinzufügen/entfernen am Ende der Liste.

LinkedList<T> ist nur am effizientesten, wenn Sie auf sequentielle Daten zugreifen (entweder vorwärts oder rückwärts) - der Zufallszugriff ist relativ teuer, da sie jedes Mal die Kette laufen muss (daher hat er keinen Indexer). Allerdings, weil a List<T> ist im Wesentlichen nur ein Array (mit einem Wrapper) Zufallszugriff in Ordnung.

List<T> bietet auch viele Support -Methoden - Find, ToArray, etc; Diese sind jedoch auch für verfügbar LinkedList<T> Mit .NET 3.5/C# 3.0 über Erweiterungsmethoden - das ist weniger ein Faktor.

Das Denken einer verknüpften Liste als Liste kann etwas irreführend sein. Es ist eher eine Kette. In der Tat in .net, LinkedList<T> Implementiert nicht einmal IList<T>. Es gibt kein echtes Indexkonzept in einer verknüpften Liste, obwohl es so aussieht. Sicherlich akzeptiert keine der in der Klasse bereitgestellten Methoden Indizes.

Verlinkte Listen können nur verknüpft oder doppelt verknüpft sein. Dies bezieht sich darauf, ob jedes Element in der Kette nur eine Verbindung zum nächsten (einzeln verknüpft) oder sowohl mit den vorherigen/nächsten Elementen (doppelt verknüpft) hat. LinkedList<T> ist doppelt verknüpft.

Im Inneren, List<T> wird durch ein Array unterstützt. Dies liefert eine sehr kompakte Darstellung im Speicher. Umgekehrt, LinkedList<T> Beinhaltet zusätzlichen Speicher, um die bidirektionalen Verbindungen zwischen aufeinanderfolgenden Elementen zu speichern. Also der Gedächtnis Fußabdruck von a LinkedList<T> wird im Allgemeinen größer sein als für List<T> (mit der Einschränkung das List<T> Kann unbenutzte interne Array -Elemente haben, um die Leistung während des Anhangs zu verbessern.)

Sie haben auch unterschiedliche Leistungsmerkmale:

Anhängen

LinkedList<T>.AddLast(item) ständige Zeit
List<T>.Add(item) Amortisierte konstante Zeit, linear schlechtester Fall

Vorbereiten

LinkedList<T>.AddFirst(item) ständige Zeit
List<T>.Insert(0, item) lineare Zeit

Einfügen

LinkedList<T>.AddBefore(node, item) ständige Zeit
LinkedList<T>.AddAfter(node, item) ständige Zeit
List<T>.Insert(index, item) lineare Zeit

Entfernung

LinkedList<T>.Remove(item) lineare Zeit
LinkedList<T>.Remove(node) ständige Zeit
List<T>.Remove(item) lineare Zeit
List<T>.RemoveAt(index) lineare Zeit

Zählen

LinkedList<T>.Count ständige Zeit
List<T>.Count ständige 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 die API von LinkedList<T> ist mehr umständlich zu bedienen und Details zu den internen Bedürfnissen in Ihren Code.

Wenn Sie jedoch in einer Liste viele Einfügungen/Umbauten ausführen müssen, bietet es eine ständige Zeit. List<T> Bietet lineare Zeit, da zusätzliche Artikel in der Liste nach dem Einsetzen/Entfernen gemischt werden müssen.

Verlinkte Listen bieten ein sehr schnelles 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 in Position I einzufügen:

Aktualisieren Sie den Zeiger in Mitglied I-1, um auf das neue Mitglied zu verweisen
Stellen Sie den Zeiger im neuen Mitglied auf das Mitglied i ein

Der Nachteil einer verknüpften Liste ist, dass der Zufallszugriff nicht möglich ist. Der Zugriff auf ein Mitglied erfordert das Durchqueren der Liste, bis das gewünschte Mitglied gefunden wurde.

Der Unterschied zwischen der Liste und der LinkedList liegt in ihrer zugrunde liegenden Implementierung. Die Liste ist eine Array -basierte Sammlung (ArrayList). LinkedList ist eine noten-peinterbasierte Sammlung (LinkedListNode). Auf der Verwendung von API -Ebene sind beide ziemlich gleich, da beide gleiche Menge von Schnittstellen wie Icollection, IEnumerable usw. implementieren.

Der Hauptunterschied kommt, wenn die Leistung wichtig ist. Wenn Sie beispielsweise die Liste mit einer schweren "Einfügen" -Operation implementieren, übertrifft die LinkedList -Liste. Da LinkedList dies in O (1) Zeit tun kann, muss die Liste jedoch möglicherweise die Größe des zugrunde liegenden Arrays erweitern. Für weitere Informationen/Details möchten Sie möglicherweise über den algorithmischen Unterschied zwischen LinkedList- und Array -Datenstrukturen informiert. http://en.wikipedia.org/wiki/linked_list und Array

Ich hoffe das hilft,

Meine vorherige Antwort war nicht genug genau. Als wirklich schrecklich war es schrecklich: D, aber jetzt kann ich viel nützlicher und korrektere Antwort posten.

Ich habe einige zusätzliche Tests durchgeführt. Sie können die Quelle durch den folgenden Link finden und sie in Ihrer Umgebung nach Ihrer eigenen überprüfen: https://github.com/ukushu/datastructururestsandother.git

Kurze Ergebnisse:

Array muss verwenden:
- So oft wie möglich. Es ist schnell und nimmt den kleinsten RAM -Bereich für die gleichen Menge an.
- Wenn Sie die genaue Anzahl der benötigten Zellen kennen
- Wenn Daten in Array <85000 B gespeichert sind
- Bei Bedarf hoher Zufallszugriffsgeschwindigkeit
Die Liste muss verwendet werden:
- Bei Bedarf, um Zellen zum Ende der Liste hinzuzufügen (oft)
- Bei Bedarf, um Zellen zu Beginn/Mitte der Liste hinzuzufügen (nicht oft)
- Wenn Daten in Array <85000 B gespeichert sind
- Bei Bedarf hoher Zufallszugriffsgeschwindigkeit
LinkedList muss verwenden:
- Bei Bedarf, 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 Gegenstände sparen müssen, die Gegenstände jedoch niedrig sind.
- Verwenden Sie besser nicht für eine große Anzahl von Elementen, da es zusätzlichen Speicher für Links verwendet.

Mehr Details:

Interessant zu wissen:

LinkedList<T> Intern ist keine Liste in .NET. Es implementiert sogar nicht IList<T>. Und deshalb gibt es keine Indizes und Methoden im Zusammenhang mit Indizes.
LinkedList<T> ist eine nodenzeigerbasierte Sammlung. In .NET ist es in doppelt verknüpfter Implementierung. Dies bedeutet, dass Prior/Next -Elemente eine Verbindung zum aktuellen Element haben. Und Daten werden fragmentiert - verschiedene Listenobjekte können an verschiedenen RAM -Stellen lokalisiert werden. Außerdem wird es mehr Speicher geben, für das verwendet wird LinkedList<T> als für List<T> oder Array.
List<T> In .NET ist Javas Alternative von ArrayList<T>. Dies bedeutet, dass dies Array -Wrapper ist. Daher wird es im Speicher als einen zusammenhängenden Datenblock zugewiesen. Wenn die zugewiesene Datengröße 85000 Bytes überschreitet, wird sie in einen großen Objekthaufen verschoben. Abhängig von der Größe kann dies zu einer Haufen -Fragmentierung (einer milden Form des Speicherlecks) führen. Aber gleichzeitig, wenn die Größe <85000 Bytes-dies bietet eine sehr kompakte und schnelle Zugriffsdarstellung im Speicher.
Einzelblock mit einem zusammenhängenden Block wird für den Zufallszugriffsleistung und den Speicherverbrauch bevorzugt, aber für Sammlungen, die die Größe regelmäßig ändern müssen, muss eine Struktur wie ein Array im Allgemeinen an einen neuen Ort kopiert werden /gelöschte Knoten.

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

Wenn Sie einen integrierten indizierten Zugriff, Sortieren (und nach dieser binären Suche) und "toArray ()" benötigen, sollten Sie die Liste verwenden.

Ein häufiger Umstand für die Verwendung von LinkedList ist wie folgt:

Angenommen, Sie möchten viele bestimmte Zeichenfolgen aus einer Liste von Saiten mit einer großen Größe entfernen, z. B. 100.000. Die zu entfernenen Saiten können in Hashset DIC nachgeschlagen werden, und die Liste der Zeichenfolgen wird vermutlich zwischen 30.000 und 60.000 solcher Saiten enthalten, die zu entfernen sind.

Was ist dann die beste Art von Liste für die Speicherung der 100.000 Saiten? Die Antwort lautet LinkedList. Wenn sie in einer Arraylist gespeichert sind, dann über die Iterie und das Entfernen von übereinstimmenden Saiten, die bis zu Milliarden Operationen dauern sollten, während es nur rund 100.000 Vorgänge durch Verwendung eines Iterators und der REME (REME () -Methode 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();
}

Dies ist angepasst Tono NamDie akzeptierte Antwort, die ein paar falsche Messungen darin 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. Ziemlich deutlich - LinkedList<T> Gewinne bei Einfügen eine große Zeit. Ich habe nicht zur Entfernung aus der Mitte der Liste getestet, aber das Ergebnis sollte das gleiche sein. Na sicher List<T> hat andere Bereiche, in denen es viel besser wie o (1) Zufallszugriff abschneidet.

Im Wesentlichen a List<> in .net ist ein Wrapper über einem Array. EIN LinkedList<> ist eine verknüpfte Liste. Es kommt also auf die Frage an, 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 würden die beiden wichtigsten Faktoren bei Ihrer Entscheidung, auf die man verwenden kann, auf:

Linked Listen haben eine viel bessere Einfügungs-/Entfernungsleistung, solange die Einfügungen/Entfernungen nicht das letzte Element in der Sammlung sind. Dies liegt daran, dass ein Array alle verbleibenden Elemente verschieben muss, die nach dem Einfügen/Entfernungspunkt vorhanden sind. Wenn die Einfügung/Entfernung am Ende der Liste liegt, ist diese Verschiebung jedoch nicht erforderlich (obwohl das Array möglicherweise geändert werden muss, wenn seine Kapazität überschritten wird).
Arrays haben viel bessere Zugriffsfunktionen. Arrays können direkt (in konstanter Zeit) indiziert werden. Verbindete Listen müssen durchquert werden (lineare Zeit).

Ich stimme dem größten Teil des oben genannten Punktes zu. Und ich stimme auch zu, dass die Liste in den meisten Fällen eine offensichtlichere Wahl aussieht.

Ich möchte jedoch nur hinzufügen, dass es viele Instanzen gibt, in denen die LinkedList für eine bessere Effizienz weitaus bessere Wahl gibt als Liste.

Angenommen, Sie durchqueren die Elemente und möchten viele Einfügungen/Löschung durchführen. LinkedList macht es in der linearen O (n) -Zeit, während die Liste in der quadratischen O (n^2) -Zeit erledigt wird.
Angenommen, Sie möchten immer wieder auf größere Objekte zugreifen, die LinkedList wird sehr nützlicher.
Deque () und Queue () werden mithilfe der LinkedList besser implementiert.
Die Erhöhung der Größe der LinkedList ist viel einfacher und besser, wenn Sie mit vielen und größeren Objekten zu tun haben.

Ich hoffe, jemand würde diese Kommentare nützlich finden.

Verwenden LinkedList<> Wenn

Sie wissen nicht, wie viele Objekte durch das Fluttor kommen. Zum Beispiel, Token Stream.
Wenn Sie nur an den Enden löschen wollten.

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

So viele durchschnittliche Antworten hier ...

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

Verwenden Sie verknüpfte Listen, wenn

1) Sie möchten Fadensicherheit. Sie können bessere Faden -Safe -Algen bauen. Die Verriegelungskosten dominieren eine gleichzeitige Liste mit gleichzeitiger Stil.

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

Ich fragte a Ähnliche Frage im Zusammenhang mit der Leistung der LinkedList -Sammlung, und entdeckt Steven Clearys C# Implementierung von Deque war eine Lösung. Im Gegensatz zur Warteschlangensammlung ermöglicht Deque das Verschieben von Gegenständen vorne und hinten. Es ähnelt der verknüpften Liste, jedoch mit einer verbesserten Leistung.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow