Ich war schon immer einer, der einfach benutzte:
List<String> names = new ArrayList<>();
Ich verwende die Schnittstelle als Typnamen für die Portabilität , damit ich meinen Code überarbeiten kann, wenn ich Fragen wie diese stelle.
Wann sollte LinkedList
verwendet werden ArrayList
und umgekehrt?
java
arraylist
collections
linked-list
sdellysse
quelle
quelle
Antworten:
Zusammenfassung
ArrayList
mitArrayDeque
sind in viel mehr Anwendungsfällen vorzuziehen alsLinkedList
. Wenn Sie sich nicht sicher sind, beginnen Sie einfach mitArrayList
.LinkedList
undArrayList
sind zwei verschiedene Implementierungen der List-Schnittstelle.LinkedList
implementiert es mit einer doppelt verknüpften Liste.ArrayList
implementiert es mit einem Array mit dynamischer Größenänderung.Wie bei Standardoperationen für verknüpfte Listen und Arrays haben die verschiedenen Methoden unterschiedliche algorithmische Laufzeiten.
Zum
LinkedList<E>
get(int index)
ist O (n) (mit durchschnittlich n / 4 Schritten), aber O (1) wannindex = 0
oderindex = list.size() - 1
(in diesem Fall können Sie auchgetFirst()
und verwendengetLast()
). Einer der Hauptvorteile vonLinkedList<E>
add(int index, E element)
ist O (n) (mit durchschnittlich n / 4 Schritten), aber O (1) wannindex = 0
oderindex = list.size() - 1
(in diesem Fall können Sie auchaddFirst()
undaddLast()
/add()
) verwenden. Einer der Hauptvorteile vonLinkedList<E>
remove(int index)
ist O (n) (mit durchschnittlich n / 4 Schritten), aber O (1) wannindex = 0
oderindex = list.size() - 1
(in diesem Fall können Sie auchremoveFirst()
und verwendenremoveLast()
). Einer der Hauptvorteile vonLinkedList<E>
Iterator.remove()
ist O (1) . Einer der Hauptvorteile vonLinkedList<E>
ListIterator.add(E element)
ist O (1) . Einer der Hauptvorteile vonLinkedList<E>
Hinweis: Viele der Operationen benötigen durchschnittlich n / 4 Schritte, im besten Fall eine konstante Anzahl von Schritten (z. B. Index = 0) und im schlechtesten Fall (Mitte der Liste) n / 2 Schritte.
Zum
ArrayList<E>
get(int index)
ist O (1) . Hauptvorteil vonArrayList<E>
add(E element)
ist O (1) amortisiert, aber O (n) im schlimmsten Fall, da die Größe des Arrays geändert und kopiert werden mussadd(int index, E element)
ist O (n) (mit durchschnittlich n / 2 Schritten)remove(int index)
ist O (n) (mit durchschnittlich n / 2 Schritten)Iterator.remove()
ist O (n) (mit durchschnittlich n / 2 Schritten)ListIterator.add(E element)
ist O (n) (mit durchschnittlich n / 2 Schritten)Hinweis: Viele der Operationen benötigen durchschnittlich n / 2 Schritte, im besten Fall eine konstante Anzahl von Schritten (Ende der Liste), im schlechtesten Fall n Schritte (Beginn der Liste)
LinkedList<E>
Ermöglicht zeitlich konstante Einfügungen oder Entfernungen mithilfe von Iteratoren , jedoch nur den sequentiellen Zugriff auf Elemente. Mit anderen Worten, Sie können die Liste vorwärts oder rückwärts gehen, aber das Finden einer Position in der Liste benötigt Zeit, die proportional zur Größe der Liste ist. Javadoc sagt, "Operationen, die in die Liste indizieren, durchlaufen die Liste vom Anfang oder vom Ende, je nachdem, was näher liegt" , so dass diese Methoden im Durchschnitt O (n) ( n / 4 Schritte) sind, obwohl O (1) fürindex = 0
.ArrayList<E>
Ermöglichen Sie andererseits einen schnellen zufälligen Lesezugriff, sodass Sie jedes Element in konstanter Zeit erfassen können. Das Hinzufügen oder Entfernen von einer anderen Stelle als dem Ende erfordert jedoch das Verschieben aller letzteren Elemente, um entweder eine Öffnung herzustellen oder die Lücke zu füllen. Auch, wenn Sie mehr Elemente als die Kapazität des zugrunde liegenden Array hinzufügen, wird ein neues Array ( die 1,5 - fache der Größe) zugeordnet, und die alte Array wird auf den neuen kopiert, wenn man so eine ZugabeArrayList
ist O (n) im schlechtesten Fall aber im Durchschnitt konstant.Abhängig von den geplanten Vorgängen sollten Sie die Implementierungen entsprechend auswählen. Das Iterieren über jede Art von Liste ist praktisch gleich billig. (Das Iterieren über ein
ArrayList
ist technisch schneller, aber wenn Sie nicht etwas wirklich Leistungsempfindliches tun, sollten Sie sich darüber keine Sorgen machen - beide sind Konstanten.)Die Hauptvorteile der Verwendung von a
LinkedList
ergeben sich, wenn Sie vorhandene Iteratoren zum Einfügen und Entfernen von Elementen wiederverwenden. Diese Operationen können dann in O (1) ausgeführt werden, indem die Liste nur lokal geändert wird. In einer Array-Liste muss der Rest des Arrays verschoben (dh kopiert) werden. Auf der anderen Seite kann in einemLinkedList
Mittel nach den Verknüpfungen in O (n) ( n / 2 Schritte) nach dem schlimmsten Fall gesucht werden, während in einerArrayList
gewünschten Position mathematisch berechnet und in O (1) zugegriffen werden kann .Ein weiterer Vorteil der Verwendung von a
LinkedList
ergibt sich, wenn Sie den Kopf der Liste hinzufügen oder daraus entfernen, da diese Operationen O (1) sind , während sie O (n) für sindArrayList
. Beachten Sie, dassArrayDeque
dies eine gute Alternative zumLinkedList
Hinzufügen und Entfernen vom Kopf sein kann, aber keineList
.Wenn Sie große Listen haben, beachten Sie auch, dass die Speichernutzung ebenfalls unterschiedlich ist. Jedes Element von a
LinkedList
hat mehr Overhead, da auch Zeiger auf das nächste und das vorherige Element gespeichert werden.ArrayLists
habe diesen Overhead nicht. AllerdingsArrayLists
nehmen so viel Speicher wie oben für die Kapazität zugeordnet ist, unabhängig davon , ob Elemente tatsächlich hinzugefügt.Die Standard-Anfangskapazität von a
ArrayList
ist ziemlich klein (10 von Java 1.4 - 1.8). Da es sich bei der zugrunde liegenden Implementierung jedoch um ein Array handelt, muss die Größe des Arrays geändert werden, wenn Sie viele Elemente hinzufügen. Um die hohen Kosten für die Größenänderung zu vermeiden, wenn Sie wissen, dass Sie viele Elemente hinzufügen werden, erstellen Sie dieArrayList
mit einer höheren Anfangskapazität.quelle
O(n/2)
oderO(n/4)
. Die große O-Notation gibt an, wie eine Operation mit einem größeren n skaliert wird . und eine Operation, die Schritte benötigt , skaliert genau wie eine Operation, die Schritte benötigt, was der Grund ist, warum konstante Summanden oder Faktoren entfernt werden. und sind beide gerecht . und haben sowieso unterschiedliche konstante Faktoren, so dass es keinen Sinn macht, einen von einem mit einem von dem anderen zu vergleichen , beide bezeichnen nur linear skalierende Operationen.n/2
n
O(n/2)
O(n/4)
O(n)
LinkedList
ArrayList
O(n/2)
O(n/4)
Bisher scheint sich niemand mit dem Speicherbedarf jeder dieser Listen befasst zu haben, außer dem allgemeinen Konsens, dass a
LinkedList
"viel mehr" als a ist. DeshalbArrayList
habe ich einige Zahlen eingegeben, um genau zu demonstrieren, wie viel beide Listen für N Nullreferenzen beanspruchen.Da Referenzen auf ihren relativen Systemen entweder 32 oder 64 Bit (auch wenn sie null sind) sind, habe ich 4 Datensätze für 32 und 64 Bit
LinkedLists
und eingefügtArrayLists
.Hinweis: Die für die
ArrayList
Zeilen angezeigten Größen gelten für zugeschnittene Listen. In der Praxis ist die Kapazität des Hintergrundarrays in einemArrayList
im Allgemeinen größer als die aktuelle Elementanzahl.Hinweis 2: (danke BeeOnRope) Da CompressedOops ab Mitte JDK6 standardmäßig aktiviert ist, stimmen die folgenden Werte für 64-Bit-Computer grundsätzlich mit den 32-Bit-Gegenstücken überein, es sei denn, Sie deaktivieren sie ausdrücklich.
Das Ergebnis zeigt deutlich, dass dies
LinkedList
viel mehr ist alsArrayList
, insbesondere bei einer sehr hohen Elementanzahl. Wenn das Gedächtnis ein Faktor ist, meiden Sie esLinkedLists
.Die von mir verwendeten Formeln folgen, lassen Sie mich wissen, wenn ich etwas falsch gemacht habe, und ich werde es reparieren. 'b' ist entweder 4 oder 8 für 32- oder 64-Bit-Systeme und 'n' ist die Anzahl der Elemente. Beachten Sie, dass der Grund für die Mods darin besteht, dass alle Objekte in Java ein Vielfaches von 8 Byte Speicherplatz belegen, unabhängig davon, ob alles verwendet wird oder nicht.
Anordnungsliste:
ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)
LinkedList:
LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)
quelle
int
4 oder 8 Datenbytes enthalten. In der verknüpften Liste gibt es im Wesentlichen 4 "Wörter" Overhead. Ihr Diagramm vermittelt somit den Eindruck, dass verknüpfte Listen "fünfmal" die Speicherung von Array-Listen verwenden. Das ist falsch. Der Overhead beträgt 16 oder 32 Bytes pro Objekt als additive Anpassung, nicht als Skalierungsfaktor.CompressedOops
jetzt in allen aktuellen JDKs (7, 8 und Aktualisierungen von 6 für einige Jahre) Standard ist, sodass 64-Bit keinen Unterschied inArrayList
oderLinkedList
Größe macht, es sei denn, Sie haben komprimierte Hoppla für explizit deaktiviert irgendein Grund.ArrayList
ohne Angabe einer Anfangskapazität füllen, wird immer noch deutlich weniger Speicher als bei a benötigtLinkedList
.ArrayList
ist was du willst.LinkedList
ist fast immer ein (Leistungs-) Fehler.Warum
LinkedList
saugt:ArrayList
verwendet würden.ArrayList
, wird sie wahrscheinlich ohnehin erheblich langsamer sein.LinkedList
in der Quelle zu sehen, weil es wahrscheinlich die falsche Wahl ist.quelle
Als jemand, der seit etwa einem Jahrzehnt Operational Performance Engineering für SOA-Webdienste in sehr großem Maßstab durchführt, würde ich das Verhalten von LinkedList ArrayList vorziehen. Während der stationäre Durchsatz von LinkedList schlechter ist und daher zum Kauf von mehr Hardware führen kann, kann das Verhalten von ArrayList unter Druck dazu führen, dass Apps in einem Cluster ihre Arrays nahezu synchron erweitern und bei großen Array-Größen zu mangelnder Reaktionsfähigkeit führen in der App und ein Ausfall, während unter Druck, was katastrophales Verhalten ist.
In ähnlicher Weise können Sie einen besseren Durchsatz in einer App mit dem Standard-Garbage Collector mit festem Durchsatz erzielen. Sobald Sie jedoch Java-Apps mit 10 GB Heaps erhalten, können Sie die App während eines vollständigen GCs für 25 Sekunden sperren, was zu Zeitüberschreitungen und Fehlern in SOA-Apps führt und bläst Ihre SLAs, wenn es zu oft auftritt. Obwohl der CMS-Kollektor mehr Ressourcen benötigt und nicht den gleichen Rohdurchsatz erzielt, ist er eine viel bessere Wahl, da er eine vorhersehbarere und geringere Latenz aufweist.
ArrayList ist nur dann eine bessere Wahl für die Leistung, wenn Sie unter Leistung nur den Durchsatz verstehen und die Latenz ignorieren können. Nach meiner Berufserfahrung kann ich die Latenz im schlimmsten Fall nicht ignorieren.
quelle
LinkedList
immer das Fünffache des Speichers zu als ein einfaches Array von Referenzen, sodass einArrayList
vorübergehend erforderliches 2,5- faches immer noch viel weniger Speicher verbraucht, selbst wenn der Speicher nicht zurückgefordert wird. Da die Zuweisung großer Arrays den Eden-Raum umgeht, haben sie keinen Einfluss auf das GC-Verhalten, es sei denn, es ist wirklich nicht genügend Speicher vorhanden. In diesem Fall ist dasLinkedList
viel früherLinkedList
benötigt nur ein kleines Stück freien Speichers, um das nächste Element zuzuweisen.ArrayList
benötigt einen großen und durchgehenden freien Speicherplatzblock, um das Array mit geänderter Größe zuzuweisen. Wenn der Heap fragmentiert wird, ordnet GC möglicherweise den gesamten Heap neu an, um einen geeigneten einzelnen Speicherblock freizugeben.Algorithmen: Big-Oh-Notation
ArrayLists eignen sich gut zum Schreiben, einmal Lesen, Lesen oder Anhängen, aber schlecht zum Hinzufügen / Entfernen von vorne oder in der Mitte.
quelle
O(1)
. Es muss die Hälfte der Liste durchlaufen, um die Einfügemarke zu finden.LinkedList
ist,O(1)
wenn Sie einen Iterator für die Einfügeposition haben , dhListIterator.add
angeblichO(1)
für aLinkedList
.Ja, ich weiß, das ist eine alte Frage, aber ich werde meine zwei Cent einwerfen:
LinkedList ist in Bezug auf die Leistung fast immer die falsche Wahl. Es gibt einige sehr spezifische Algorithmen, für die eine LinkedList erforderlich ist, aber diese sind sehr, sehr selten, und der Algorithmus hängt normalerweise speziell von der Fähigkeit von LinkedList ab, Elemente in der Mitte der Liste relativ schnell einzufügen und zu löschen, sobald Sie dort navigiert sind mit einem ListIterator.
Es gibt einen häufigen Anwendungsfall, in dem LinkedList ArrayList übertrifft: den einer Warteschlange. Wenn Ihr Ziel jedoch die Leistung ist, sollten Sie anstelle von LinkedList auch die Verwendung einer ArrayBlockingQueue (wenn Sie im Voraus eine Obergrenze für Ihre Warteschlangengröße festlegen und es sich leisten können, den gesamten Speicher im Voraus zuzuweisen) oder dieser CircularArrayList-Implementierung in Betracht ziehen . (Ja, es ist aus dem Jahr 2001, Sie müssen es also generieren, aber ich habe vergleichbare Leistungsverhältnisse wie in dem Artikel, der gerade in einer kürzlich erschienenen JVM zitiert wurde.)
quelle
ArrayDeque
. docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.htmlArrayDeque
ist langsamer alsLinkedList
wenn nicht alle Operationen am selben Ende sind. Es ist in Ordnung, wenn es als Stapel verwendet wird, aber es macht keine gute Warteschlange.ArrayDeque
ist wahrscheinlich schneller alsStack
bei Verwendung als Stapel und schneller alsLinkedList
bei Verwendung als Warteschlange.ArrayDeque
Dokumentation ist.Es ist eine Effizienzfrage.
LinkedList
ist schnell zum Hinzufügen und Löschen von Elementen, aber langsam zum Zugreifen auf ein bestimmtes Element.ArrayList
ist schnell für den Zugriff auf ein bestimmtes Element, kann jedoch an beiden Enden langsam hinzugefügt und in der Mitte besonders langsam gelöscht werden.Array vs ArrayList vs LinkedList vs Vector geht tiefer, ebenso wie Linked List .
quelle
Richtig oder falsch: Bitte führen Sie den Test lokal durch und entscheiden Sie selbst!
Bearbeiten / Entfernen ist schneller
LinkedList
alsArrayList
.ArrayList
, unterstützt vonArray
, das doppelt so groß sein muss, ist bei großvolumigen Anwendungen schlechter.Nachfolgend finden Sie das Unit-Testergebnis für jede Operation. Die Zeitangabe erfolgt in Nanosekunden.
Hier ist der Code:
quelle
LinkedList
hat viel mehr Speicheraufwand, da für jedes Element ein Knotenobjekt mit fünf Feldern vorhanden ist. Auf vielen Systemen macht das 20 Bytes Overhead. Der durchschnittliche Speicheraufwand pro Element fürArrayList
beträgt eineinhalb Wörter, was 6 Bytes und im schlimmsten Fall 8 Bytes ergibt.removeIf(element -> condition)
wo es passt, was für a imArrayList
Vergleich zum Schleifen und Entfernen per Iterator erheblich schneller sein kann , da nicht der gesamte Rest für jedes einzelne Element verschoben werden muss. Ob dies besser oder schlechter abschneidet als dies,LinkedList
hängt vom jeweiligen Szenario ab, da aLinkedList
theoretisch O (1) ist. Das Entfernen nur eines einzelnen Knotens erfordert jedoch mehrere Speicherzugriffe, die leicht die Anzahl überschreiten können, die zumArrayList
Entfernen einer signifikanten Anzahl von Elementen erforderlich ist .ArrayList
ist im Wesentlichen ein Array.LinkedList
wird als doppelt verknüpfte Liste implementiert.Das
get
ist ziemlich klar. O (1) fürArrayList
, da derArrayList
zufällige Zugriff mithilfe des Index möglich ist. O (n) fürLinkedList
, weil es zuerst den Index finden muss. Hinweis: Es gibt verschiedene Versionen vonadd
undremove
.LinkedList
ist schneller beim Hinzufügen und Entfernen, aber langsamer beim Abrufen. Kurz gesagt,LinkedList
sollte bevorzugt werden, wenn:=== ArrayList ===
=== LinkedList ===
addiere (E e)
add (int index, E element)
Hier ist eine Abbildung von programcreek.com (
add
undremove
sind der erste Typ, dh fügen Sie ein Element am Ende der Liste hinzu und entfernen Sie das Element an der angegebenen Position in der Liste.):quelle
Joshua Bloch, der Autor von LinkedList:
Link: https://twitter.com/joshbloch/status/583813919019573248
Es tut mir leid, dass die Antwort nicht so informativ ist wie die anderen Antworten, aber ich dachte, sie wäre die interessanteste und selbsterklärendste.
quelle
ArrayList
ist zufällig zugänglich, währendLinkedList
es wirklich billig ist, Elemente zu erweitern und zu entfernen. In den meisten FällenArrayList
ist in Ordnung.Wenn Sie keine großen Listen erstellt und keinen Engpass gemessen haben, müssen Sie sich wahrscheinlich nie um den Unterschied kümmern.
quelle
TL; DR wird aufgrund der modernen Computerarchitektur
ArrayList
für nahezu jeden möglichen Anwendungsfall wesentlich effizienter sein - undLinkedList
sollte daher mit Ausnahme einiger sehr einzigartiger und extremer Fälle vermieden werden.Theoretisch hat LinkedList ein O (1) für die
add(E element)
Auch das Hinzufügen eines Elements in der Mitte einer Liste sollte sehr effizient sein.
Die Praxis ist sehr unterschiedlich, da LinkedList eine Cache Hostile Data-Struktur ist. Vom Leistungs-POV - es gibt sehr wenige Fälle, in denen
LinkedList
eine bessere Leistung erzielt werden könnte als im Cache-BereichArrayList
.Hier sind die Ergebnisse eines Benchmark-Tests zum Einfügen von Elementen an zufälligen Stellen. Wie Sie sehen können, ist die Array-Liste viel effizienter, obwohl theoretisch für jede Einfügung in der Mitte der Liste die n späteren Elemente des Arrays "verschoben" werden müssen (niedrigere Werte sind besser):
Arbeiten an einer Hardware der späteren Generation (größere, effizientere Caches) - die Ergebnisse sind noch schlüssiger:
LinkedList benötigt viel mehr Zeit, um denselben Job auszuführen. Quell- Quellcode
Dafür gibt es zwei Hauptgründe:
Hauptsächlich - dass die Knoten der
LinkedList
zufällig über den Speicher verteilt sind. RAM ("Random Access Memory") ist nicht wirklich zufällig und Speicherblöcke müssen in den Cache abgerufen werden. Dieser Vorgang braucht Zeit, und wenn solche Abrufe häufig auftreten - die Speicherseiten im Cache müssen ständig ersetzt werden -> Cache-Fehler -> Cache ist nicht effizient.ArrayList
Elemente werden im kontinuierlichen Speicher gespeichert - genau dafür optimiert die moderne CPU-Architektur.Sekundär
LinkedList
erforderlich, um Rückwärts- / Vorwärtszeiger zu halten, was das Dreifache des Speicherverbrauchs pro gespeichertem Wert im Vergleich zu bedeutetArrayList
.DynamicIntArray ist übrigens eine benutzerdefinierte ArrayList-Implementierung, die
Int
(primitiver Typ) und keine Objekte enthält - daher werden alle Daten wirklich nebeneinander gespeichert - und damit noch effizienter.Ein Schlüsselelement, an das man sich erinnern sollte, ist, dass die Kosten für das Abrufen eines Speicherblocks bedeutender sind als die Kosten für den Zugriff auf eine einzelne Speicherzelle. Aus diesem Grund ist 1 MB sequentieller Speicher des Lesers bis zu 400-mal schneller als das Lesen dieser Datenmenge aus verschiedenen Speicherblöcken:
Quelle: Latenzzahlen, die jeder Programmierer kennen sollte
Um den Punkt noch deutlicher zu machen, überprüfen Sie bitte den Benchmark für das Hinzufügen von Elementen am Anfang der Liste. Dies ist ein Anwendungsfall, bei dem theoretisch das
LinkedList
wirklich glänzen sollte undArrayList
schlechte oder sogar schlechtere Ergebnisse liefern sollte:Hinweis: Dies ist ein Benchmark der C ++ Std lib, aber meine bisherigen Erfahrungen haben gezeigt, dass die C ++ - und Java-Ergebnisse sehr ähnlich sind. Quellcode
Eine sequentielle Massenspeicher Kopieren ist eine Operation , die durch die moderne CPUs optimiert - Theorie verändert und tatsächlich machen, wieder
ArrayList
/Vector
viel effizienterCredits: Alle hier veröffentlichten Benchmarks wurden von Kjell Hedström erstellt . Noch mehr Daten finden Sie in seinem Blog
quelle
Wenn Ihr Code
add(0)
und hatremove(0)
, verwenden Sie einLinkedList
und es ist schöneraddFirst()
undremoveFirst()
Methoden. Andernfalls verwenden SieArrayList
.Und natürlich Guava ‚s ImmutableList ist dein bester Freund.
quelle
Ich weiß, dass dies ein alter Beitrag ist, aber ich kann ehrlich gesagt nicht glauben, dass niemand erwähnt hat, dass dies
LinkedList
implementiert wirdDeque
. Schauen Sie sich einfach die Methoden inDeque
(undQueue
) an. wenn Sie einen fairen Vergleich wollen, versuchen Sie laufenLinkedList
gegenArrayDeque
und ein Feature-for-Feature Vergleich zu tun.quelle
Hier ist die Big-O - Notation in beide
ArrayList
undLinkedList
auchCopyOnWrite-ArrayList
:Anordnungsliste
LinkedList
CopyOnWrite-ArrayList
Basierend auf diesen müssen Sie entscheiden, was Sie wählen möchten. :) :)
quelle
LinkedList.add()
auch nicht der Fall, obwohl die meisten Antworten hier dies aussagen.Vergleichen wir LinkedList und ArrayList anhand der folgenden Parameter:
1. Implementierung
2. Leistung
get (int index) oder Suchoperation
Der Grund für Arraylist ist schneller als VerketteteListe ist , dass Array einen Index basiertes System für seine Elemente verwendet , da sie eine Array - Datenstruktur intern verwendet, auf der anderen Seite,
LinkedList bietet keinen indexbasierten Zugriff für seine Elemente, da es entweder vom Anfang oder vom Ende (je nachdem, welcher Wert näher liegt) iteriert, um den Knoten am angegebenen Elementindex abzurufen.
Einfügen () oder Hinzufügen (Objekt)
(int) Operation entfernen
Die Entfernungsoperation in LinkedList ist im Allgemeinen dieselbe wie in ArrayList, dh O (n).
3. Iterator umkehren
4. Anfangskapazität
5. Speicher-Overhead
Quelle
quelle
Normalerweise verwende ich eine über der anderen, basierend auf der zeitlichen Komplexität der Operationen, die ich für diese bestimmte Liste ausführen würde.
quelle
Zusätzlich zu den anderen oben genannten guten Argumenten sollten Sie die
ArrayList
ImplementierungsschnittstelleRandomAccess
und dieLinkedList
Implementierungsschnittstelle beachtenQueue
.Irgendwie sprechen sie leicht unterschiedliche Probleme an, mit Unterschieden in Effizienz und Verhalten (siehe ihre Liste der Methoden).
quelle
Dies hängt davon ab, welche Vorgänge Sie in der Liste ausführen werden.
ArrayList
ist schneller, um auf einen indizierten Wert zuzugreifen. Es ist viel schlimmer beim Einfügen oder Löschen von Objekten.Um mehr zu erfahren, lesen Sie jeden Artikel, der über den Unterschied zwischen Arrays und verknüpften Listen spricht.
quelle
Eine Array-Liste ist im Wesentlichen ein Array mit Methoden zum Hinzufügen von Elementen usw. (und Sie sollten stattdessen eine generische Liste verwenden). Es ist eine Sammlung von Elementen, auf die über einen Indexer zugegriffen werden kann (z. B. [0]). Dies impliziert einen Fortschritt von einem Gegenstand zum nächsten.
Eine verknüpfte Liste gibt einen Fortschritt von einem Element zum nächsten an (Element a -> Element b). Sie können den gleichen Effekt mit einer Array-Liste erzielen, aber eine verknüpfte Liste gibt absolut an, welches Element dem vorherigen folgen soll.
quelle
Siehe die Java-Tutorials - Implementierungen auflisten .
quelle
Ein wichtiges Merkmal einer verknüpften Liste (die ich in einer anderen Antwort nicht gelesen habe) ist die Verkettung von zwei Listen. Bei einem Array ist dies O (n) (+ Overhead einiger Neuzuweisungen) mit einer verknüpften Liste ist dies nur O (1) oder O (2) ;-)
Wichtig : Für Java ist
LinkedList
dies nicht wahr! Siehe Gibt es eine schnelle Concat-Methode für verknüpfte Listen in Java?quelle
next
von einer Liste auf den ersten Knoten in der zweiten Liste verweisen . Die einzige Möglichkeit besteht darin,addAll()
Elemente nacheinander hinzuzufügen, obwohl dies besser ist, alsadd()
jedes Element zu durchlaufen und aufzurufen . Um dies in O (1) schnell zu erledigen, benötigen Sie eine Compositing-Klasse (wie org.apache.commons.collections.collection.CompositeCollection), die dann jedoch für jede Art von Liste / Sammlung funktioniert.ArrayList und LinkedList haben ihre eigenen Vor- und Nachteile.
ArrayList verwendet eine zusammenhängende Speicheradresse im Vergleich zu LinkedList, die Zeiger auf den nächsten Knoten verwendet. Wenn Sie also ein Element in einer ArrayList nachschlagen möchten, ist dies schneller als n Iterationen mit LinkedList durchzuführen.
Andererseits ist das Einfügen und Löschen in eine LinkedList viel einfacher, da Sie nur die Zeiger ändern müssen, während eine ArrayList die Verwendung von Verschiebungsoperationen für das Einfügen oder Löschen impliziert.
Wenn Ihre App häufig abgerufen wird, verwenden Sie eine ArrayList. Wenn Sie häufig einfügen und löschen, verwenden Sie eine LinkedList.
quelle
Ich habe die Antworten gelesen, aber es gibt ein Szenario, in dem ich immer eine LinkedList über einer ArrayList verwende, die ich teilen möchte, um Meinungen zu hören:
Jedes Mal, wenn ich eine Methode hatte, die eine Liste von Daten zurückgibt, die aus einer Datenbank stammen, verwende ich immer eine LinkedList.
Meine Begründung war, dass, da es unmöglich ist, genau zu wissen, wie viele Ergebnisse ich erhalte, kein Speicher verschwendet wird (wie in ArrayList mit dem Unterschied zwischen der Kapazität und der tatsächlichen Anzahl von Elementen), und es keine Zeitverschwendung geben würde, dies zu versuchen Duplizieren Sie die Kapazität.
In Bezug auf eine ArrayList stimme ich zu, dass Sie zumindest immer den Konstruktor mit der anfänglichen Kapazität verwenden sollten, um die Duplizierung der Arrays so gering wie möglich zu halten.
quelle
ArrayList
undLinkedList
beide GeräteList interface
und ihre Methoden und Ergebnisse sind nahezu identisch. Es gibt jedoch nur wenige Unterschiede zwischen ihnen, die je nach Anforderung einen Unterschied gegenüber dem anderen machen.ArrayList Vs LinkedList
1) Der
Search:
ArrayList
Suchvorgang ist im Vergleich zum Suchvorgang ziemlich schnellLinkedList
.get(int index)
inArrayList
gibt die Leistung vonO(1)
währendLinkedList
Leistung istO(n)
.Reason:
ArrayList
Das indexbasierte System für seine Elemente wird beibehalten, da implizit die Array-Datenstruktur verwendet wird, wodurch die Suche nach einem Element in der Liste beschleunigt wird. Auf der anderen Seite wirdLinkedList
eine doppelt verknüpfte Liste implementiert, bei der alle Elemente zum Durchsuchen eines Elements durchlaufen werden müssen.2)
Deletion:
LinkedList
Entfernen entfernen gibtO(1)
Leistung, währendArrayList
variable Leistung gibt:O(n)
im schlimmsten Fall (beim Entfernen des ersten Elements) undO(1)
im besten Fall (beim Entfernen des letzten Elements).Grund: Jedes Element von LinkedList verwaltet zwei Zeiger (Adressen), die auf die beiden Nachbarelemente in der Liste verweisen. Daher erfordert das Entfernen nur eine Änderung der Zeigerposition in den beiden Nachbarknoten (Elementen) des Knotens, der entfernt werden soll. In ArrayList müssen alle Elemente verschoben werden, um den durch das entfernte Element erstellten Platz auszufüllen.
3)
Inserts Performance:
LinkedList
add - Methode gibt dieO(1)
Leistung währendArrayList
gibtO(n)
im schlimmsten Fall. Der Grund ist der gleiche wie für das Entfernen erläutert.4)
Memory Overhead:
ArrayList
verwaltet Indizes und Elementdaten, währendLinkedList
Elementdaten und zwei Zeiger für Nachbarknoten verwaltet werdenEs gibt nur wenige Ähnlichkeiten zwischen diesen Klassen:
iterator
undlistIterator
von diesen Klassen zurückgegeben werdenfail-fast
(wenn die Liste zu irgendeinem Zeitpunkt nach dem Erstellen des Iterators strukturell geändert wird, außer durch dieiterator’s
eigenen Methoden zum Entfernen oder Hinzufügen, wird der Iteratorthrow
aConcurrentModificationException
).Wann wird LinkedList und wann ArrayList verwendet?
(O(1))
imLinkedList
Vergleich zu eine gute LeistungArrayList(O(n))
.get method
) -Operationen sind schnell in,Arraylist (O(1))
aber nicht inLinkedList (O(n))
quelle
Die Operation get (i) in ArrayList ist schneller als LinkedList, weil:
ArrayList: Implementierung der List-Schnittstelle durch ein
skalierbares Array LinkedList: Doppelt verknüpfte Listenimplementierung der List- und Deque-Schnittstellen
Operationen, die in die Liste indizieren, durchlaufen die Liste vom Anfang oder vom Ende, je nachdem, welcher Wert näher am angegebenen Index liegt.
quelle
1) Grundlegende Datenstruktur
Der erste Unterschied zwischen ArrayList und LinkedList besteht darin, dass ArrayList von Array unterstützt wird, während LinkedList von LinkedList unterstützt wird. Dies führt zu weiteren Leistungsunterschieden.
2) LinkedList implementiert Deque
Ein weiterer Unterschied zwischen ArrayList und LinkedList besteht darin, dass LinkedList neben der List-Schnittstelle auch die Deque-Schnittstelle implementiert, die First-In-First-Out-Operationen für add () und poll () sowie mehrere andere Deque-Funktionen bereitstellt. 3) Hinzufügen von Elementen in ArrayList Das Hinzufügen von Elementen in ArrayList ist eine O (1) -Operation, wenn es keine Größenänderung des Arrays auslöst. In diesem Fall wird es zu O (log (n)). Andererseits wird ein Element in angehängt LinkedList ist eine O (1) -Operation, da keine Navigation erforderlich ist.
4) Entfernen eines Elements aus einer Position
Um ein Element aus einem bestimmten Index zu entfernen, z. B. durch Aufrufen von remove (index), führt ArrayList eine Kopieroperation aus, die es nahe an O (n) bringt, während LinkedList zu dem Punkt gehen muss, der es auch zu O (n / 2) macht. , da es je nach Nähe aus beiden Richtungen durchqueren kann.
5) Iterieren über ArrayList oder LinkedList
Iteration ist die O (n) -Operation für LinkedList und ArrayList, wobei n eine Nummer eines Elements ist.
6) Element von einer Position abrufen
Die get (index) -Operation ist O (1) in ArrayList, während O (n / 2) in LinkedList ist, da sie bis zu diesem Eintrag durchlaufen muss. In der Big O-Notation ist O (n / 2) jedoch nur O (n), da wir dort Konstanten ignorieren.
7) Speicher
LinkedList verwendet das Wrapper-Objekt Entry, eine statisch verschachtelte Klasse zum Speichern von Daten und zwei Knoten neben und vor, während ArrayList nur Daten in Array speichert.
Daher scheint der Speicherbedarf bei ArrayList geringer zu sein als bei LinkedList, außer in dem Fall, in dem Array die Größenänderung ausführt, wenn es Inhalte von einem Array in ein anderes kopiert.
Wenn das Array groß genug ist, kann es zu diesem Zeitpunkt viel Speicher beanspruchen und die Garbage Collection auslösen, was die Antwortzeit verlangsamen kann.
Aufgrund der oben genannten Unterschiede zwischen ArrayList und LinkedList ist ArrayList in fast allen Fällen die bessere Wahl als LinkedList, es sei denn, Sie führen häufig add () aus als remove () oder get ().
Es ist einfacher, eine verknüpfte Liste als ArrayList zu ändern, insbesondere wenn Sie Elemente vom Anfang oder Ende hinzufügen oder entfernen, da die verknüpfte Liste intern Verweise auf diese Positionen enthält und in O (1) -Zeit verfügbar ist.
Mit anderen Worten, Sie müssen die verknüpfte Liste nicht durchlaufen, um die Position zu erreichen, an der Sie Elemente hinzufügen möchten. In diesem Fall wird das Hinzufügen zur O (n) -Operation. Beispiel: Einfügen oder Löschen eines Elements in der Mitte einer verknüpften Liste.
Verwenden Sie meiner Meinung nach ArrayList über LinkedList für die meisten praktischen Zwecke in Java.
quelle
Einer der Tests, die ich hier gesehen habe, führt den Test nur einmal durch. Was mir jedoch aufgefallen ist, ist, dass Sie diese Tests viele Male ausführen müssen und ihre Zeiten schließlich konvergieren werden. Grundsätzlich muss sich die JVM aufwärmen. Für meinen speziellen Anwendungsfall musste ich Elemente zu einer Liste hinzufügen / entfernen, die auf ungefähr 500 Elemente anwächst. In meinen Tests
LinkedList
kam schneller heraus, mitLinkedList
ungefähr 50.000 NS undArrayList
ungefähr 90.000 NS ... Geben oder Nehmen. Siehe den Code unten.quelle
Sowohl remove () als auch insert () haben eine Laufzeiteffizienz von O (n) für ArrayLists und LinkedLists. Der Grund für die lineare Verarbeitungszeit liegt jedoch in zwei sehr unterschiedlichen Gründen:
In einer ArrayList gelangen Sie zu dem Element in O (1), aber wenn Sie etwas entfernen oder einfügen, wird es zu O (n), da alle folgenden Elemente geändert werden müssen.
In einer LinkedList ist O (n) erforderlich, um tatsächlich zum gewünschten Element zu gelangen, da wir ganz am Anfang beginnen müssen, bis wir den gewünschten Index erreichen. Das tatsächliche Entfernen oder Einfügen ist konstant, da nur 1 Referenz für remove () und 2 Referenzen für insert () geändert werden müssen.
Welche der beiden Methoden zum Einsetzen und Entfernen schneller ist, hängt davon ab, wo dies geschieht. Wenn wir näher am Anfang sind, wird die LinkedList schneller sein, da wir relativ wenige Elemente durchlaufen müssen. Wenn wir uns dem Ende nähern, ist eine ArrayList schneller, da wir in konstanter Zeit dort ankommen und nur die wenigen verbleibenden Elemente ändern müssen, die darauf folgen. Wenn genau in der Mitte ausgeführt, ist die LinkedList schneller, da das Durchlaufen von n Elementen schneller ist als das Verschieben von n Werten.
Bonus: Während es keine Möglichkeit gibt, diese beiden Methoden O (1) für eine ArrayList zu erstellen, gibt es in LinkedLists tatsächlich eine Möglichkeit, dies zu tun. Angenommen, wir möchten die gesamte Liste durchgehen und dabei Elemente entfernen und einfügen. Normalerweise würden Sie für jedes Element mit der LinkedList von vorne beginnen. Wir könnten auch das aktuelle Element, an dem wir arbeiten, mit einem Iterator "speichern". Mit Hilfe des Iterators erhalten wir eine O (1) -Effizienz für remove () und insert (), wenn wir in einer LinkedList arbeiten. Ich bin mir bewusst, dass eine LinkedList immer besser ist als eine ArrayList.
quelle
ArrayList erweitert AbstractList und implementiert die List Interface. ArrayList ist ein dynamisches Array.
Man kann sagen, dass es im Grunde genommen erstellt wurde, um die Nachteile von Arrays zu überwinden.
Die LinkedList-Klasse erweitert AbstractSequentialList und implementiert die List-, Deque- und Queue-Schnittstelle.
Leistung
arraylist.get()
ist O (1), wohingegenlinkedlist.get()
O (n)arraylist.add()
O (1) ist undlinkedlist.add()
0 (1)arraylist.contains()
O (n) ist undlinkedlist.contains()
O (n)arraylist.next()
O (1) ist undlinkedlist.next()
O (1)arraylist.remove()
O (n) ist wohingegenlinkedlist.remove()
O (1)in der Arrayliste
iterator.remove()
O (n) ist,während in der verknüpften Liste
iterator.remove()
O (1) istquelle