Wann sollte ich eine Liste vs. eine LinkedList verwenden?

Question

Wann ist es besser, eine Liste gegen ein LinkedList ?

Answer 1

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

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

List<T> bietet auch eine Vielzahl von Unterstützungsmethoden - Find , ToArray usw.; diese sind jedoch auch erhältlich für LinkedList<T> mit .NET 3.5/C# 3.0 über Erweiterungsmethoden - das ist also ein geringerer Faktor.

Answer 2

Die Vorstellung, dass eine verknüpfte Liste eine Liste ist, kann ein wenig irreführend sein. Sie ist eher wie eine Kette. In der Tat, in .NET, LinkedList<T> implementiert nicht einmal IList<T> . In einer verknüpften Liste gibt es kein wirkliches Konzept für einen Index, auch wenn es den Anschein hat. Sicherlich akzeptiert keine der Methoden der Klasse Indizes.

Verknüpfte Listen können einfach oder doppelt verknüpft sein. Dies bezieht sich darauf, ob jedes Element in der Kette nur mit dem nächsten verknüpft ist (einfach verknüpft) oder sowohl mit dem vorherigen als auch mit dem nächsten Element (doppelt verknüpft). LinkedList<T> ist doppelt verknüpft.

Intern, List<T> wird durch ein Array unterstützt. Dies ermöglicht eine sehr kompakte Darstellung im Speicher. Umgekehrt, LinkedList<T> erfordert zusätzlichen Speicher, um die bidirektionalen Verbindungen zwischen aufeinanderfolgenden Elementen zu speichern. Daher ist der Speicherbedarf eines LinkedList<T> wird im Allgemeinen größer sein als bei List<T> (unter dem Vorbehalt, dass List<T> können ungenutzte interne Array-Elemente haben, um die Leistung bei Append-Operationen zu verbessern).

Sie haben auch unterschiedliche Leistungsmerkmale:

Anhängen

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

vorangestellt.

• 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

Umzug

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

Zählen Sie

• 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 weitgehend gleichwertig. In der Praxis ist die API von LinkedList<T> ist umständlicher in der Anwendung, und die Details der internen Anforderungen fließen in Ihren Code ein.

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

Answer 3

Verknüpfte Listen ermöglichen ein sehr schnelles Einfügen oder Löschen eines Listenelements. Jedes Mitglied einer verknüpften Liste enthält einen Zeiger auf das nächste Mitglied in der Liste, so dass ein Mitglied an Position i eingefügt werden kann:

• den Zeiger in Mitglied i-1 aktualisieren, damit er auf das neue Mitglied zeigt
• den Zeiger im neuen Element auf das Element i setzen

Der Nachteil einer verknüpften Liste besteht darin, dass ein zufälliger Zugriff nicht möglich ist. Um auf ein Mitglied zuzugreifen, muss die Liste durchlaufen werden, bis das gewünschte Mitglied gefunden ist.

Answer 4

Bearbeiten

Bitte lesen Sie die Kommentare zu dieser Antwort. Die Leute behaupten, ich hätte nicht nicht richtig getestet. Ich stimme zu, dass dies keine akzeptierte Antwort sein sollte. Als ich noch lernte, machte ich einige Tests und wollte sie mit anderen 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 man nur auf Daten zugreift, ist es viel langsamer!! Ich sage, verwenden Sie niemals eine linkedList.

---

---

---

Hier ist ein weiterer Vergleich, bei dem viele Einfügungen vorgenommen werden (wir planen, ein Element 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 Verweis auf den Ort, an dem eingefügt werden soll (.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 Artikel einzufügen und Sie auch irgendwo den Verweis auf die Stelle haben, an der Sie das Element einfügen möchten, dann verwenden Sie eine verknüpfte Liste. Nur weil Sie viele Elemente einfügen müssen, wird es nicht schneller, denn die Suche nach der Stelle, an der Sie das Element einfügen möchten, dauert.

Answer 5

Meine vorherige Antwort war nicht genau genug. Denn sie war wirklich schrecklich :D Aber jetzt kann ich viel mehr nützliche und korrekte Antwort posten.

---

Ich habe einige zusätzliche Tests durchgeführt. Sie können die Quelle unter folgendem Link finden und sie in Ihrer Umgebung selbst überprüfen: https://github.com/ukushu/DataStructuresTestsAndOther.git

Kurze Ergebnisse:

• Array verwenden müssen:

  • 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 die im Array gespeicherten Daten < 85000 b sind (85000/32 = 2656 Elemente für Integer-Daten)
  • Bei Bedarf hohe Zufallszugriffsgeschwindigkeit

• Liste verwenden müssen:

  • Falls erforderlich, um Zellen am Ende der Liste hinzuzufügen (häufig)
  • Falls erforderlich, um Zellen am Anfang/Mitte der Liste hinzuzufügen (NICHT ÖFFENTLICH)
  • Wenn die im Array gespeicherten Daten < 85000 b sind (85000/32 = 2656 Elemente für Integer-Daten)
  • Bei Bedarf hohe Zufallszugriffsgeschwindigkeit

• LinkedList verwenden müssen:

  • Falls erforderlich, um Zellen am Anfang/Mitte/Ende der Liste hinzuzufügen (häufig)
  • Bei Bedarf nur sequentieller Zugriff (vorwärts/rückwärts)
  • Wenn Sie GROSSE Artikel speichern müssen, aber die Anzahl der Artikel gering ist.
  • Verwenden Sie diese Funktion besser nicht für eine große Anzahl von Elementen, da sie zusätzlichen Speicher für Links benötigt.

Weitere Einzelheiten:

Interessant zu wissen:

1. LinkedList<T> ist intern keine Liste in .NET. Es ist sogar nicht implementiert IList<T> . Deshalb gibt es auch keine Indizes und keine Methoden, die mit Indizes zusammenhängen.

2. LinkedList<T> ist eine auf Knotenzeigern basierende Sammlung. In .NET ist es eine doppelt verknüpfte Implementierung. Das bedeutet, dass vorherige/nächste Elemente einen Link zum aktuellen Element haben. Und die Daten sind fragmentiert - verschiedene Listenobjekte können sich an verschiedenen Stellen im RAM befinden. Außerdem wird mehr Speicher verwendet für LinkedList<T> als für List<T> oder Array.

3. List<T> in .Net ist Javas Alternative zu ArrayList<T> . Das bedeutet, dass dies ein Array-Wrapper ist. Es wird also im Speicher als ein zusammenhängender Datenblock zugewiesen. Wenn die Größe der zugewiesenen Daten 85000 Bytes überschreitet, werden sie in den Large Object Heap verschoben. Je nach Größe kann dies zu einer Fragmentierung des Heaps führen (eine milde Form eines Speicherlecks). Bei einer Größe von weniger als 85000 Bytes bietet dies jedoch eine sehr kompakte und schnell zugängliche Darstellung im Speicher.

4. Für Sammlungen, deren Größe sich regelmäßig ändert, muss eine Struktur wie ein Array im Allgemeinen an einen neuen Ort kopiert werden, während eine verknüpfte Liste nur den Speicher für die neu eingefügten/gelöschten Knoten verwalten muss.