Wann wird LinkedList über ArrayList in Java verwendet?

3122

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 LinkedListverwendet werden ArrayListund umgekehrt?

sdellysse
quelle
4
Siehe auch: Array versus verknüpfte Liste
Hawkeye Parker
1
Lesen Sie einfach das Zitat des Autors von LinkedList stackoverflow.com/a/42529652/2032701 und Sie erhalten einen praktischen Überblick über das Problem.
Ruslan
Weitere Informationen finden Sie im Beitrag Java LinkedList vs ArrayList , in dem die Unterschiede beschrieben werden und der einige Leistungstests enthält.
Alonana

Antworten:

3371

Zusammenfassung ArrayList mit ArrayDequesind in viel mehr Anwendungsfällen vorzuziehen als LinkedList. Wenn Sie sich nicht sicher sind, beginnen Sie einfach mit ArrayList.


LinkedListund ArrayListsind zwei verschiedene Implementierungen der List-Schnittstelle. LinkedListimplementiert es mit einer doppelt verknüpften Liste. ArrayListimplementiert 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) wann index = 0oder index = list.size() - 1(in diesem Fall können Sie auch getFirst()und verwenden getLast()). Einer der Hauptvorteile von LinkedList<E>
  • add(int index, E element)ist O (n) (mit durchschnittlich n / 4 Schritten), aber O (1) wann index = 0oder index = list.size() - 1(in diesem Fall können Sie auch addFirst()und addLast()/ add()) verwenden. Einer der Hauptvorteile von LinkedList<E>
  • remove(int index)ist O (n) (mit durchschnittlich n / 4 Schritten), aber O (1) wann index = 0oder index = list.size() - 1(in diesem Fall können Sie auch removeFirst()und verwenden removeLast()). Einer der Hauptvorteile von LinkedList<E>
  • Iterator.remove()ist O (1) . Einer der Hauptvorteile von LinkedList<E>
  • ListIterator.add(E element)ist O (1) . Einer der Hauptvorteile von LinkedList<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 von ArrayList<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 muss
  • add(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ür index = 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 Zugabe ArrayListist 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 ArrayListist 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 LinkedListergeben 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 einem LinkedListMittel nach den Verknüpfungen in O (n) ( n / 2 Schritte) nach dem schlimmsten Fall gesucht werden, während in einer ArrayListgewünschten Position mathematisch berechnet und in O (1) zugegriffen werden kann .

Ein weiterer Vorteil der Verwendung von a LinkedListergibt 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 sind ArrayList. Beachten Sie, dass ArrayDequedies eine gute Alternative zum LinkedListHinzufügen und Entfernen vom Kopf sein kann, aber keine List.

Wenn Sie große Listen haben, beachten Sie auch, dass die Speichernutzung ebenfalls unterschiedlich ist. Jedes Element von a LinkedListhat mehr Overhead, da auch Zeiger auf das nächste und das vorherige Element gespeichert werden. ArrayListshabe diesen Overhead nicht. Allerdings ArrayListsnehmen 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 ArrayListist 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 die ArrayListmit einer höheren Anfangskapazität.

Jonathan Tran
quelle
182
Ich habe vergessen, die Einfügungskosten zu erwähnen. In einer LinkedList kostet das Einfügen O (1), sobald Sie die richtige Position haben, während es in einer ArrayList auf O (n) steigt - alle Elemente, die über die Einfügemarke hinausgehen, müssen verschoben werden.
David Rodríguez - Dribeas
26
In Bezug auf die Verwendung von Vector: Es besteht wirklich keine Notwendigkeit, auf Vector zurückzugreifen. Die Möglichkeit hierfür besteht in Ihrer bevorzugten List-Implementierung und einem Aufruf von synchronizedList, um einen synchronisierten Wrapper zu erhalten. Siehe: java.sun.com/docs/books/tutorial/collections/implementations/…
Ryan Cox
69
Nein, für eine LinkedList ist get immer noch O (n), selbst wenn Sie die Position kennen, denn um zu dieser Position zu gelangen, muss die zugrunde liegende Implementierung die "nächsten" Zeiger der verknüpften Liste durchlaufen, um zum Wert dieser Position zu gelangen. Es gibt keinen Direktzugriff. Für Position 2 mag das Gehen der Zeiger billig sein, aber für Position 1 Million nicht so billig. Der Punkt ist, es ist proportional zur Position, was bedeutet, dass es O (n) ist.
Jonathan Tran
53
@ Kevin Es kann wichtig sein, dass der Speicher "nahe beieinander" ist. Die Hardware speichert zusammenhängende Speicherblöcke (dynamisches RAM) in einem schnelleren statischen RAM im L1- oder L2-Cache. Theoretisch und die meiste Zeit praktisch kann Speicher als Direktzugriff behandelt werden. In der Realität ist das sequentielle Lesen des Speichers jedoch etwas schneller als in zufälliger Reihenfolge. Für eine leistungskritische Schleife könnte dies von Bedeutung sein. Sie nennen es "räumliche Lokalität" oder Referenzlokalität .
Jonathan Tran
92
Es gibt kein O(n/2)oder O(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/2nO(n/2)O(n/4)O(n)LinkedListArrayListO(n/2)O(n/4)
Holger
630

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. Deshalb ArrayListhabe 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 LinkedListsund eingefügt ArrayLists.

Hinweis: Die für die ArrayListZeilen angezeigten Größen gelten für zugeschnittene Listen. In der Praxis ist die Kapazität des Hintergrundarrays in einem ArrayListim 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.


Diagramm von LinkedList und ArrayList Anzahl der Elemente x Bytes


Das Ergebnis zeigt deutlich, dass dies LinkedListviel mehr ist als ArrayList, insbesondere bei einer sehr hohen Elementanzahl. Wenn das Gedächtnis ein Faktor ist, meiden Sie es LinkedLists.

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)

Numeron
quelle
2
Sehr interessant zu sehen, dass LinkedList zum Speichern eines einzelnen Elements genauso viel Speicher benötigt wie ArrayList. Wie unintuitiv! Was passiert, wenn Sie Ihr Beispiel mit -XX: + UseCompressedOops ausführen?
Jontejj
215
Das Problem mit Ihrer Mathematik ist, dass Ihr Diagramm die Auswirkungen stark überträgt. Sie modellieren Objekte, die jeweils nur int4 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.
Heath Hunnicutt
6
Keines der ArrayList / LinkedList / Node-Objekte enthält nur ein int, daher verstehe ich nicht, was Sie dort sagen. Ich habe 'Objekt-Overhead' in 'Objekt-Header' umbenannt - es gibt einen 8-Byte-Header für jedes Objekt, unabhängig vom System, und ja, das schließt alle Node-Objekte in LinkedList ein, die alle so weit wie möglich korrekt gezählt werden sagen. Übrigens, als ich es mir noch einmal ansah, fand ich ein paar andere Probleme mit meiner Mathematik in LinkedList, die die Aufteilung und ArrayList tatsächlich verschlimmern . Ich bin froh, es weiter zu aktualisieren, also zögern Sie bitte nicht, es weiter zu klären und näher zu erläutern.
Numeron
6
Es sollte beachtet werden, dass dies CompressedOopsjetzt in allen aktuellen JDKs (7, 8 und Aktualisierungen von 6 für einige Jahre) Standard ist, sodass 64-Bit keinen Unterschied in ArrayListoder LinkedListGröße macht, es sei denn, Sie haben komprimierte Hoppla für explizit deaktiviert irgendein Grund.
BeeOnRope
1
@jontejj Die Standardkapazitätserhöhung beträgt 50%. Wenn Sie also eine ArrayListohne Angabe einer Anfangskapazität füllen, wird immer noch deutlich weniger Speicher als bei a benötigt LinkedList.
Holger
243

ArrayListist was du willst. LinkedListist fast immer ein (Leistungs-) Fehler.

Warum LinkedListsaugt:

  • Es verwendet viele kleine Speicherobjekte und wirkt sich daher auf die Leistung im gesamten Prozess aus.
  • Viele kleine Objekte sind schlecht für die Cache-Lokalität.
  • Jede indizierte Operation erfordert eine Durchquerung, dh eine O (n) -Leistung. Dies ist im Quellcode nicht offensichtlich, was zu Algorithmen O (n) führt, die langsamer sind als wenn sie ArrayListverwendet würden.
  • Gute Leistung zu erzielen ist schwierig.
  • Selbst wenn die Big-O-Leistung dieselbe ist wie ArrayList, wird sie wahrscheinlich ohnehin erheblich langsamer sein.
  • Es ist unglaublich, LinkedListin der Quelle zu sehen, weil es wahrscheinlich die falsche Wahl ist.
Tom Hawtin - Tackline
quelle
236
Es tut uns leid. hat dich markiert. LinkedList saugt nicht. Es gibt Situationen, in denen LinkedList die richtige Klasse ist. Ich stimme zu, dass es nicht viele Situationen gibt, in denen es besser ist als ein Arraylist, aber es gibt sie. Erziehe Leute, die dumme Dinge tun!
David Turner
40
Es tut mir leid zu sehen, dass Sie dafür viele Abstimmungen erhalten haben. Es gibt in der Tat kaum einen Grund, Javas LinkedList zu verwenden. Zusätzlich zu der schlechten Leistung verwendet es viel mehr Speicher als die anderen konkreten Listenklassen (jeder Knoten hat zwei zusätzliche Zeiger und jeder Knoten ist ein separates Wrapper-Objekt mit den dazugehörigen zusätzlichen Overhead-Bytes).
Kevin Brock
42
Dies ist eine der nützlichsten Antworten hier. Es ist eine Schande, dass so viele Programmierer (a) den Unterschied zwischen abstrakten Datentypen und konkreten Implementierungen nicht verstehen und (b) die reale Bedeutung konstanter Faktoren und des Speicheraufwands für die Bestimmung der Leistung.
Porculus
50
-1: Dies ist eine ziemlich blinkende Ansicht. Ja, es stimmt, dass ArrayList ein sehr vielseitiges Tool ist. Es hat jedoch seine Grenzen. Es gibt Fälle, in denen dies zu Problemen führt und Sie LinkedList verwenden müssen. Natürlich ist es eine sehr spezialisierte Lösung, und wie jedes spezialisierte Werkzeug wird es in den meisten Fällen von einer vielseitigen Lösung übertroffen. Das heißt aber nicht, dass es "scheiße" ist oder so, man muss nur wissen, wann man es benutzt.
Malcolm
27
@ DavidTurner: Sie existieren, aber ich denke, Toms Punkt war, dass Sie wahrscheinlich ArrayList wollen, wenn Sie fragen müssen.
user541686
139

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.

lamont
quelle
8
Wäre es nicht eine andere Lösung, die Größe der Liste programmgesteuert mithilfe der Methode verifyCapacity () der ArrayList zu verwalten? Meine Frage ist, warum so viele Dinge in einer Reihe spröder Datenstrukturen gespeichert werden, wenn sie möglicherweise besser in einem Caching- oder DB-Mechanismus gespeichert werden. Ich hatte neulich ein Interview, in dem sie über die Übel von ArrayList schworen, aber ich komme hierher und finde, dass die Komplexitätsanalyse rundum besser ist! Toller Punkt für die Diskussion, obwohl. VIELEN DANK!
Ingyhere
22
Sobald Sie 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 führt. Mit LinkedList ermorden Sie den Garbage Collector während eines vollständigen GCs. Er muss die übermäßig große LinkedList mit aktiviertem Cache-Fehler durchlaufen jeder Knoten.
Bests
5
Das ist ... eine schreckliche Lösung. Sie sind im Grunde genommen auf die GC-Bereinigung für Sie angewiesen, was unglaublich teuer ist, wenn Sie stattdessen auf einer Arrayliste "sureCapacity ()" aufrufen können ...
Philip Devine
5
@Andreas: A weist LinkedList immer das Fünffache des Speichers zu als ein einfaches Array von Referenzen, sodass ein ArrayListvorü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 das LinkedListviel früher
Holger
5
@Andreas Das andere Problem ist, wie der Speicher zugewiesen wird. LinkedListbenötigt nur ein kleines Stück freien Speichers, um das nächste Element zuzuweisen. ArrayListbenö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.
Piotr Kusmierczyk
128
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 eignen sich gut zum Schreiben, einmal Lesen, Lesen oder Anhängen, aber schlecht zum Hinzufügen / Entfernen von vorne oder in der Mitte.

Michael Munsey
quelle
42
Sie können Big-O-Werte nicht direkt vergleichen, ohne über konstante Faktoren nachzudenken. Bei kleinen Listen (und die meisten Listen sind klein) ist das O (N) von ArrayList schneller als das O (1) von LinkedList.
Porculus
4
Die Leistung kleiner Listen ist mir egal, und mein Computer auch nicht, es sei denn, er wird irgendwie in einer Schleife verwendet.
Maarten Bodewes
45
LinkedList kann nicht wirklich in der Mitte einfügen O(1). Es muss die Hälfte der Liste durchlaufen, um die Einfügemarke zu finden.
Thomas Ahle
8
LinkedList: in Mitte O (1) einfügen - ist FALSCH! Ich fand heraus, dass selbst das Einfügen in die 1/10 Position der LinkedList-Größe langsamer ist als das Einfügen eines Elements in die 1/10 Position einer ArrayList. Und noch schlimmer: das Ende der Sammlung. Das Einfügen in die letzten Positionen (nicht die allerletzten) von ArrayList ist schneller als in die letzten Positionen (nicht die allerletzten) von LinkedList
kachanov
14
@kachanov Einfügen in a LinkedList ist, O(1) wenn Sie einen Iterator für die Einfügeposition haben , dh ListIterator.addangeblich O(1)für a LinkedList.
Hat aufgehört - Anony-Mousse
107

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

Daniel Martin
quelle
39
Ab Java 6 können Sie verwenden ArrayDeque. docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html
Thomas Ahle
1
ArrayDequeist langsamer als LinkedListwenn nicht alle Operationen am selben Ende sind. Es ist in Ordnung, wenn es als Stapel verwendet wird, aber es macht keine gute Warteschlange.
Jeremy List
2
Nicht wahr - zumindest für die Implementierung von Oracle in jdk1.7.0_60 und im folgenden Test. Ich habe einen Test erstellt, bei dem ich 10 Millionen Mal eine Schleife durchführe und eine Deque von 10 Millionen zufälligen Ganzzahlen habe. Innerhalb der Schleife frage ich ein Element ab und biete ein konstantes Element an. Auf meinem Computer ist LinkedList mehr als zehnmal langsamer als ArrayDeque und benötigt weniger Speicher. Der Grund dafür ist, dass ArrayDeque im Gegensatz zu ArrayList einen Zeiger auf den Kopf des Arrays behält, damit beim Entfernen des Kopfes nicht alle Elemente verschoben werden müssen.
Henno Vermeulen
6
ArrayDequeist wahrscheinlich schneller als Stackbei Verwendung als Stapel und schneller als LinkedListbei Verwendung als Warteschlange.
akhil_mittal
3
Beachten Sie, dass der Kommentar von akhil_mittal ein Zitat aus der ArrayDequeDokumentation ist.
Stuart Marks
65

Es ist eine Effizienzfrage. LinkedListist schnell zum Hinzufügen und Löschen von Elementen, aber langsam zum Zugreifen auf ein bestimmtes Element. ArrayListist 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 .

dgtized
quelle
54

Richtig oder falsch: Bitte führen Sie den Test lokal durch und entscheiden Sie selbst!

Bearbeiten / Entfernen ist schneller LinkedListals ArrayList.

ArrayList, unterstützt von Array, 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.


Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

Hier ist der Code:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}
Asche
quelle
1
ArrayList muss nicht verdoppelt werden, um genau zu sein. Bitte überprüfen Sie zuerst die Quellen.
Danubian Sailor
Es sollte beachtet werden, dass Ihr Beispiel fehlerhaft ist ... Sie entfernen aus einer Zeichenfolge zwischen: 18 + [2, 12] Bytes ("true0false", "true500000false"), durchschnittlich 25 Bytes, was der Größe der Elemente entspricht mitten drin. Es ist bekannt, dass mit zunehmender Größe der Elementbytes die Leistung der verknüpften Liste besser wird. Mit zunehmender Größe der Liste wird ein zusammenhängendes Array (Liste) besser abschneiden. Am wichtigsten ist, dass Sie .equals () für Zeichenfolgen ausführen - was keine billige Operation ist. Wenn Sie stattdessen ganze Zahlen verwenden würden, würde es einen Unterschied geben.
Centril
2
"... ist bei großvolumigen Anwendungen schlechter ": Dies ist ein Missverständnis. LinkedListhat 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ür ArrayListbeträgt eineinhalb Wörter, was 6 Bytes und im schlimmsten Fall 8 Bytes ergibt.
Lii
1
Ich habe hier eine bessere Version Ihres Benchmarks mit Ergebnissen erstellt - die Leistung beim Anhängen für die Arrayliste ist für Ihre künstlich niedrig, da addAll ein Speicherarray mit genau der Anfangsgröße bereitstellt, sodass die erste Einfügung immer eine auslöst Arraycopy. Dies umfasst auch Aufwärmzyklen, um die JIT-Kompilierung zu ermöglichen, bevor Daten erfasst werden.
BobMcGee
4
@BillK seit Java 8 können Sie verwenden, removeIf(element -> condition)wo es passt, was für a im ArrayListVergleich 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, LinkedListhängt vom jeweiligen Szenario ab, da a LinkedListtheoretisch O (1) ist. Das Entfernen nur eines einzelnen Knotens erfordert jedoch mehrere Speicherzugriffe, die leicht die Anzahl überschreiten können, die zum ArrayListEntfernen einer signifikanten Anzahl von Elementen erforderlich ist .
Holger
50

ArrayListist im Wesentlichen ein Array. LinkedListwird als doppelt verknüpfte Liste implementiert.

Das getist ziemlich klar. O (1) für ArrayList, da der ArrayListzufällige Zugriff mithilfe des Index möglich ist. O (n) für LinkedList, weil es zuerst den Index finden muss. Hinweis: Es gibt verschiedene Versionen von addund remove.

LinkedListist schneller beim Hinzufügen und Entfernen, aber langsamer beim Abrufen. Kurz gesagt, LinkedListsollte bevorzugt werden, wenn:

  1. Es gibt keine große Anzahl von Direktzugriffen auf Elemente
  2. Es gibt eine große Anzahl von Hinzufügungs- / Entfernungsvorgängen

=== ArrayList ===

  • addiere (E e)
    • am Ende von ArrayList hinzufügen
    • erfordern Kosten für die Größenänderung des Speichers.
    • O (n) am schlimmsten, O (1) amortisiert
  • add (int index, E element)
    • zu einer bestimmten Indexposition hinzufügen
    • erfordern Verschiebung und mögliche Kosten für die Größenänderung des Speichers
    • Auf)
  • entfernen (int index)
    • Entfernen Sie ein angegebenes Element
    • erfordern Verschiebung und mögliche Kosten für die Größenänderung des Speichers
    • Auf)
  • entfernen (Objekt o)
    • Entfernen Sie das erste Vorkommen des angegebenen Elements aus dieser Liste
    • müssen zuerst das Element durchsuchen und dann die Kosten für das Verschieben und mögliche Ändern der Speichergröße verschieben
    • Auf)

=== LinkedList ===

  • addiere (E e)

    • am Ende der Liste hinzufügen
    • O (1)
  • add (int index, E element)

    • an der angegebenen Position einsetzen
    • müssen zuerst die Position finden
    • Auf)
  • entfernen()
    • Entfernen Sie das erste Element der Liste
    • O (1)
  • entfernen (int index)
    • Element mit angegebenem Index entfernen
    • müssen zuerst das Element finden
    • Auf)
  • entfernen (Objekt o)
    • Entfernen Sie das erste Vorkommen des angegebenen Elements
    • müssen zuerst das Element finden
    • Auf)

Hier ist eine Abbildung von programcreek.com ( addund removesind 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.):

Geben Sie hier die Bildbeschreibung ein

Ryan
quelle
3
"LinkedList ist schneller als Hinzufügen / Entfernen". Falsch, überprüfen Sie die Antwort über stackoverflow.com/a/7507740/638670
Nerrve
49

Joshua Bloch, der Autor von LinkedList:

Verwendet jemand tatsächlich LinkedList? Ich habe es geschrieben und benutze es 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 die interessanteste und selbsterklärendste.

Ruslan
quelle
34

ArrayListist zufällig zugänglich, während LinkedListes wirklich billig ist, Elemente zu erweitern und zu entfernen. In den meisten Fällen ArrayListist 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.

Dustin
quelle
15
LinkedList ist nicht billig, um Elemente hinzuzufügen. Es ist fast immer schneller, einer ArrayList eine Million Elemente hinzuzufügen, als sie einer LinkedList hinzuzufügen. Und die meisten Listen im realen Code sind nicht einmal eine Million Elemente lang.
Porculus
10
Zu jedem Zeitpunkt kennen Sie die Kosten für das Hinzufügen eines Elements zu Ihrer LinkedList. Die ArrayList haben Sie (im Allgemeinen) nicht. Das Hinzufügen eines einzelnen Elements zu einer ArrayList mit einer Million Elementen kann sehr lange dauern. Dies ist eine O (n) -Operation plus doppelter Speicherplatz, es sei denn, Sie haben Speicherplatz vorab zugewiesen. Das Hinzufügen eines Elements zu einer LinkedList ist O (1). Meine letzte Aussage steht.
Dustin
4
Das Hinzufügen eines einzelnen Elements zu einer ArrayList ist O (1), unabhängig davon, ob es sich um 1 Million oder 1 Milliarde handelt. Das Hinzufügen eines Elements zu einer LinkedList ist ebenfalls O (1). "Hinzufügen" bedeutet HINZUFÜGEN ZUM ENDE.
Kachanov
Sie müssen die Implementierung anders gelesen haben als ich. Nach meiner Erfahrung dauert das Kopieren eines 1-Milliarden-Element-Arrays länger als das Kopieren eines 1-Millionen-Element-Arrays.
Dustin
6
@kachanov du musst Dustin falsch verstehen. Wenn Sie kein Array mit 1 Milliarde Elementen deklariert haben, müssen Sie möglicherweise die Größe Ihres Arrays ändern. In diesem Fall müssen Sie alle Elemente in ein neues größeres Array kopieren. Daher erhalten Sie manchmal O (N), jedoch mit einer verknüpften Liste immer Holen Sie sich O (1)
Stan R.
29

TL; DR wird aufgrund der modernen Computerarchitektur ArrayListfür nahezu jeden möglichen Anwendungsfall wesentlich effizienter sein - und LinkedListsollte 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 LinkedListeine bessere Leistung erzielt werden könnte als im Cache-Bereich ArrayList .

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):

Geben Sie hier die Bildbeschreibung ein

Arbeiten an einer Hardware der späteren Generation (größere, effizientere Caches) - die Ergebnisse sind noch schlüssiger:

Geben Sie hier die Bildbeschreibung ein

LinkedList benötigt viel mehr Zeit, um denselben Job auszuführen. Quell- Quellcode

Dafür gibt es zwei Hauptgründe:

  1. Hauptsächlich - dass die Knoten der LinkedListzufä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. ArrayListElemente werden im kontinuierlichen Speicher gespeichert - genau dafür optimiert die moderne CPU-Architektur.

  2. Sekundär LinkedList erforderlich, um Rückwärts- / Vorwärtszeiger zu halten, was das Dreifache des Speicherverbrauchs pro gespeichertem Wert im Vergleich zu bedeutet ArrayList.

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:

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

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 LinkedListwirklich glänzen sollte und ArrayListschlechte oder sogar schlechtere Ergebnisse liefern sollte:

Geben Sie hier die Bildbeschreibung ein

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/ Vectorviel effizienter


Credits: Alle hier veröffentlichten Benchmarks wurden von Kjell Hedström erstellt . Noch mehr Daten finden Sie in seinem Blog

Lior Bar-On
quelle
Ich würde eine Warteschlange nicht als einzigartig oder extrem bezeichnen! Eine FIFO-Warteschlange ist in einer LinkedList viel einfacher zu implementieren als in einer ArrayList. Es ist tatsächlich ein Albtraum auf einer ArrayList, da Sie Ihren eigenen Start verfolgen, anhalten und Ihre eigene Neuzuweisung vornehmen müssen. Sie können auch ein Array verwenden, aber eine verknüpfte Liste ist ein Fifo. Ich bin mir über die Implementierung von Java nicht sicher, aber eine LinkedList kann O (1) sowohl für Warteschlangen- als auch für Warteschlangenoperationen ausführen .)
Bill K
24

Wenn Ihr Code add(0)und hat remove(0), verwenden Sie ein LinkedListund es ist schöner addFirst()und removeFirst()Methoden. Andernfalls verwenden Sie ArrayList.

Und natürlich Guava ‚s ImmutableList ist dein bester Freund.

Jesse Wilson
quelle
3
Bei kleinen Listen ist ArrayList.add (0) immer noch schneller als LinkedList.addFirst ().
Porculus
1
@Porculus Ich höre ständig dieses Argument, dass ArrayList.add (0) für kleine Listen schneller sein wird. Wie klein ist das? 10 Elemente, 10 Millionen?
Garg10Mai
1
@ garg10may klein ist weniger als 10.
Jesse Wilson
@Porculus small bedeutet weniger als die maximale Kapazität des internen Arrays, das der ArrayList zugrunde liegt.
Janac Meena
21

Ich weiß, dass dies ein alter Beitrag ist, aber ich kann ehrlich gesagt nicht glauben, dass niemand erwähnt hat, dass dies LinkedListimplementiert wird Deque. Schauen Sie sich einfach die Methoden in Deque(und Queue) an. wenn Sie einen fairen Vergleich wollen, versuchen Sie laufen LinkedListgegen ArrayDequeund ein Feature-for-Feature Vergleich zu tun.

Ajax
quelle
18

Hier ist die Big-O - Notation in beide ArrayListund LinkedListauch CopyOnWrite-ArrayList:

Anordnungsliste

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

LinkedList

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Basierend auf diesen müssen Sie entscheiden, was Sie wählen möchten. :) :)

Rajith Delantha
quelle
9
>>>> ArrayList add -> O (1) <- nicht wahr. In einigen Fällen muss ArrayList wachsen, um ein weiteres Element hinzuzufügen
Kachanov
1
LinkedList remove ist nicht O (1), es müsste nach dem zu entfernenden Element gesucht werden, daher Worst-Case O (n) und durchschnittliches O (n / 2)
garg10may
Dies ist LinkedList.add()auch nicht der Fall, obwohl die meisten Antworten hier dies aussagen.
user207421
18

Vergleichen wir LinkedList und ArrayList anhand der folgenden Parameter:

1. Implementierung

ArrayList ist die anpassbare Array-Implementierung der Listenschnittstelle

LinkedList ist die doppelt verknüpfte Listenimplementierung der Listenschnittstelle .


2. Leistung

  • get (int index) oder Suchoperation

    Die Operation ArrayList get (int index) wird in konstanter Zeit ausgeführt, dh O (1) while

    Die Laufzeit der LinkedList get (int index) -Operation ist O (n).

    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)

    Einfügungen in LinkedList sind im Vergleich zu ArrayList im Allgemeinen schnell. In LinkedList ist das Hinzufügen oder Einfügen eine O (1) -Operation.

    Wenn in ArrayList das Array vollständig ist, dh im schlimmsten Fall, fallen zusätzliche Kosten für die Größenänderung des Arrays und das Kopieren von Elementen in das neue Array an, wodurch die Laufzeit der Additionsoperation in ArrayList O (n) erhöht wird, andernfalls ist es O (1). .

  • (int) Operation entfernen

    Die Entfernungsoperation in LinkedList ist im Allgemeinen dieselbe wie in ArrayList, dh O (n).

    In LinkedList gibt es zwei überladene Entfernungsmethoden. Eine davon ist remove () ohne einen Parameter, der den Kopf der Liste entfernt und in konstanter Zeit O (1) ausgeführt wird. Die andere überladene Methode zum Entfernen in LinkedList ist remove (int) oder remove (Object), mit der das als Parameter übergebene Objekt oder int entfernt wird. Diese Methode durchläuft die LinkedList, bis das Objekt gefunden und von der ursprünglichen Liste getrennt wurde. Daher ist diese Methodenlaufzeit O (n).

    Während in ArrayList die Methode remove (int) das Kopieren von Elementen aus dem alten Array in ein neues aktualisiertes Array umfasst, beträgt die Laufzeit daher O (n).


3. Iterator umkehren

LinkedList kann mit descendingIterator () while in umgekehrter Richtung iteriert werden

In ArrayList gibt es keinen descendingIterator () , daher müssen wir unseren eigenen Code schreiben, um die ArrayList in umgekehrter Richtung zu durchlaufen.


4. Anfangskapazität

Wenn der Konstruktor nicht überladen ist, erstellt ArrayList eine leere Liste der Anfangskapazität 10, während

LinkedList erstellt nur die leere Liste ohne anfängliche Kapazität.


5. Speicher-Overhead

Der Speicheraufwand in LinkedList ist im Vergleich zu ArrayList höher, da ein Knoten in LinkedList die Adressen des nächsten und vorherigen Knotens verwalten muss. Während

In ArrayList enthält jeder Index nur das tatsächliche Objekt (Daten).


Quelle

Abhijeet Ashok Muneshwar
quelle
18

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.

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|
Gayan Weerakutti
quelle
Das ArrayDeque gleicht die Dinge etwas mehr in Richtung der Arrays aus, da das Einfügen / Entfernen von Vorder- und Rückseite alle O (1) sind. Das einzige, was die verknüpfte Liste noch gewinnt, ist das Hinzufügen / Entfernen während des Durchlaufs (die Iterator-Operationen).
Bill K
14

Zusätzlich zu den anderen oben genannten guten Argumenten sollten Sie die ArrayListImplementierungsschnittstelle RandomAccessund die LinkedListImplementierungsschnittstelle beachten Queue.

Irgendwie sprechen sie leicht unterschiedliche Probleme an, mit Unterschieden in Effizienz und Verhalten (siehe ihre Liste der Methoden).

PhiLho
quelle
10

Dies hängt davon ab, welche Vorgänge Sie in der Liste ausführen werden.

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

Matthew Schinckel
quelle
2
Um mehr zu erfahren, lesen Sie nicht, schreiben Sie einfach den Code. und Sie werden feststellen, dass die ArrayList-Implementierung beim Einfügen und Löschen schneller ist als die LinkedList.
Kachanov
8

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.

kemiller2002
quelle
7

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 LinkedListdies nicht wahr! Siehe Gibt es eine schnelle Concat-Methode für verknüpfte Listen in Java?

Karussell
quelle
2
Wie ist das? Dies gilt möglicherweise für verknüpfte Listendatenstrukturen, jedoch nicht für ein Java LinkList-Objekt. Sie können nicht einfach einen nextvon 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, als add()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.
Kevin Brock
ja stimmt. Ich habe die Antwort entsprechend bearbeitet. Aber sehen Sie diese Antwort für 'wie' es mit LinkedList macht: stackoverflow.com/questions/2494031/…
Karussell
7

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.

Nesan Mano
quelle
6

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.

Gaijinco
quelle
5

ArrayListund LinkedListbeide Geräte List 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: ArrayListSuchvorgang ist im Vergleich zum Suchvorgang ziemlich schnell LinkedList. get(int index)in ArrayListgibt die Leistung von O(1)während LinkedListLeistung ist O(n).

Reason: ArrayListDas 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 wird LinkedListeine doppelt verknüpfte Liste implementiert, bei der alle Elemente zum Durchsuchen eines Elements durchlaufen werden müssen.

2) Deletion: LinkedListEntfernen entfernen gibt O(1)Leistung, während ArrayListvariable Leistung gibt: O(n)im schlimmsten Fall (beim Entfernen des ersten Elements) und O(1)im besten Fall (beim Entfernen des letzten Elements).

Schlussfolgerung: Das Löschen von LinkedList-Elementen ist im Vergleich zu ArrayList schneller.

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: LinkedListadd - Methode gibt die O(1)Leistung während ArrayListgibt O(n)im schlimmsten Fall. Der Grund ist der gleiche wie für das Entfernen erläutert.

4) Memory Overhead: ArrayListverwaltet Indizes und Elementdaten, während LinkedListElementdaten und zwei Zeiger für Nachbarknoten verwaltet werden

Daher ist der Speicherverbrauch in LinkedList vergleichsweise hoch.

Es gibt nur wenige Ähnlichkeiten zwischen diesen Klassen:

  • Sowohl ArrayList als auch LinkedList sind Implementierungen der List-Schnittstelle.
  • Beide behalten die Einfügereihenfolge der Elemente bei, was bedeutet, dass beim Anzeigen von ArrayList- und LinkedList-Elementen die Ergebnismenge dieselbe Reihenfolge aufweist, in der die Elemente in die Liste eingefügt wurden.
  • Beide Klassen sind nicht synchronisiert und können mithilfe der Collections.synchronizedList-Methode explizit synchronisiert werden.
  • Die iteratorund listIteratorvon diesen Klassen zurückgegeben werden fail-fast(wenn die Liste zu irgendeinem Zeitpunkt nach dem Erstellen des Iterators strukturell geändert wird, außer durch die iterator’seigenen Methoden zum Entfernen oder Hinzufügen, wird der Iterator throwa ConcurrentModificationException).

Wann wird LinkedList und wann ArrayList verwendet?

  • Wie oben erläutert, ergeben die Einfüge- und Entfernungsvorgänge (O(1))im LinkedListVergleich zu eine gute Leistung ArrayList(O(n)).

    Wenn in der Anwendung häufig hinzugefügt und gelöscht werden muss, ist LinkedList die beste Wahl.

  • Search ( get method) -Operationen sind schnell in, Arraylist (O(1))aber nicht inLinkedList (O(n))

    Wenn weniger Operationen zum Hinzufügen und Entfernen und mehr Suchvorgänge erforderlich sind, ist ArrayList die beste Wahl.

Real73
quelle
5

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.

Amitābha
quelle
5

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.

Anjali Suman
quelle
1
Ich denke, dies ist die am besten formulierte Antwort der gesamten Gruppe hier. Es ist genau und informativ. Ich würde vorschlagen, die letzte Zeile zu ändern - am Ende "abgesehen von Warteschlangen" hinzufügen, die sehr wichtige Strukturen sind, die für eine verknüpfte Liste überhaupt keinen Sinn ergeben.
Bill K
3

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 LinkedListkam schneller heraus, mitLinkedList ungefähr 50.000 NS und ArrayListungefähr 90.000 NS ... Geben oder Nehmen. Siehe den Code unten.

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}
Jose Martinez
quelle
2

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.

pietz
quelle
1

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), wohingegen linkedlist.get()O (n)
arraylist.add()O (1) ist und linkedlist.add()0 (1)
arraylist.contains()O (n) ist und linkedlist.contains()O (n)
arraylist.next()O (1) ist und linkedlist.next()O (1)
arraylist.remove()O (n) ist wohingegen linkedlist.remove()O (1)
in der Arrayliste
iterator.remove()O (n) ist,
während in der verknüpften Liste
iterator.remove()O (1) ist

Randhawa
quelle