Frage Wann wird LinkedList über ArrayList verwendet?


Ich war immer einer, der einfach benutzt wurde:

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

Ich benutze die Schnittstelle als den Typnamen für Portabilität, so dass ich meinen Code nachbearbeiten kann, wenn ich Fragen wie diese stelle.

Wann sollte LinkedList über verwendet werden ArrayList und umgekehrt?


2565
2017-11-27 01:36


Ursprung


Antworten:


Zusammenfassung  ArrayList mit ArrayDeque sind bevorzugt in viel mehr Anwendungsfälle als LinkedList. Nicht sicher - fang einfach an ArrayList.


LinkedList und ArrayList sind zwei verschiedene Implementierungen der List-Schnittstelle. LinkedList implementiert es mit einer doppelt verknüpften Liste. ArrayList implementiert es mit einem dynamisch neu dimensionierten Array.

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

Zum LinkedList<E>

  • get(int index) ist Auf) (mit n / 4 Schritte im Durchschnitt)
  • add(E element) ist O (1)
  • add(int index, E element) ist Auf) (mit n / 4 Schritte im Durchschnitt), aber O (1) wann index = 0  <--- Hauptvorteil von LinkedList<E>
  • remove(int index) ist Auf) (mit n / 4 Schritte im Durchschnitt)
  • Iterator.remove() ist O (1). <--- Hauptvorteil von LinkedList<E>
  • ListIterator.add(E element) ist O (1)  Dies ist einer der Hauptvorteile von LinkedList<E>

Hinweis: Viele der Operationen benötigen n / 4 Schritte im Durchschnitt, Konstante Anzahl der Schritte im besten Fall (z.B. Index = 0) und n / 2 Schritte im schlimmsten Fall (Mitte der Liste)

Zum ArrayList<E>

  • get(int index) ist O (1)  <--- Hauptvorteil von ArrayList<E>
  • add(E element) ist O (1) amortisiert, aber Auf) Worst-Case, da das Array in der Größe geändert und kopiert werden muss
  • add(int index, E element) ist Auf) (mit n / 2 Schritte im Durchschnitt)
  • remove(int index) ist Auf) (mit n / 2 Schritte im Durchschnitt)
  • Iterator.remove() ist Auf) (mit n / 2 Schritte im Durchschnitt)
  • ListIterator.add(E element) ist Auf) (mit n / 2 Schritte im Durchschnitt)

Hinweis: Viele der Operationen benötigen n / 2 Schritte im Durchschnitt, Konstante Anzahl der Schritte im besten Fall (Ende der Liste), n Schritte im schlimmsten Fall (Listenanfang)

LinkedList<E> ermöglicht das Einfügen oder Entfernen von konstanten Zeiten Verwenden von Iteratoren, aber nur sequentiellen Zugriff von Elementen. Mit anderen Worten, Sie können die Liste vorwärts oder rückwärts durchlaufen, aber das Finden einer Position in der Liste dauert proportional zur Größe der Liste. Javadoc sagt "Operationen, die sich in der Liste befinden, durchlaufen die Liste vom Anfang oder vom Ende, je nachdem, was näher ist", so sind diese Methoden Auf) (n / 4 Schritte) im Durchschnitt, obwohl O (1) zum index = 0.

ArrayList<E>Auf der anderen Seite, erlauben Sie schnellen wahlfreien Lesezugriff, so dass Sie jedes Element in konstanter Zeit greifen können. Aber das Hinzufügen oder Entfernen von einer beliebigen Stelle außer dem Ende erfordert das Verschieben aller letzteren Elemente, um entweder eine Öffnung zu erzeugen oder die Lücke zu füllen. Wenn Sie außerdem mehr Elemente hinzufügen als die Kapazität des zugrunde liegenden Arrays, wird ein neues Array (1,5 mal so groß) zugewiesen, und das alte Array wird in das neue Array kopiert ArrayList ist Auf) im schlimmsten Fall aber im Durchschnitt konstant.

Je nachdem, welche Operationen Sie durchführen möchten, sollten Sie die Implementierungen entsprechend auswählen. Das Iterieren über jede Art von Liste ist praktisch gleich billig. (Iteriert über ein ArrayList ist technisch schneller, aber wenn Sie nicht wirklich leistungsabhängig sind, sollten Sie sich keine Gedanken darüber machen - sie sind beide Konstanten.

Die wichtigsten Vorteile von a LinkedList Wenn Sie vorhandene Iteratoren zum Einfügen und Entfernen von Elementen erneut verwenden. Diese Operationen können dann in ausgeführt werden O (1) indem Sie die Liste nur lokal ändern. In einer Array-Liste muss der Rest des Arrays sein gerührt (d. h. kopiert) Auf der anderen Seite suchen in einem LinkedList bedeutet, den Links in folgen Auf) (n / 2 Schritte) für den schlimmsten Fall, während in einem ArrayList Die gewünschte Position kann rechnerisch berechnet und abgerufen werden O (1).

Ein weiterer Vorteil der Verwendung eines LinkedList entstehen, wenn Sie am Kopf der Liste hinzufügen oder entfernen, da diese Operationen sind O (1)während sie sind Auf) zum ArrayList. Beachten Sie, dass ArrayDeque kann eine gute Alternative sein LinkedList zum Hinzufügen und Entfernen vom Kopf, aber es ist kein List.

Beachten Sie bei großen Listen auch, dass die Speicherbelegung ebenfalls unterschiedlich ist. Jedes Element von a LinkedList hat mehr Overhead, da Zeiger auf die nächsten und vorherigen Elemente ebenfalls gespeichert werden. ArrayLists hab diesen Overhead nicht. Jedoch, ArrayLists nehmen Sie so viel Speicher in Anspruch, wie für die Kapazität reserviert ist, unabhängig davon, ob Elemente tatsächlich hinzugefügt wurden.

Die standardmäßige Anfangskapazität von a ArrayList ist ziemlich klein (10 von Java 1.4 - 1.8). Da die zugrunde liegende Implementierung ein Array ist, muss die Größe des Arrays geändert werden, wenn Sie viele Elemente hinzufügen. Um die hohen Kosten der Größenänderung zu vermeiden, wenn Sie wissen, dass Sie viele Elemente hinzufügen, konstruieren Sie die ArrayList mit einer höheren Anfangskapazität.


2845
2017-10-06 06:46



Bislang scheint niemand den Speicherabdruck jeder dieser Listen außer dem allgemeinen Konsens, dass a LinkedList ist "viel mehr" als ein ArrayList Also habe ich ein paar Zahlen gemacht, um genau zu zeigen, wie viel beide Listen für N Null-Referenzen benötigen.

Da die Referenzen entweder 32 oder 64 Bits (selbst wenn Null) auf ihren relativen Systemen sind, habe ich 4 Sätze von Daten für 32 und 64 Bit enthalten LinkedLists und ArrayLists.

Hinweis: Die Größen für die ArrayList Linien sind für getrimmte Listen - In der Praxis ist die Kapazität des Backing-Arrays in einem ArrayList ist in der Regel größer als die aktuelle Elementanzahl.

Anmerkung 2:  (Danke BeeOnRope) Da CompressedOops ab der Mitte von JDK6 standardmäßig eingestellt ist, stimmen die unten angegebenen Werte für 64-Bit-Maschinen im Allgemeinen mit ihren 32-Bit-Gegenstücken überein, es sei denn, Sie deaktivieren sie ausdrücklich.


Graph of LinkedList and ArrayList No. of Elements x Bytes


Das Ergebnis zeigt dies deutlich LinkedList ist eine ganze Menge mehr als ArrayListbesonders mit einer sehr hohen Elementzahl. Wenn die Erinnerung ein Faktor ist, sollten Sie Abstand halten von LinkedLists.

Die Formeln, die ich verwendet habe, 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 liegt, dass alle Objekte in Java ein Vielfaches von 8 Byte Platz einnehmen, 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)

534
2017-11-27 14:20



ArrayList ist was du willst. LinkedList ist fast immer ein (Leistungs-) Fehler.

Warum LinkedList saugt:

  • Es verwendet viele kleine Speicherobjekte und wirkt sich daher auf die Leistung im gesamten Prozess aus.
  • Viele kleine Objekte sind schlecht für Cache-Lokalität.
  • Jede indizierte Operation erfordert eine Traversierung, d. H. Eine O (n) -Leistung. Dies ist im Quellcode nicht offensichtlich, was dazu führt, dass Algorithmen O (n) langsamer als if sind ArrayListwurde benutzt.
  • Gute Leistung ist schwierig.
  • Auch wenn Big-O-Leistung die gleiche ist wie ArrayListEs wird wahrscheinlich sowieso deutlich langsamer sein.
  • Es ist erschütternd zu sehen LinkedList in der Quelle, weil es wahrscheinlich die falsche Wahl ist.

190
2018-01-01 20:23



Als jemand, der seit etwa einem Jahrzehnt in sehr großen SOA-Webservices operational Performance Engineering betreibt, würde ich das Verhalten von LinkedList gegenüber ArrayList bevorzugen. Während der Durchsatz von LinkedList im Steady-State schlechter ist und daher zu mehr Hardware führen kann, könnte das unter Druck stehende ArrayList dazu führen, dass Anwendungen in einem Cluster ihre Arrays fast synchron erweitern und bei großen Array-Größen zu mangelnder Reaktionsfähigkeit führen können in der App und einem Ausfall, während unter Druck, was katastrophales Verhalten ist.

Auf ähnliche Weise können Sie in einer App einen besseren Durchsatz als den standardmäßigen Garbage Collector erzielen, aber sobald Sie Java-Apps mit 10 GB Heap erhalten, können Sie die App für 25 Sekunden während eines Full GCs sperren, was zu Timeouts 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 vorhersagbarere und kleinere Latenzzeiten aufweist.

ArrayList ist nur dann eine bessere Wahl für die Leistung, wenn Sie nur Leistung als Leistung verstehen und Latenz ignorieren können. Nach meiner Erfahrung bei meiner Arbeit kann ich die Latenz im schlimmsten Fall nicht ignorieren.


125
2018-04-08 20:33



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

ArrayLists sind gut für einmal schreiben-lesen-viele oder Appender, aber schlecht beim Hinzufügen / Entfernen von vorne oder Mitte.


111
2018-05-19 11:21



Ja, ich weiß, das ist eine uralte Frage, aber ich werde meine zwei Cent einwerfen:

LinkedList ist fast immer die falsche Wahl, leistungsmäßig. Es gibt einige sehr spezifische Algorithmen, für die eine LinkedList aufgerufen wird, aber diese sind sehr, sehr selten und der Algorithmus hängt normalerweise spezifisch von LinkedLists Fähigkeit ab, Elemente in der Mitte der Liste relativ schnell einzufügen und zu löschen, sobald Sie dort navigiert haben mit einem ListIterator.

Es gibt einen häufigen Anwendungsfall, in dem LinkedList die ArrayList übertrifft: die einer Warteschlange. Wenn Ihr Ziel jedoch die Leistung ist, sollten Sie anstelle von LinkedList auch die Verwendung einer ArrayBlockingQueue erwägen (wenn Sie eine obere Grenze für Ihre Warteschlangengröße im Voraus bestimmen können und es sich leisten können, den gesamten Speicher im Voraus zu reservieren) oder dies CircularArrayList-Implementierung. (Ja, es ist von 2001, also müssen Sie es generifizieren, aber ich habe vergleichbare Leistungsverhältnisse zu dem, was in dem Artikel gerade in einer aktuellen JVM zitiert wurde)


92
2017-11-27 01:39



Es ist eine Effizienzfrage. LinkedList ist schnell zum Hinzufügen und Löschen von Elementen, aber langsam, um auf ein bestimmtes Element zuzugreifen. ArrayList ist schnell für den Zugriff auf ein bestimmtes Element, kann aber langsam zu jedem Ende hinzugefügt werden und besonders langsam in der Mitte zu löschen.

Array vs ArrayList vs LinkedList vs Vektorgeht tiefer, wie auch Verknüpfte Liste.


50
2017-09-21 22:59