unterschied Wann sollte LinkedList über ArrayList in Java verwendet werden?




linked list java (24)

Ich war immer einer, den ich einfach benutzen konnte:

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

Ich benutze die Schnittstelle als Typnamen für die Portabilität , damit ich meinen Code überarbeiten kann, wenn ich Fragen wie diese stelle.

Wann sollte LinkedList über ArrayList und umgekehrt?


ArrayListist willkürlich zugänglich, während LinkedListes wirklich billig ist, Elemente zu erweitern und zu entfernen. Für die meisten Fälle ArrayListist das gut.

Wenn Sie keine großen Listen erstellt und einen Engpass gemessen haben, müssen Sie sich wahrscheinlich nie um den Unterschied sorgen.


Es hängt davon ab, welche Operationen Sie auf der Liste ausführen werden.

ArrayListist schneller, um auf einen indizierten Wert zuzugreifen. Es ist viel schlimmer, wenn Sie Objekte einfügen oder löschen.

Weitere Informationen finden Sie in den Artikeln, in denen der Unterschied zwischen Arrays und verknüpften Listen beschrieben wird.


Ich habe die Antworten gelesen, aber es gibt ein Szenario, in dem ich immer eine LinkedList über eine ArrayList verwende, die ich teilen möchte, um Meinungen zu hören:

Jedes Mal, wenn ich eine Methode hatte, die eine Liste von Daten aus einer Datenbank zurückgibt, verwende ich immer eine LinkedList.

Mein Grund war, dass es unmöglich ist, genau zu wissen, wie viele Ergebnisse ich bekomme, dass kein Speicherplatz verschwendet wird (wie in ArrayList mit dem Unterschied zwischen der Kapazität und der tatsächlichen Anzahl von Elementen), und es würde keine Zeit für den Versuch geben Kapazität verdoppeln.

Soweit eine ArrayList, stimme ich zu, dass Sie immer den Konstruktor mit der ursprünglichen Kapazität verwenden sollten, um die Duplizierung der Arrays so gering wie möglich zu halten.


1) Basisdatenstruktur

Der erste Unterschied zwischen ArrayList und LinkedList besteht darin, dass ArrayList von Array und von LinkedList durch LinkedList gesichert 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-Out-Operationen für add () und poll () und mehrere andere Deque-Funktionen bereitstellt. 3) Hinzufügen von Elementen in ArrayList Das Hinzufügen von Elementen in ArrayList ist O (1), wenn die Größe des Arrays nicht geändert wird. In diesem Fall wird es O (log (n)) LinkedList ist 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) heranführt, während LinkedList an diesen Punkt gelangen muss, wodurch es auch O (n / 2) ist. , wie es aus jeder Richtung aufgrund der Nähe verfahren werden kann.

5) Iteration über ArrayList oder LinkedList

Iteration ist die O (n) -Operation sowohl für LinkedList als auch für ArrayList, wobei n die Nummer eines Elements ist.

6) Element von einer Position abrufen

Die get (Index) -Operation ist O (1) in ArrayList und deren O (n / 2) in LinkedList, da bis zu diesem Eintrag durchlaufen werden muss. In der Big-O-Notation ist O (n / 2) jedoch nur O (n), weil wir dort Konstanten ignorieren.

7) Speicher

LinkedList verwendet das Wrapper-Objekt Entry, eine statische verschachtelte Klasse zum Speichern von Daten und zwei Knoten neben und vor, während ArrayList nur Daten in Array speichert.

Die Speicheranforderung scheint also bei ArrayList geringer als bei LinkedList zu sein, mit Ausnahme des Falles, in dem Array die Größenänderung vornimmt, wenn Inhalt von einem Array in ein anderes kopiert wird.

Wenn das Array groß genug ist, kann an diesem Punkt viel Speicherplatz erforderlich sein und die Garbage-Collection ausgelöst werden, was die Antwortzeit verlangsamen kann.

Aufgrund der oben genannten Unterschiede zwischen ArrayList und LinkedList scheint ArrayList in fast allen Fällen die bessere Wahl als LinkedList zu sein, es sei denn, Sie führen eine häufige Operation 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 auf diese Zeit (1) zugreifbar 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 der Zusatz O (n). Zum Beispiel das Einfügen oder Löschen eines Elements in der Mitte einer verknüpften Liste.

Meiner Meinung nach verwenden Sie ArrayList gegenüber LinkedList für die meisten praktischen Zwecke in Java.


Ich weiß , das ist eine alte Post, aber ich kann ehrlich nicht glauben , dass niemand erwähnt , dass LinkedListGeräte Deque. Schauen Sie sich 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.


Operation get (i) in Arraylist ist schneller als LinkedList, denn:
Arraylist: Resizable-Array Implementierung der Liste Schnittstelle
LinkedList: doppelt verketteten Liste Umsetzung der Liste und Deque Schnittstellen

Operationen, die in die Liste aufgenommen werden, durchlaufen die Liste vom Anfang oder vom Ende, je nachdem, welcher Punkt näher am angegebenen Index liegt.


ArrayList und LinkedList haben ihre eigenen Vor- und Nachteile.

ArrayList verwendet zusammenhängende Speicheradressen im Vergleich zu LinkedList, die Zeiger auf den nächsten Knoten verwendet. Wenn Sie also nach einem Element in einer ArrayList suchen möchten, ist dies schneller als das Durchlaufen von N Iterationen mit LinkedList.

Andererseits ist das Einfügen und Löschen in einer LinkedList viel einfacher, da Sie lediglich die Zeiger ändern müssen, während eine ArrayList die Verwendung einer Shift-Operation für das Einfügen oder Löschen impliziert.

Wenn in Ihrer App häufig Abrufvorgänge ausgeführt werden, verwenden Sie eine ArrayList. Bei häufigem Einfügen und Löschen verwenden Sie eine LinkedList.


Einer der Tests, die ich hier gesehen habe, führt den Test nur einmal durch. Ich habe jedoch festgestellt, dass Sie diese Tests viele Male ausführen müssen, und ihre Zeiten werden eventuell zusammenlaufen. Grundsätzlich muss die JVM aufwärmen. Für meinen speziellen Anwendungsfall musste ich Elemente zu einem Leisten hinzufügen / entfernen, der auf etwa 500 Elemente anwächst. In meinen Tests LinkedListkamen die Tests schneller zustande, wobei LinkedListetwa 50.000 NS miteinander verbunden waren und ArrayListetwa 90.000 NS kamen. 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;
}

ArrayList erweitert AbstractList und implementiert die Listenschnittstelle. ArrayList ist ein dynamisches Array.
Es kann gesagt werden, dass es im Grunde geschaffen wurde, um die Nachteile von Arrays zu überwinden.

Die LinkedList-Klasse erweitert AbstractSequentialList und implementiert die Schnittstelle List, Deque und Queue.
Performance
arraylist.get()ist , während O (1) linkedlist.get()O (n)
arraylist.add()O (1) und linkedlist.add()0 (1)
arraylist.contains()ist O (n) und linkedlist.contains()O (n)
arraylist.next()O (1) und linkedlist.next()O (1)
arraylist.remove()ist O (n) , während linkedlist.remove()ist O (1)
In der Arrayliste
iterator.remove()ist O (n),
wohingegen die In Linkedlist
iterator.remove()O (1) ist.


Ja, ich weiß, das ist eine alte Frage, aber ich werde meine zwei Cents einbringen:

LinkedList ist fast immer die falsche Wahl, was die Leistung angeht. Es gibt einige sehr spezifische Algorithmen, für die eine LinkedList erforderlich ist, aber diese sind sehr, sehr selten und der Algorithmus hängt in der Regel 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 allgemeinen Anwendungsfall, in dem LinkedList ArrayList übertrifft: der einer Warteschlange. Wenn Ihr Ziel jedoch die Leistung ist, sollten Sie anstelle von LinkedList auch die Verwendung eines ArrayBlockingQueue-Objekts in Betracht ziehen (wenn Sie im Voraus eine Obergrenze für Ihre Warteschlangengröße festlegen können und es sich leisten können, den gesamten Speicher im Voraus zuzuordnen) oder diese CircularArrayList-Implementierung . (Ja, es ist aus dem Jahr 2001, daher müssen Sie es generieren, aber ich habe vergleichbare Leistungsverhältnisse zu dem, was gerade in einer aktuellen JVM im Artikel zitiert wurde).


Vergleichen wir LinkedList und ArrayList mit den folgenden Parametern:

1. Umsetzung

ArrayList ist die anpassbare Array-Implementierung der Listenschnittstelle, während

LinkedList ist die Implementierung der Listenschnittstelle mit doppelt verknüpfter Liste.

2. Leistung

  • get (int index) oder Suchvorgang

    Die ArrayList- Operation 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 sie entweder vom Anfang oder vom Ende (je nachdem, was näher ist) den Knoten am angegebenen Elementindex abruft.

  • Einfügen () oder Hinzufügen (Objekt)

    Einfügungen in LinkedList sind im Allgemeinen vergleichbar mit ArrayList. In LinkedList ist das Hinzufügen oder Einfügen O (1).

    Wenn in ArrayList das Array voll ist, dh im schlimmsten Fall, entstehen zusätzliche Kosten für die Größenänderung des Arrays und das Kopieren von Elementen in das neue Array, wodurch die Laufzeit der Add-Operation in ArrayList O (n) ausgeführt wird. .

  • (int) Operation entfernen

    Der Vorgang zum Entfernen in LinkedList entspricht im Allgemeinen dem von ArrayList, dh O (n).

    In LinkedList gibt es zwei überladene remove-Methoden. one ist remove () ohne Parameter, die den Kopf der Liste entfernen und in einer konstanten Zeit O (1) laufen. Die andere überladene remove-Methode in LinkedList ist remove (int) oder remove (Object), wodurch das als Parameter übergebene Object oder int entfernt wird. Diese Methode durchsucht die LinkedList, bis sie das Objekt gefunden hat, und hebt die Verknüpfung von der ursprünglichen Liste auf. Daher ist diese Methodenlaufzeit O (n).

    Während in der remove (int) -Methode in ArrayList Elemente aus dem alten Array in ein neues aktualisiertes Array kopiert werden, ist ihre Laufzeit O (n).

3. Umgekehrter Iterator

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

Es gibt keinen descendingIterator () in ArrayList. 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 mit der ursprünglichen Kapazität 10

LinkedList erstellt nur die leere Liste ohne Anfangskapazität.

5. Speicheraufwand

Der Speicheraufwand in LinkedList ist mehr als bei ArrayList, da ein Knoten in LinkedList die Adressen des nächsten und vorherigen Knotens beibehalten muss. Während

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

Source


Ein wichtiges Merkmal einer verknüpften Liste (die ich nicht in einer anderen Antwort gelesen habe) ist die Verkettung zweier Listen. Bei einem Array ist dies O (n) (+ Overhead einiger Neuzuordnungen), bei einer verknüpften Liste ist dies nur O (1) oder O (2) ;-)

Wichtig : Für Java LinkedListist das nicht wahr! Siehe Gibt es eine schnelle Concat-Methode für verknüpfte Liste in Java?


Joshua Bloch, der Autor von LinkedList:

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

Link: https://twitter.com/joshbloch/status/583813919019573248

Es tut mir leid für die Antwort, nicht so informativ wie die anderen Antworten zu sein, aber ich dachte, es wäre am interessantesten und selbsterklärend.


ArrayList ist im Wesentlichen ein Array. LinkedList wird als doppelt verknüpfte Liste implementiert.

Das ist ziemlich klar. O (1) für ArrayList , da ArrayList den wahlfreien Zugriff über den Index zulässt. O (n) für LinkedList , da der Index zuerst gefunden werden muss. Hinweis: Es gibt verschiedene Versionen von add und remove .

LinkedList ist schneller beim Hinzufügen und Entfernen, aber langsamer beim LinkedList . Kurz LinkedList , LinkedList sollte bevorzugt werden, wenn:

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

=== ArrayList ===

  • addieren (E e)
    • add am Ende von ArrayList
    • erfordern die Größenänderung des Speichers.
    • O (n) am schlechtesten, 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)
    • ein bestimmtes Element entfernen
    • 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
    • Zuerst müssen Sie das Element durchsuchen und dann die möglichen Kosten für die Größenänderung des Speichers verschieben
    • Auf)

=== LinkedList ===

  • addieren (E e)

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

    • an der angegebenen Position einfügen
    • müssen zuerst die Position finden
    • Auf)
  • Löschen()
    • erstes Element der Liste entfernen
    • O (1)
  • entfernen (int index)
    • Element mit dem angegebenen Index entfernen
    • Das Element muss zuerst gefunden werden
    • Auf)
  • entfernen (Objekt o)
    • Entfernen Sie das erste Vorkommen des angegebenen Elements
    • Das Element muss zuerst gefunden werden
    • 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.):


Hier ist die Big-O-Notation in ArrayListund LinkedListund auch 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 sollen. :)


1) Suche: Der ArrayList-Suchvorgang ist im Vergleich zum LinkedList-Suchvorgang ziemlich schnell. get (int index) in ArrayList gibt die Leistung von O (1) an, während die Leistung von LinkedList O (n) ist.

Grund: ArrayList verwaltet ein indexbasiertes System für seine Elemente, da die Array-Datenstruktur implizit verwendet wird, was die Suche nach einem Element in der Liste beschleunigt. Auf der anderen Seite implementiert LinkedList eine doppelt verknüpfte Liste, die den Durchlauf durch alle Elemente zum Durchsuchen eines Elements erfordert.

2) Löschen: Der Vorgang zum Entfernen der LinkedList gibt O (1) Leistung, während ArrayList die variable Leistung ergibt: O (n) im schlimmsten Fall (beim Entfernen des ersten Elements) und O (1) im besten Fall (beim Entfernen des letzten Elements) .

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

Grund: Jedes Element von LinkedList enthält zwei Zeiger (Adressen), die auf beide Nachbarelemente in der Liste zeigen. Daher erfordert das Entfernen nur eine Änderung der Zeigerposition in den zwei benachbarten Knoten (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: Die LinkedList-Add-Methode gibt O (1) Performance, während ArrayList im schlimmsten Fall O (n) ergibt. Der Grund ist derselbe wie für das Entfernen.

4) Speicheraufwand: ArrayList verwaltet Indizes und Elementdaten, während LinkedList Elementdaten und zwei Zeiger für benachbarte Knoten verwaltet, sodass der Speicherverbrauch in LinkedList vergleichsweise hoch ist.

Es gibt wenige Ähnlichkeiten zwischen diesen Klassen, die wie folgt lauten:

Sowohl ArrayList als auch LinkedList sind Implementierungen der List-Schnittstelle. Sie behalten beide die Einfügereihenfolge der Elemente bei, dh, bei der Anzeige von ArrayList- und LinkedList-Elementen würde die Ergebnismenge dieselbe Reihenfolge aufweisen, 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. Der Iterator und der listIterator, die von diesen Klassen zurückgegeben werden, sind ausfallsicher (wenn die Liste zu irgendeinem Zeitpunkt nach dem Erstellen des Iterators strukturell geändert wird, abgesehen von den eigenen Remove- oder Add-Methoden des Iterators, gibt der Iterator eine ConcurrentModificationException aus).

Wann ist LinkedList und wann ArrayList zu verwenden?

1) Wie oben erläutert, ergeben die Einfüge- und Entfernungsoperationen in LinkedList eine gute Leistung (O (1)) im Vergleich zu ArrayList (O (n)). Wenn daher häufiges Hinzufügen und Löschen in einer Anwendung erforderlich ist, ist LinkedList die beste Wahl.

2) Suchoperationen (get-Methode) sind in ArrayList (O (1)) schnell, aber nicht in LinkedList (O (n)). Wenn weniger Add- und Remove-Vorgänge erforderlich sind und mehr Suchvorgänge erforderlich sind, wäre ArrayList die beste Wahl.



Bislang scheint niemand den Speicherfußabdruck jeder dieser Listen angesprochen zu haben, abgesehen von dem allgemeinen Konsens, dass eine LinkedList "viel mehr" als eine ArrayList ist. LinkedList habe ich einige Zahlen gezwungen, um genau zu zeigen, wie viel beide Listen für N-Null-Verweise LinkedList .

Da Verweise in ihren relativen Systemen entweder 32 oder 64 Bits (auch wenn sie null sind) enthalten, habe ich 4 Datensätze für 32- und 64-Bit- LinkedLists und ArrayLists LinkedLists .

Hinweis: Die für die ArrayList Zeilen angegebenen Größen gelten für getrimmte Listen. In der Praxis ist die Kapazität des Hintergrundarrays in einer ArrayList im Allgemeinen größer als die aktuelle Elementanzahl.

Hinweis 2: (Dank an BeeOnRope) Da CompressedOops nun ab Mitte JDK6 voreingestellt ist, stimmen die unten angegebenen Werte für 64-Bit-Maschinen grundsätzlich mit ihren 32-Bit-Pendants überein, es sei denn, Sie deaktivieren es ausdrücklich.

Das Ergebnis zeigt deutlich, dass LinkedList weitaus mehr ist als ArrayList , insbesondere bei einer sehr hohen Elementanzahl. Wenn Speicher ein Faktor ist, müssen Sie sich von 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. Der Grund für die Mods ist, dass alle Objekte in Java ein Vielfaches von 8 Byte Speicherplatz beanspruchen, unabhängig davon, ob alle Objekte 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)

ArrayList ist was Sie wollen. LinkedList ist fast immer ein (Performance-) Fehler.

Warum LinkedList :

  • Es verwendet viele kleine Speicherobjekte und beeinflusst daher die Leistung im gesamten Prozess.
  • Viele kleine Objekte sind schlecht für die Cache-Lokalität.
  • Jede indizierte Operation erfordert eine Durchquerung, dh sie hat eine Leistung von O (n). Dies ist im Quellcode nicht offensichtlich und führt dazu, dass die Algorithmen O (n) langsamer sind als bei der Verwendung von ArrayList .
  • Gute Leistung zu erhalten, ist schwierig.
  • Selbst wenn Big-O-Leistung mit ArrayList identisch ist, wird sie wahrscheinlich sowieso erheblich langsamer sein.
  • Es ist erschütternd, LinkedList in der Quelle zu sehen, weil es wahrscheinlich die falsche Wahl ist.

Als jemand, der seit ungefähr einem Jahrzehnt operatives Performance-Engineering für sehr umfangreiche SOA-Web-Services durchführt, würde ich das Verhalten von LinkedList gegenüber ArrayList vorziehen. Der Steady-State-Durchsatz von LinkedList ist zwar schlechter und kann daher dazu führen, dass mehr Hardware gekauft wird. Das Verhalten von ArrayList unter Druck könnte dazu führen, dass Apps in einem Cluster ihre Arrays nahezu synchron ausdehnen und bei großen Arraygrößen zu mangelnder Reaktionsfähigkeit führen in der App und einem Ausfall, während unter Druck, das katastrophale Verhalten ist.

In ähnlicher Weise können Sie den Durchsatz in einer App mit dem standardmäßigen Durchsatz-Garbage-Collector verbessern. Sobald Sie jedoch Java-Apps mit 10 GB-Heaps erhalten, können Sie die App für 25 Sekunden während eines Full GCs schließen, was zu Timeouts und Fehlern in SOA-Apps führt und bläst Ihre SLAs, wenn es zu oft auftritt. Obwohl der CMS-Collector mehr Ressourcen beansprucht und nicht denselben Rohdurchsatz erzielt, ist er eine viel bessere Wahl, da er besser vorhersehbar ist und eine geringere Latenz aufweist.

ArrayList ist nur dann eine bessere Wahl für die Leistung, wenn Sie nur den Durchsatz als Leistung bezeichnen und die Latenz ignorieren können. Nach meiner Berufserfahrung kann ich die Worst-Case-Latenz nicht ignorieren.


Zusammenfassung ArrayList mit ArrayDeque ist in viel mehr Anwendungsfällen vorzuziehen als LinkedList . Wenn Sie sich nicht sicher sind, beginnen Sie einfach mit 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 Array zur dynamischen Größenänderung.

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

Für LinkedList<E>

  • get(int index) ist O (n) (mit durchschnittlich n / 4 Schritten)
  • add(E element) ist O (1)
  • add(int index, E element) ist O (n) (mit durchschnittlich n / 4 Schritten), aber O (1), wenn index = 0 <Hauptnutzen von LinkedList<E>
  • remove(int index) ist O (n) (mit durchschnittlich n / 4 Schritten)
  • 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 Operationen benötigen im Durchschnitt n / 4 Schritte, im besten Fall eine konstante Anzahl von Schritten (z. B. Index = 0) und im ungünstigsten Fall n / 2 Schritte (Mitte der Liste).

Für ArrayList<E>

  • get(int index) ist O (1) <--- Hauptvorteil von ArrayList<E>
  • add(E element) wird O (1) amortisiert, aber O (n) ungünstigster Fall, da das Array in der Größe 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: Für viele Operationen sind im Durchschnitt n / 2 Schritte erforderlich, im besten Fall eine konstante Anzahl von Schritten (Ende der Liste), im schlechtesten Fall n Schritte (Beginn der Liste).

LinkedList<E> ermöglicht das Einfügen oder LinkedList<E> von Zeitkonstanten mithilfe von Iteratoren , jedoch nur den sequentiellen Zugriff auf Elemente. Mit anderen Worten, Sie können die Liste vorwärts oder rückwärts durchlaufen, aber das Auffinden einer Position in der Liste erfordert Zeit, die der Größe der Liste proportional ist. Javadoc sagt, dass "Operationen, die in die Liste aufgenommen werden, die Liste vom Anfang oder vom Ende durchqueren, je nachdem, was näher ist" , so dass diese Methoden im Durchschnitt O (n) ( n / 4 Schritte) sind, O (1) für index = 0

ArrayList<E> hingegen erlaubt einen schnellen wahlfreien Lesezugriff, sodass Sie jedes Element in konstanter Zeit erfassen können. Das Hinzufügen oder Entfernen von einer beliebigen Stelle bis auf das Ende erfordert jedoch das Verschieben aller letzteren Elemente, um entweder eine Öffnung zu schaffen oder die Lücke zu füllen. Wenn Sie mehr Elemente als die Kapazität des zugrunde liegenden Arrays hinzufügen, wird ein neues Array (das 1,5-fache der Größe) zugewiesen, und das alte Array wird in das neue Array kopiert. Das Hinzufügen zu einer ArrayList ist also O (n) im Array schlimmster Fall aber im Durchschnitt konstant.

Abhängig von den geplanten Operationen sollten Sie die Implementierungen entsprechend auswählen. Das Durchlaufen einer der beiden Arten von Listen ist praktisch genauso günstig. (Das Durchlaufen einer ArrayList ist technisch schneller, aber wenn Sie nicht wirklich leistungsabhängig sind, sollten Sie sich keine Sorgen machen - sie sind beide Konstanten.)

Die Hauptvorteile der Verwendung einer LinkedList ergeben sich, wenn Sie vorhandene Iteratoren zum Einfügen und Entfernen von Elementen erneut verwenden. Diese Operationen können dann in O (1) ausgeführt werden, indem nur die Liste lokal geändert wird. In einer Array-Liste muss der Rest des Arrays verschoben (dh kopiert) werden. Auf der anderen Seite bedeutet das Suchen in einer LinkedList dass den Verknüpfungen in O (n) ( n / 2 Schritten) im schlimmsten Fall LinkedList wird, während in einer ArrayList die gewünschte Position mathematisch berechnet und in O (1) abgerufen werden kann.

Ein weiterer Vorteil der Verwendung einer LinkedList sich aus dem Hinzufügen oder Entfernen aus dem Kopf der Liste, da diese Operationen O (1) und O (n) für ArrayList . Beachten Sie, dass ArrayDeque eine gute Alternative zu LinkedList zum Hinzufügen und Entfernen vom Kopf ist, aber es ist keine List .

Wenn Sie über große Listen verfügen, sollten Sie auch daran denken, dass sich auch die Speichernutzung unterscheidet. Jedes Element einer LinkedList hat mehr Overhead, da auch Zeiger auf das nächste und vorherige Element gespeichert werden. ArrayLists haben diesen Overhead nicht. ArrayLists jedoch so viel Speicher, wie für die Kapazität reserviert ist, unabhängig davon, ob tatsächlich Elemente hinzugefügt wurden.

Die anfängliche Standardkapazität einer ArrayList ist ziemlich klein (10 von Java 1.4 - 1.8). Da die zugrunde liegende Implementierung jedoch ein Array ist, muss die Größe des Arrays geändert werden, wenn Sie viele Elemente hinzufügen. Konstruieren Sie die ArrayList mit einer höheren Anfangskapazität, um die hohen Kosten für die Größenänderung zu vermeiden, wenn Sie wissen, dass Sie viele Elemente hinzufügen werden.


Remove () und insert () haben sowohl für ArrayLists als auch für LinkedLists eine Laufzeiteffizienz von O (n). Der Grund für die lineare Bearbeitungszeit hat jedoch zwei sehr unterschiedliche Gründe:

In einer ArrayList gelangen Sie zu dem Element in O (1). Wenn Sie jedoch etwas entfernen oder einfügen, wird es O (n), da alle folgenden Elemente geändert werden müssen.

In einer LinkedList braucht man O (n), 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 Entfernen oder Einfügen ist tatsächlich konstant, da wir nur 1 Referenz für remove () und 2 Referenzen für insert () ändern müssen.

Welcher der beiden zum Einfügen und Entfernen schneller ist, hängt davon ab, wo er auftritt. Wenn wir näher am Anfang sind, wird die LinkedList schneller, da wir relativ wenige Elemente durchlaufen müssen. Wenn wir näher am Ende sind, wird eine ArrayList schneller sein, weil wir in konstanter Zeit dorthin gelangen und nur die wenigen verbleibenden Elemente ändern müssen, die ihr folgen. Wenn genau in der Mitte gearbeitet wird, ist die LinkedList schneller, da das Durchlaufen von n Elementen schneller ist als das Verschieben von n Werten.

Bonus: Es gibt zwar keine Möglichkeit, diese beiden Methoden zu O (1) für eine ArrayList zu machen, es gibt jedoch eine Möglichkeit, dies in LinkedLists durchzuführen. Angenommen, wir möchten die gesamte Liste durchgehen und Elemente entfernen und auf unserem Weg einfügen. Normalerweise fangen Sie für jedes Element mit der LinkedList am Anfang an, wir könnten das aktuelle Element, an dem wir arbeiten, mit einem Iterator "speichern". Mit Hilfe des Iterators erhalten wir beim Arbeiten in einer LinkedList eine O (1) - Effizienz für remove () und insert (). Es ist der einzige Leistungsvorteil, von dem ich weiß, dass eine LinkedList immer besser ist als eine ArrayList.


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

Bearbeiten / Entfernen ist in LinkedList schneller als ArrayList .

ArrayList , unterstützt durch Array , das doppelt so groß sein muss, ist bei Anwendungen mit großem Volumen schlechter.

Unten ist das Ergebnis der Einheitentests für jede Operation. Die Zeiteinstellung 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);
    }
}

Es ist eine Frage der Effizienz. LinkedList ist schnell für das Hinzufügen und Löschen von Elementen, aber der Zugriff auf ein bestimmtes Element ist langsam. ArrayList ist schnell für den Zugriff auf ein bestimmtes Element, kann jedoch langsam an einem Ende hinzugefügt werden und vor allem langsam in der Mitte gelöscht werden.

Array vs ArrayList vs LinkedList vs Vector geht in die Tiefe, ebenso wie Linked List .





linked-list