Wann sollte man LinkedList statt ArrayList in Java verwenden?

Question

Ich war schon immer jemand, der einfach nur benutzt:

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

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

Wann sollte LinkedList verwendet werden über ArrayList und andersherum?

Answer 1

ArrayList y LinkedList beide Geräte List interface und ihre Methoden und Ergebnisse sind fast identisch. Es gibt jedoch einige wenige Unterschiede zwischen ihnen, die je nach Anforderung den einen besser machen als den anderen.

ArrayList vs. LinkedList

1) Search: ArrayList Suchvorgang ist ziemlich schnell im Vergleich zum LinkedList Suchvorgang. get(int index) en ArrayList gibt die Leistung von O(1) während LinkedList Leistung ist O(n) .

Reason: ArrayList unterhält ein indexbasiertes System für seine Elemente, da es implizit eine Array-Datenstruktur verwendet, was die Suche nach einem Element in der Liste schneller macht. Auf der anderen Seite LinkedList implementiert eine doppelt verkettete Liste, bei der alle Elemente durchlaufen werden müssen, um ein Element zu finden.

2) Deletion: LinkedList Die Operation Entfernen ergibt O(1) Leistung während ArrayList ergibt eine variable Leistung: 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 schneller im Vergleich zu ArrayList.

Grund: LinkedList's jedes Element unterhält zwei Zeiger (Adressen), die auf die beiden benachbarten Elemente in der Liste zeigt. Daher erfordert das Entfernen nur eine Änderung der Zeigerposition in den beiden Nachbarknoten (Elementen) des Knotens, der entfernt werden soll. Während in ArrayList alle Elemente verschoben werden müssen, um den durch das entfernte Element entstandenen Platz auszufüllen.

3) Inserts Performance: LinkedList add-Methode ergibt O(1) Leistung während ArrayList gibt O(n) im schlimmsten Fall. Der Grund dafür ist derselbe wie beim Entfernen.

4) Memory Overhead: ArrayList verwaltet Indizes und Elementdaten, während LinkedList verwaltet Elementdaten und zwei Zeiger für Nachbarknoten

Daher ist der Speicherverbrauch in LinkedList vergleichsweise hoch.

Es gibt nur wenige Gemeinsamkeiten zwischen diesen Klassen, die wie folgt lauten:

• Sowohl ArrayList als auch LinkedList sind Implementierungen der Schnittstelle List.
• Sie halten beide die Elemente Einfüge-Reihenfolge, die während der Anzeige von ArrayList und LinkedList Elemente der Ergebnismenge wäre mit der gleichen Reihenfolge, in der die Elemente in die Liste eingefügt wurde bedeutet.
• Diese beiden Klassen sind nicht synchronisiert und können explizit mit der Methode Collections.synchronizedList synchronisiert werden.
• El iterator y listIterator die von diesen Klassen zurückgegeben werden, sind fail-fast (wenn die Liste zu irgendeinem Zeitpunkt nach der Erstellung des Iterators strukturell verändert wird, und zwar in irgendeiner Weise außer durch die iterator’s eigene Methoden zum Entfernen oder Hinzufügen, wird der Iterator throw a ConcurrentModificationException ).

Wann sollte man LinkedList und wann ArrayList verwenden?

• Wie oben erläutert, sind die Einfüge- und Entnahmevorgänge sehr leistungsfähig (O(1)) en LinkedList im Vergleich zu ArrayList(O(n)) .

  Wenn also in einer Anwendung häufiges Hinzufügen und Löschen erforderlich ist, ist LinkedList die beste Wahl.

• Suche ( get method ) Operationen sind schnell in Arraylist (O(1)) aber nicht in LinkedList (O(n))

  Wenn also weniger Hinzufügungs- und Entfernungsvorgänge und mehr Suchvorgänge erforderlich sind, wäre ArrayList die beste Wahl.

Answer 2

両方 remove() y insert() haben eine Laufzeiteffizienz von O(n) sowohl für ArrayLists als auch für LinkedLists. Der Grund für die lineare Verarbeitungszeit liegt jedoch in zwei sehr unterschiedlichen Gründen:

In einer ArrayList erreicht man das Element in O(1), aber wenn man etwas entfernt oder einfügt, ist es O(n), weil alle folgenden Elemente geändert werden müssen.

In einer LinkedList dauert es O(n), um 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 wir nur 1 Verweis ändern müssen für remove() und 2 Referenzen für insert() .

Welches der beiden Verfahren schneller ist, hängt davon ab, wo das Einsetzen und Herausnehmen geschieht. Wenn wir uns näher am Anfang befinden, ist die LinkedList schneller, weil wir relativ wenige Elemente durchgehen müssen. Wenn wir uns näher am Ende befinden, ist eine ArrayList schneller, weil wir in konstanter Zeit dorthin gelangen und nur die wenigen verbleibenden Elemente ändern müssen, die ihr folgen. Wenn wir uns genau in der Mitte befinden, ist die LinkedList schneller, weil das Durchgehen von n Elementen schneller ist als das Verschieben von n Werten.

Bonus: Während es keine Möglichkeit gibt, diese beiden Methoden für eine ArrayList zu O(1) zu machen, gibt es tatsächlich eine Möglichkeit, dies in LinkedLists zu tun. Nehmen wir an, wir wollen die gesamte Liste durchgehen und dabei Elemente entfernen und einfügen. Normalerweise würde man mit der LinkedList für jedes Element ganz von vorne beginnen, wir könnten aber 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() y insert() bei der Arbeit in einer LinkedList. Das ist der einzige Leistungsvorteil, der mir bekannt ist, bei dem eine LinkedList immer besser ist als eine ArrayList.

Answer 3

Einer der Tests, die ich hier gesehen habe, führt den Test nur einmal durch. Aber mir ist aufgefallen, dass man diese Tests viele Male durchführen muss und die Zeiten schließlich konvergieren. Im Grunde muss die JVM erst einmal warmlaufen. In meinem speziellen Anwendungsfall musste ich Elemente zu einer Liste hinzufügen/entfernen, die auf etwa 500 Elemente anwächst. In meinen Tests LinkedList kam schneller heraus, mit LinkedList rund 50.000 NS und ArrayList mit etwa 90.000 NS... mehr oder weniger. 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;
}

Answer 4

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

Die Klasse LinkedList erweitert AbstractSequentialList und implementiert die Schnittstellen List, Deque und Queue.
Leistung
arraylist.get() ist O(1), während linkedlist.get() ist O(n)
arraylist.add() ist O(1) und linkedlist.add() ist 0(1)
arraylist.contains() ist O(n) und linkedlist.contains() ist O(n)
arraylist.next() ist O(1) und linkedlist.next() ist O(1)
arraylist.remove() ist O(n), während linkedlist.remove() ist O(1)
In arraylist
iterator.remove() ist O(n)
in der Erwägung, dass in der verknüpften Liste
iterator.remove() ist O(1)

Answer 5

Meine Faustregel lautet: Wenn ich eine Collection (d.h. es muss nicht unbedingt ein List ), dann verwenden Sie ArrayList wenn Sie die Größe im Voraus kennen, oder die Größe sicher wissen, oder wissen, dass sie nicht viel variieren wird. Wenn Sie zufälligen Zugriff benötigen (d. h. Sie verwenden get(index) ) dann vermeiden LinkedList . Grundsätzlich gilt: Verwenden Sie LinkedList nur, wenn Sie keinen Indexzugriff benötigen und die (ungefähre) Größe der Sammlung, die Sie zuweisen, nicht kennen. Auch wenn Sie viele Hinzufügungen und Entfernungen vornehmen werden (wiederum durch die Collection Schnittstelle) kann LinkedList vorzuziehen sein.