Wann sollte man LinkedList statt ArrayList in Java verwenden?

Question

Ich war schon immer jemand, der einfach nur benutzt:

List<String> names = new ArrayList<>();

Ich verwende die Schnittstelle als Typname für Tragbarkeit damit ich, wenn ich Fragen wie diese stelle, meinen Code überarbeiten kann.

Wann sollte LinkedList verwendet werden über ArrayList und andersherum?

Answer 1

Zusammenfassung ArrayList con ArrayDeque sind vorzuziehen in viele mehr Anwendungsfälle als LinkedList . Wenn Sie sich nicht sicher sind - beginnen Sie einfach mit ArrayList .

---

TLDR, in ArrayList Zugriff auf ein Element dauert konstante Zeit [O(1)] und Hinzufügen eines Elements dauert O(n) Zeit [worst case]. In LinkedList dauert das Hinzufügen eines Elements O(n) Zeit und der Zugriff dauert auch O(n) Zeit, aber LinkedList verwendet mehr Speicher als ArrayList.

LinkedList y ArrayList sind zwei verschiedene Implementierungen der Schnittstelle List. LinkedList setzt sie mit einer doppelt verknüpften Liste um. ArrayList implementiert es mit einem Array, dessen Größe sich dynamisch ändert.

Wie bei standardmäßigen verknüpften Listen- und Array-Operationen haben die verschiedenen Methoden unterschiedliche algorithmische Laufzeiten.

Für LinkedList<E>

• get(int index) でございます O(n) (mit n/4 Schritte im Durchschnitt), aber O(1) wenn index = 0 o index = list.size() - 1 (in diesem Fall können Sie auch getFirst() y getLast() ). Einer der wichtigsten Vorteile von LinkedList<E>
• add(int index, E element) でございます O(n) (mit n/4 Schritte im Durchschnitt), aber O(1) wenn index = 0 o index = list.size() - 1 (in diesem Fall können Sie auch addFirst() y addLast() / add() ). Einer der wichtigsten Vorteile von LinkedList<E>
• remove(int index) でございます O(n) (mit n/4 Schritte im Durchschnitt), aber O(1) wenn index = 0 o index = list.size() - 1 (in diesem Fall können Sie auch removeFirst() y removeLast() ). Einer der wichtigsten Vorteile von LinkedList<E>
• Iterator.remove() でございます O(1) . Einer der wichtigsten Vorteile von LinkedList<E>
• ListIterator.add(E element) でございます O(1) . Einer der wichtigsten Vorteile von LinkedList<E>

Hinweis: Viele der Vorgänge erfordern n/4 Schritte im Durchschnitt, Konstante Anzahl der Schritte im günstigsten Fall (z. B. Index = 0), und n/2 Schritte im schlimmsten Fall (Mitte der Liste)

Für ArrayList<E>

• get(int index) でございます O(1) . Hauptnutzen von ArrayList<E>
• add(E element) でございます O(1) abgeschrieben, aber O(n) Schlimmster Fall, da die Größe des Arrays geändert und kopiert werden muss
• add(int index, E element) でございます O(n) (mit n/2 Schritte im Durchschnitt)
• remove(int index) でございます O(n) (mit n/2 Schritte im Durchschnitt)
• Iterator.remove() でございます O(n) (mit n/2 Schritte im Durchschnitt)
• ListIterator.add(E element) でございます O(n) (mit n/2 Schritte im Durchschnitt)

Hinweis: Viele der Vorgänge erfordern n/2 Schritte im Durchschnitt, Konstante Anzahl der Schritte im besten Fall (Ende der Liste), n Schritte im schlimmsten Fall (Anfang der Liste)

LinkedList<E> ermöglicht ein zeitlich konstantes Einfügen oder Entfernen Verwendung von Iteratoren sondern nur der sequentielle Zugriff auf die Elemente. Mit anderen Worten: Sie können die Liste vorwärts oder rückwärts durchlaufen, aber das Auffinden einer Position in der Liste nimmt Zeit in Anspruch, die proportional zur Größe der Liste ist. Javadoc sagt "Operationen, die in die Liste indexieren, durchlaufen die Liste vom Anfang oder vom Ende aus, je nachdem, was näher ist. Diese Methoden sind also O(n) ( n/4 Schritte) im Durchschnitt, obwohl O(1) für index = 0 .

ArrayList<E> ermöglichen dagegen einen schnellen Lesezugriff nach dem Zufallsprinzip, so dass Sie jedes Element in konstanter Zeit erfassen können. Das Hinzufügen oder Entfernen von Elementen, die sich nicht am Ende befinden, erfordert jedoch, dass alle anderen Elemente verschoben werden, um entweder eine Öffnung zu schaffen oder die Lücke zu füllen. Wenn Sie mehr Elemente hinzufügen, als das zugrunde liegende Array fassen kann, wird ein neues Array (mit der 1,5-fachen Größe) angelegt und das alte Array in das neue kopiert. ArrayList でございます O(n) im ungünstigsten Fall, aber im Durchschnitt konstant.

Je nachdem, was Sie vorhaben, sollten Sie also die entsprechenden Implementierungen wählen. Das Iterieren über beide Arten von Listen ist praktisch gleich billig. (Das Iterieren über eine ArrayList ist technisch gesehen schneller, aber wenn Sie nicht gerade etwas wirklich Leistungssensitives machen, sollten Sie sich darüber keine Gedanken machen - es sind beides Konstanten).

Die wichtigsten Vorteile der Verwendung eines LinkedList entstehen, wenn Sie vorhandene Iteratoren zum Einfügen und Entfernen von Elementen wiederverwenden. Diese Operationen können dann in O(1) indem Sie die Liste nur lokal ändern. In einer Array-Liste muss der Rest des Arrays umgezogen (d.h. kopiert). Auf der anderen Seite, die Suche in einem LinkedList bedeutet, dass Sie den Links in O(n) ( n/2 Schritte) für den schlimmsten Fall, während in einem ArrayList kann die gewünschte Position mathematisch berechnet und in O(1) .

Ein weiterer Vorteil der Verwendung eines LinkedList entsteht, wenn Sie am Kopf der Liste etwas hinzufügen oder entfernen, da diese Operationen O(1) während sie O(n) für ArrayList . Beachten Sie, dass ArrayDeque kann eine gute Alternative sein zu LinkedList zum Hinzufügen und Entfernen aus dem Kopf, aber es ist keine List .

Wenn Sie große Listen haben, sollten Sie außerdem bedenken, dass der Speicherverbrauch ebenfalls unterschiedlich ist. Jedes Element einer LinkedList hat mehr Overhead, da auch Zeiger auf das nächste und vorherige Element gespeichert werden. ArrayLists haben diesen Aufwand nicht. Wie auch immer, ArrayLists nehmen so viel Speicherplatz ein, wie für die Kapazität zugewiesen ist, unabhängig davon, ob tatsächlich Elemente hinzugefügt wurden.

Die Standard-Anfangskapazität eines ArrayList ist ziemlich klein (10 von Java 1.4 - 1.8). Da die zugrunde liegende Implementierung aber ein Array ist, muss die Größe des Arrays angepasst werden, wenn Sie viele Elemente hinzufügen. Um die hohen Kosten für die Größenanpassung zu vermeiden, wenn Sie wissen, dass Sie eine Menge Elemente hinzufügen werden, konstruieren Sie die ArrayList mit einer höheren Anfangskapazität.

Wenn man die beiden Strukturen aus der Perspektive der Datenstrukturen betrachtet, ist eine LinkedList im Grunde eine sequentielle Datenstruktur, die einen Kopfknoten enthält. Der Knoten ist eine Hülle für zwei Komponenten: einen Wert vom Typ T [durch Generika akzeptiert] und einen weiteren Verweis auf den mit ihm verknüpften Knoten. Wir können also behaupten, dass es sich um eine rekursive Datenstruktur handelt (ein Knoten enthält einen anderen Knoten, der wiederum einen anderen Knoten enthält und so weiter...). Das Hinzufügen von Elementen dauert in LinkedList wie oben beschrieben linear.

Eine ArrayList ist ein erweiterbares Array. Es ist genau wie ein normales Array. Wenn ein Element hinzugefügt wird und die ArrayList bereits voll ist, wird ein weiteres Array mit einer Größe erstellt, die größer als die vorherige Größe ist. Die Elemente werden dann aus dem vorherigen Array in das neue Array kopiert und die hinzuzufügenden Elemente werden ebenfalls an den angegebenen Indizes platziert.

Answer 2

Bisher scheint sich noch niemand mit dem Speicherbedarf jeder dieser Listen befasst zu haben, abgesehen von dem allgemeinen Konsens, dass eine LinkedList ist "viel mehr" als ein ArrayList also habe ich einige Zahlen berechnet, um genau zu zeigen, wie viel beide Listen für N Null-Referenzen benötigen.

Da Referenzen entweder 32 oder 64 Bit (auch wenn sie Null sind) auf ihren jeweiligen Systemen sind, habe ich 4 Datensätze für 32 und 64 Bit aufgenommen LinkedLists y ArrayLists .

Anmerkung: Die angegebenen Größen für die ArrayList Zeilen sind für gekürzte Listen - In der Praxis ist die Kapazität des Backing Arrays in einer ArrayList ist in der Regel größer als seine aktuelle Elementanzahl.

Anmerkung 2: (dank BeeOnRope) Da CompressedOops ab Mitte JDK6 standardmäßig eingestellt ist, entsprechen die unten angegebenen Werte für 64-Bit-Maschinen im Wesentlichen ihren 32-Bit-Gegenstücken, es sei denn, Sie schalten sie ausdrücklich aus.

---

---

Das Ergebnis zeigt deutlich, dass LinkedList ist sehr viel mehr als ArrayList insbesondere mit einer sehr hohen Anzahl von Elementen. Wenn der Speicher ein Faktor ist, sollten Sie sich von LinkedLists .

Die Formeln, die ich verwendet habe, folgen. Lassen Sie mich wissen, wenn ich etwas falsch gemacht habe, und ich werde es in Ordnung bringen. b" ist entweder 4 oder 8 für 32- oder 64-Bit-Systeme, und "n" ist die Anzahl der Elemente. Der Grund für die Mods ist, dass alle Objekte in Java ein Vielfaches von 8 Bytes Platz benötigen, unabhängig davon, ob sie alle verwendet werden oder nicht.

ArrayList:

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)

Answer 3

ArrayList ist das, was Sie wollen. LinkedList ist fast immer ein (Leistungs-)Fehler.

Warum LinkedList ist scheiße:

• Sie verwendet viele kleine Speicherobjekte und beeinträchtigt daher die Leistung des gesamten Prozesses.
• Viele kleine Objekte sind schlecht für die Cache-Lokalität.
• Jede indizierte Operation erfordert ein Traversal, d.h. sie ist O(n) leistungsfähig. Dies ist im Quellcode nicht offensichtlich und führt zu Algorithmen, die O(n) langsamer sind, als wenn ArrayList verwendet wurde.
• Eine gute Leistung zu erzielen ist schwierig.
• Selbst wenn die Big-O-Leistung die gleiche ist wie ArrayList wird sie wahrscheinlich ohnehin deutlich langsamer sein.
• Es ist erschütternd zu sehen LinkedList in der Quelle, weil es wahrscheinlich die falsche Wahl ist.

Answer 4

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)

Algorithmen: Big-Oh-Notation (archiviert)

ArrayLists sind gut für write-once-read-many oder appenders, aber schlecht auf add/remove von vorne oder Mitte.

Answer 5

Joshua Bloch, der Autor von LinkedList:

Verwendet eigentlich jemand LinkedList? Ich habe sie geschrieben und benutze sie nie.

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 am selbsterklärendsten, wenn auch nicht aufschlussreich.