webentwicklung-frage-antwort-db.com.de

Wann soll eine verknüpfte Liste über einem Array / einer Array-Liste verwendet werden?

Ich verwende viele Listen und Arrays, aber ich muss noch auf ein Szenario stoßen, in dem die Array-Liste nicht so einfach wie die verknüpfte Liste verwendet werden kann, wenn nicht sogar einfacher. Ich hatte gehofft, jemand könnte mir einige Beispiele geben, wenn die verknüpfte Liste deutlich besser ist.

157
faceless1_14

Verknüpfte Listen sind Arrays vorzuziehen, wenn:

  1. sie benötigen Einfügungen/Löschungen in konstanter Zeit aus der Liste (z. B. beim Echtzeit-Computing, bei dem die Vorhersagbarkeit der Zeit von entscheidender Bedeutung ist).

  2. sie wissen nicht, wie viele Elemente in der Liste sein werden. Bei Arrays müssen Sie möglicherweise den Speicher neu deklarieren und kopieren, wenn das Array zu groß wird

  3. sie benötigen keinen wahlfreien Zugriff auf Elemente

  4. sie möchten in der Lage sein, Elemente in der Mitte der Liste einzufügen (z. B. eine Prioritätswarteschlange).

Arrays sind vorzuziehen, wenn:

  1. sie benötigen indizierten/zufälligen Zugriff auf Elemente

  2. sie kennen die Anzahl der Elemente im Array im Voraus, damit Sie die richtige Speichermenge für das Array zuweisen können

  3. sie benötigen Geschwindigkeit, wenn Sie alle Elemente der Reihe nach durchlaufen. Sie können Zeigermathematik für das Array verwenden, um auf jedes Element zuzugreifen, während Sie den Knoten basierend auf dem Zeiger für jedes Element in der verknüpften Liste nachschlagen müssen. Dies kann zu Seitenfehlern führen, die zu Leistungseinbußen führen können.

  4. erinnerung ist ein Anliegen. Gefüllte Arrays belegen weniger Speicher als verknüpfte Listen. Jedes Element im Array besteht nur aus den Daten. Jeder Knoten der verknüpften Liste benötigt die Daten sowie einen (oder mehrere) Zeiger auf die anderen Elemente in der verknüpften Liste.

Array-Listen (wie die in .Net) bieten Ihnen die Vorteile von Arrays, weisen Ihnen jedoch dynamisch Ressourcen zu, sodass Sie sich keine Sorgen um die Listengröße machen müssen und Elemente an jedem Index ohne Aufwand und ohne erneute Aktualisierung gelöscht werden können. Elemente herum mischen. In Bezug auf die Leistung sind Arraylisten langsamer als unformatierte Arrays.

238
Lamar

Arrays haben O(1) zufälligen Zugriff, sind aber sehr teuer, um Inhalte hinzuzufügen oder zu entfernen.

Verknüpfte Listen sind wirklich billig, um Elemente überall hinzuzufügen oder zu entfernen und zu iterieren, aber der wahlfreie Zugriff ist O (n).

54
Dustin
Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

ArrayLists sind gut für Write-Once-Read-Many oder Appender, aber schlecht für das Hinzufügen/Entfernen von vorne oder in der Mitte.

17
Vpn_talent

Um die anderen Antworten zu ergänzen, reservieren die meisten Arraylistenimplementierungen zusätzliche Kapazität am Ende der Liste, sodass neue Elemente zum Ende der Liste in der Zeit O(1) hinzugefügt werden können. Wenn die Kapazität einer Array-Liste überschritten wird, wird ein neues, größeres Array intern zugewiesen und alle alten Elemente werden kopiert. Normalerweise ist das neue Array doppelt so groß wie das alte. Dies bedeutet, dass das Hinzufügen neuer Elemente am Ende einer Array-Liste in diesen Implementierungen im Durchschnitt eine O(1) -Operation ist . Selbst wenn Sie die Anzahl der Elemente im Voraus nicht kennen, ist eine Array-Liste möglicherweise schneller als eine verknüpfte Liste zum Hinzufügen von Elementen, solange Sie sie am Ende hinzufügen. Das Einfügen neuer Elemente an beliebigen Stellen in einer Array-Liste ist natürlich immer noch eine O(n) -Operation.

Der Zugriff auf Elemente in einer Array-Liste ist auch dann schneller als bei einer verknüpften Liste, wenn die Zugriffe sequentiell sind. Dies liegt daran, dass Array-Elemente in einem zusammenhängenden Speicher gespeichert werden und einfach zwischengespeichert werden können. Verknüpfte Listenknoten können möglicherweise über viele verschiedene Seiten verteilt sein.

Ich würde nur empfehlen, eine verknüpfte Liste zu verwenden, wenn Sie wissen, dass Sie Elemente an beliebigen Stellen einfügen oder löschen. Array-Listen sind für so ziemlich alles andere schneller.

14
Jay Conrod

Der Vorteil von Listen wird angezeigt, wenn Sie Elemente in der Mitte einfügen müssen und nicht mit der Größenänderung des Arrays und dem Verschieben von Elementen beginnen möchten.

Sie haben Recht, dass dies normalerweise nicht der Fall ist. Ich hatte ein paar sehr spezifische Fälle, aber nicht zu viele.

7
Uri

Dies sind die am häufigsten verwendeten Implementierungen von Collection.

ArrayList:

  • einfügen/Löschen am Ende im Allgemeinen O(1) Worst Case O (n)

  • einfügen/Löschen in der Mitte O (n)

  • beliebige Position abrufen O (1)

LinkedList:

  • einfügen/Löschen an beliebiger Stelle O(1) (Hinweis, wenn Sie einen Verweis auf das Element haben)

  • in der Mitte abrufen O (n)

  • erstes oder letztes Element O abrufen (1)

Vector: benutze es nicht. Es handelt sich um eine alte Implementierung, die ArrayList ähnelt, bei der jedoch alle Methoden synchronisiert sind. Dies ist nicht der richtige Ansatz für eine freigegebene Liste in einer Multithreading-Umgebung.

HashMap

einfügen/Löschen/Abrufen durch Eingabe von O (1)

TreeSet Einfügen/Löschen/Enthält in O (Log N)

HashSet Einfügen/Entfernen/Enthält/Größe in O (1)

2

Es kommt darauf an, welche Art von Operation Sie während der Iteration ausführen. Alle Datenstrukturen haben einen Kompromiss zwischen Zeit und Speicher. Abhängig von unseren Anforderungen sollten wir den richtigen DS auswählen. Es gibt also einige Fälle, in denen LinkedList schneller ist als Array und umgekehrt. Betrachten Sie die drei grundlegenden Operationen für Datenstrukturen.

  • Suche

Da das Array eine indexbasierte Datenstruktur ist, dauert die Suche nach array.get (index) O(1) Zeit, während die verknüpfte Liste nicht indexiert ist DS) Durchsuchen Sie den Index, wobei Index <= n, n die Größe der verknüpften Liste ist, sodass Array die verknüpfte Liste schneller ist, wenn Sie über einen wahlfreien Zugriff auf Elemente verfügen.

Q.So was ist die Schönheit dahinter?

Da Arrays zusammenhängende Speicherblöcke sind, werden beim ersten Zugriff große Teile davon in den Cache geladen. Dies macht es vergleichsweise schnell, auf die verbleibenden Elemente des Arrays zuzugreifen, da der Zugriff auf die Elemente in der Array-Referenzlokalität ebenfalls zunimmt und damit weniger catch Wenn dies nicht der Fall ist, bezieht sich die Cache-Lokalität darauf, dass sich die Operationen im Cache befinden und daher im Vergleich zum Arbeitsspeicher viel schneller ausgeführt werden. Grundsätzlich maximieren wir im Array die Chancen, dass der sequentielle Elementzugriff im Cache erfolgt. Während verknüpfte Listen nicht notwendigerweise in zusammenhängenden Speicherblöcken gespeichert sind, gibt es keine Garantie dafür, dass Elemente, die nacheinander in der Liste angezeigt werden, tatsächlich im Speicher nebeneinander angeordnet sind. Dies bedeutet, dass weniger Cache-Treffer, z. mehr Cache-Fehlschläge, da wir für jeden Zugriff auf verknüpfte Listenelemente Daten aus dem Speicher lesen müssen, was die Zugriffszeit und die Leistung verringert. Wenn wir also mehr Direktzugriffsoperationen (auch Suchen genannt) ausführen, ist das Array wie unten erläutert schnell.

  • Einfügung

Dies ist in LinkedList einfach und schnell, da das Einfügen in LinkedList (in Java) eine O(1) - Operation ist. Betrachten Sie den Fall, wenn das Array voll ist, müssen Sie den Inhalt in new kopieren Array, wenn Array voll wird, wodurch das Einfügen eines Elements in ArrayList von O(n) im schlimmsten Fall, während ArrayList auch seinen Index aktualisieren muss, wenn Sie irgendwo etwas einfügen, außer am Ende des Arrays, Im Falle einer verknüpften Liste muss deren Größe nicht geändert werden. Sie müssen lediglich die Zeiger aktualisieren.

  • Löschung

Es funktioniert wie Einfügungen und ist in LinkedList besser als in Array.

2
Harleen

In der Realität hat die Speicherlokalität einen großen Einfluss auf die Leistung der realen Verarbeitung.

Die zunehmende Verwendung von Festplatten-Streaming bei der "Big Data" -Verarbeitung im Vergleich zum Direktzugriff zeigt, wie die Strukturierung Ihrer Anwendung die Leistung in größerem Maßstab erheblich verbessern kann.

Wenn es eine Möglichkeit gibt, sequentiell auf ein Array zuzugreifen, ist dies bei weitem die beste Leistung. Das Entwerfen mit diesem Ziel sollte zumindest in Betracht gezogen werden, wenn Leistung wichtig ist.

1
user3150186

Ich habe ein Benchmarking durchgeführt und festgestellt, dass die Listenklasse beim zufälligen Einfügen tatsächlich schneller ist als LinkedList:

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 20000;
            Random Rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            ll.AddLast(0);
            for (int i = 1; i < count; i++)
            {
                ll.AddBefore(ll.Find(Rand.Next(i)),i);

            }
            Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);

            watch = Stopwatch.StartNew();
            List<int> list = new List<int>();
            list.Add(0);
            for (int i = 1; i < count; i++)
            {
                list.Insert(list.IndexOf(Rand.Next(i)), i);

            }
            Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

Es dauert 900 ms für die verknüpfte Liste und 100 ms für die Listenklasse.

Es werden Listen nachfolgender ganzzahliger Zahlen erstellt. Jede neue Ganzzahl wird nach einer Zufallszahl eingefügt, die bereits in der Liste enthalten ist. Vielleicht verwendet die List-Klasse etwas Besseres als nur ein Array.

1
Emil Albert

Ich denke, der Hauptunterschied besteht darin, ob Sie häufig Dinge einfügen oder entfernen müssen, die ganz oben auf der Liste stehen.

Wenn Sie bei einem Array etwas von der obersten Liste entfernen, ist die Komplexität o(n), da alle Indizes der Array-Elemente verschoben werden müssen.

Bei einer verknüpften Liste ist dies o(1), da Sie nur den Knoten erstellen, den Kopf neu zuweisen und den Verweis als vorherigen Kopf dem nächsten zuweisen müssen.

Beim häufigen Einfügen oder Entfernen am Ende der Liste sind Arrays vorzuziehen, da die Komplexität 0 (1) beträgt und keine erneute Indizierung erforderlich ist. Bei einer verknüpften Liste ist dies jedoch o(n) = weil Sie vom Kopf bis zum letzten Knoten gehen müssen.

Ich denke, dass die Suche sowohl in verknüpften Listen als auch in Arrays "o" (log n) ist, da Sie wahrscheinlich eine binäre Suche verwenden werden.

0
Curious_goat

Hmm, Arraylist kann in den folgenden Fällen verwendet werden:

  1. sie sind sich nicht sicher, wie viele Elemente vorhanden sein werden
  2. sie müssen jedoch durch Indizierung zufällig auf alle Elemente zugreifen

Beispielsweise müssen Sie alle Elemente in einer Kontaktliste (deren Größe Ihnen unbekannt ist) importieren und darauf zugreifen.

0
Raghu

1) Wie oben erläutert, bieten die Einfüge- und Entfernungsoperationen eine gute Leistung (O (1)) in LinkedList im Vergleich zu ArrayList (O (n)). Daher ist LinkedList die beste Wahl, wenn die Anwendung häufig hinzugefügt und gelöscht werden muss.

2) Suchoperationen (Get-Methode) sind in Arraylist (O (1)) schnell, aber nicht in LinkedList (O (n)). Wenn weniger Hinzufügungs- und Entfernungsoperationen und mehr Suchoperationen erforderlich sind, ist ArrayList die beste Wahl.

0
Avanish Kumar

Verwenden Sie die verknüpfte Liste für Radix-Sortierung über Arrays und für Polynomoperationen.

0
gizgok