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

176

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

gesichtslos1_14
quelle
In Java verwenden ArrayList und LinkedList genau denselben Code außer dem Konstruktor. Ihre "Array-Liste ... wird so einfach oder einfacher als die verknüpfte Liste verwendet" macht keinen Sinn. Bitte geben Sie ein Beispiel dafür an, dass eine ArrayList "einfacher" ist als eine LinkedList.
S.Lott
2
Überprüfen Sie dies auch, stackoverflow.com/questions/322715/…
NoNaMe
Mögliches Duplikat von Array gegen verknüpfte Liste
Hawkeye Parker
3
S.Lott Das stimmt nicht. Die Java ArrayList ist ein Wrapper um ein Array, dem einige Dienstprogrammfunktionen hinzugefügt wurden. Eine verknüpfte Liste ist offensichtlich eine verknüpfte Liste. developer.classpath.org/doc/java/util/ArrayList-source.html
kingfrito_5005

Antworten:

259

Verknüpfte Listen sind Arrays vorzuziehen, wenn:

  1. Sie benötigen Einfügungen / Löschungen mit konstanter Zeit aus der Liste (z. B. beim Echtzeit-Computing, bei dem die Vorhersagbarkeit der Zeit absolut kritisch ist).

  2. Sie wissen nicht, wie viele Elemente in der Liste enthalten 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 zufälligen Zugriff auf Elemente

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

Arrays sind vorzuziehen, wenn:

  1. Sie benötigen einen 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 nacheinander 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 suchen müssen, was zu Seitenfehlern führen kann, die zu Leistungseinbußen führen können.

  4. Erinnerung ist ein Anliegen. Gefüllte Arrays beanspruchen weniger Speicher als verknüpfte Listen. Jedes Element im Array sind nur die Daten. Jeder verknüpfte Listenknoten 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 nicht zu viele Gedanken über die Listengröße machen müssen und Elemente an jedem Index ohne Aufwand oder erneutes Löschen löschen können Elemente mischen. In Bezug auf die Leistung sind Arraylisten langsamer als Raw-Arrays.

Lamar
quelle
7
Guter Start, aber dies lässt wichtige Dinge aus: Listen unterstützen die gemeinsame Nutzung von Strukturen, Arrays sind dichter und haben eine bessere Lokalität.
Darius Bacon
1
In der Praxis ist der Leistungsunterschied zwischen Arraylisten und Arrays vernachlässigbar. Dies setzt voraus, dass Sie vergleichbar vergleichen und beispielsweise, wenn Sie die Größe im Voraus kennen, der Arrayliste davon erzählen.
Svick
40
Seit wann hat LinkedList O (1) Einfügungen / Löschungen (was Sie wohl meinen, wenn Sie sagen, dass Einfügungen / Löschungen mit konstanter Zeit erfolgen )? Das Einfügen von Inhalten in die Mitte einer LinkedList ist immer O (n)
Pacerier
28
LinkedLists haben O (1) -Einfügungen, wenn Sie sich bereits an der Position der Einfügung befinden (über einen Iterator). Nicht immer.
Adam
4
Die Verwendung verknüpfter Listen für Prioritätswarteschlangen ist eine sehr dumme Idee. Dynamische Array-Backed-Heaps ermöglichen das amortisierte Einfügen von O (lg n) und das logarithmische Löschen im schlimmsten Fall (min) und gehören zu den schnellsten Warteschlangenstrukturen mit praktischer Priorität.
Fred Foo
54

Arrays haben einen O (1) -Wahlzugriff, aber das Hinzufügen oder Entfernen von Inhalten ist sehr teuer.

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

Dustin
quelle
3
Das Entfernen von Elementen vom Ende eines Arrays ist eine Kontingentzeit, ebenso wie das Einfügen / Entfernen von Elementen von beiden Enden einer verknüpften Liste. In der Mitte ... auch nicht so sehr.
Joey
1
@Joey ist das Einfügen / Löschen nicht am Ende einer verknüpften Liste O (n)? Sofern Sie nicht bereits am vorletzten Link positioniert sind, benötigen Sie noch O (n) Schritte, um das letzte Element zu finden, nicht wahr?
Alex Moore-Niemi
@ AlexMoore-Niemi: Für eine einfach verknüpfte Liste ja. Aber viele haben Links vorwärts und rückwärts und behalten daher Zeiger auf beide Enden.
Joey
2
Wenn Sie doppelt verknüpfte Listen haben, können Sie vorwärts und rückwärts suchen, es sei denn, Ihr LL hat Werte geordnet ... und das schlimmste Szenario ist immer noch O (n)
Securecurve
"Verknüpfte Listen sind wirklich billig, um Elemente überall hinzuzufügen oder zu entfernen und zu iterieren" ist nicht ganz richtig. Wenn ich ein Element entfernen möchte, das sich in der Mitte einer verknüpften Liste befindet, muss ich von Anfang an iterieren, bis ich dieses Element in der Liste erreiche. Seine O (n / 2) -Zeit, wobei n = Anzahl der Elemente in der Liste ist. Aus Ihrer Antwort geht hervor, dass Sie die konstante Zeit O (1) vorschlagen, als wäre sie im Array. Es ist eine konstante Zeit, um den Kopf- / Wurzelknoten einer verknüpften Liste hinzuzufügen / daraus zu entfernen.
Yawar Murtaza
21
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 eignen sich gut zum Schreiben, einmal Lesen, Lesen oder Anhängen, aber schlecht zum Hinzufügen / Entfernen von vorne oder in der Mitte.

Vpn_talent
quelle
14

Um die anderen Antworten zu ergänzen, reservieren die meisten Implementierungen von Array-Listen zusätzliche Kapazität am Ende der Liste, sodass neue Elemente in O (1) -Zeit am Ende der Liste hinzugefügt werden können. Wenn die Kapazität einer Array-Liste überschritten wird, wird intern ein neues, größeres Array 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 nicht im Voraus kennen, ist eine Array-Liste möglicherweise immer noch schneller als eine verknüpfte Liste zum Hinzufügen von Elementen, solange Sie sie am Ende hinzufügen. Offensichtlich ist das Einfügen neuer Elemente an beliebigen Stellen in eine Array-Liste immer noch eine O (n) -Operation.

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

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

Jay Conrod
quelle
1
Darüber hinaus können Sie verknüpfte Listen (im Sinne des abstrakten Datentyps) mithilfe dynamischer Arrays implementieren. Auf diese Weise können Sie den Computer-Cache nutzen, während Sie Einfügungen und Löschungen mit konstanter Zeit am Anfang der Liste und Einfügungen und Löschungen mit konstanter Zeit in der Mitte der Liste amortisiert haben, wenn Sie den Index des Elements haben, nach dem die Einfügung erfolgen muss durchgeführt werden oder der Index des zu löschenden Elements (keine Verschiebungen / Verschiebungen erforderlich). Eine gute Referenz hierfür ist CLRS 10.3 .
Domenico De Felice
7

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 einige sehr spezifische Fälle wie diesen, aber nicht zu viele.

Uri
quelle
Das Verschieben und Ändern der Größe des Arrays geschieht tatsächlich, wenn Sie Inversionen in der Mitte durchführen. Sie müssen nur ohne Größenänderung verschieben, wenn Sie die Amortisationsgrenze nicht erreichen.
Securecurve
3

Es hängt alles davon ab, 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 Fälle, in denen LinkedList schneller als Array ist und umgekehrt. Betrachten Sie die drei grundlegenden Operationen für Datenstrukturen.

  • Suchen

Da das Array eine indexbasierte Datenstruktur ist, dauert die Suche nach array.get (index) O (1), während die verknüpfte Liste nicht der Index DS ist. Sie müssen also zum Index wechseln, wobei der Index <= n, n die Größe der verknüpften Liste ist. Das Array ist also schneller als die verknüpfte Liste, wenn Sie zufälligen Zugriff auf Elemente haben.

Frage: 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 den Vergleich auf verbleibende Elemente des Arrays vergleichsweise schnell, da der Zugriff auf die Elemente in der Array-Referenzlokalität ebenfalls zunimmt und somit weniger Fang erfolgt Fehlt, bezieht sich die Cache-Lokalität auf die Operationen, die sich im Cache befinden und daher im Vergleich zum Speicher viel schneller ausgeführt werden. Im Array maximieren wir im Grunde genommen die Wahrscheinlichkeit, dass sich sequentielle Elemente im Cache befinden. Während verknüpfte Listen nicht unbedingt in zusammenhängenden Speicherblöcken enthalten sind, gibt es keine Garantie dafür, dass Elemente, die nacheinander in der Liste erscheinen, tatsächlich nahe beieinander im Speicher angeordnet sind. Dies bedeutet weniger Cache-Treffer, z

  • Einfügen

Dies ist in LinkedList einfach und schnell, da das Einfügen eine O (1) -Operation in LinkedList (in Java) im Vergleich zum Array ist. Wenn das Array voll ist, müssen wir den Inhalt in ein neues Array kopieren, wenn das Array voll wird, wodurch das Einfügen eines Element 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 Fall einer verknüpften Liste müssen wir die Größe nicht ändern, sondern nur Zeiger aktualisieren.

  • Streichung

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

Harleen
quelle
2

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

Anordnungsliste:

  • Einfügen / Löschen am Ende allgemein O (1) Worst Case O (n)

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

  • eine beliebige Position O (1) abrufen

LinkedList:

  • Einfügen / Löschen an einer beliebigen Position O (1) (Hinweis, wenn Sie einen Verweis auf das Element haben)

  • in der Mitte abrufen O (n)

  • erstes oder letztes Element O abrufen (1)

Vektor: benutze es nicht. Es ist eine alte Implementierung, die ArrayList ähnelt, jedoch alle Methoden synchronisiert hat. Dies ist nicht der richtige Ansatz für eine gemeinsam genutzte 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)

Praveen Kumar Verma
quelle
1

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

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

Wenn es eine Möglichkeit gibt, nacheinander 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.

user3150186
quelle
0

Hmm, Arraylist kann in 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

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

Raghu
quelle
0

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

Gizgok
quelle
0

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

2) Suchoperationen (Methode abrufen) sind in Arraylist (O (1)) schnell, jedoch nicht in LinkedList (O (n)). Wenn weniger Operationen zum Hinzufügen und Entfernen und mehr Suchoperationen erforderlich sind, ist ArrayList die beste Wahl.

Avanish Kumar
quelle
0

Ich denke, der Hauptunterschied besteht darin, ob Sie häufig Dinge am Anfang der Liste einfügen oder entfernen müssen.

Wenn Sie bei einem Array etwas vom Anfang der Liste entfernen, ist die Komplexität o (n), da sich alle Indizes der Array-Elemente verschieben müssen.

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

Wenn Sie häufig am Ende der Liste einfügen oder entfernen, sind Arrays vorzuziehen, da die Komplexität o (1) beträgt und keine Neuindizierung erforderlich ist. Bei einer verknüpften Liste ist sie jedoch o (n), da Sie vom Kopf abweichen müssen bis zum letzten Knoten.

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

Curious_goat
quelle
0

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

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

Emil Albert
quelle
Liste ist eine Schnittstelle, keine Klasse
Borgmater
0

Arrays sind bei weitem die am häufigsten verwendeten Datenstrukturen. Verknüpfte Listen erweisen sich jedoch auf ihre einzigartige Weise als nützlich, wenn Arrays ungeschickt oder teuer sind, um es gelinde auszudrücken.

Verknüpfte Listen sind nützlich, um Stapel und Warteschlangen in Situationen zu implementieren, in denen ihre Größe variieren kann. Jeder Knoten in der verknüpften Liste kann verschoben oder verschoben werden, ohne die Mehrheit der Knoten zu stören. Gleiches gilt für das Einfügen / Löschen von Knoten irgendwo in der Mitte. In Arrays müssen jedoch alle Elemente verschoben werden, was in Bezug auf die Ausführungszeit eine teure Aufgabe ist.

Binäre Bäume und binäre Suchbäume, Hash-Tabellen und Versuche sind einige der Datenstrukturen, bei denen Sie - zumindest in C - verknüpfte Listen als Grundbestandteil für deren Aufbau benötigen.

Verknüpfte Listen sollten jedoch in Situationen vermieden werden, in denen erwartet wird, dass sie ein beliebiges Element anhand ihres Index aufrufen können.

photonisch
quelle