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

Eine wichtige Eigenschaft einer verketteten Liste (die ich in einer anderen Antwort nicht gelesen habe) ist die Verkettung zweier Listen. Bei einem Array ist dies O(n) (+ Overhead einiger Reallokationen), bei einer verketteten Liste ist dies nur O(1) oder O(2) ;-)

Wichtig : Für Java ist es LinkedList Das ist nicht wahr! Siehe Gibt es eine schnelle concat-Methode für verknüpfte Listen in Java?

Answer 2

ArrayList und LinkedList haben ihre eigenen Vor- und Nachteile.

ArrayList verwendet zusammenhängende Speicheradressen im Vergleich zu LinkedList, das Zeiger auf den nächsten Knoten verwendet. Wenn Sie also ein Element in einer ArrayList nachschlagen wollen, ist das schneller als n Iterationen mit LinkedList.

Andererseits ist das Einfügen und Löschen in einer LinkedList viel einfacher, da man nur die Zeiger ändern muss, während eine ArrayList die Verwendung einer Verschiebeoperation für jedes Einfügen oder Löschen impliziert.

Wenn Sie häufige Abrufvorgänge in Ihrer Anwendung haben, verwenden Sie eine ArrayList. Wenn Sie häufig einfügen und löschen, verwenden Sie eine LinkedList.

Answer 3

1) Zugrunde liegende Datenstruktur

Der erste Unterschied zwischen ArrayList und LinkedList liegt in der Tatsache, dass ArrayList durch Array unterstützt wird, während LinkedList durch LinkedList unterstützt wird. Dies wird zu weiteren Unterschieden in der Leistung führen.

2) LinkedList implementiert Deque

Ein weiterer Unterschied zwischen ArrayList und LinkedList ist, dass LinkedList neben der List-Schnittstelle auch die Deque-Schnittstelle implementiert, die First-in-First-out-Operationen für add() y poll() und mehrere andere Deque-Funktionen. 3) Hinzufügen von Elementen in ArrayList Das Hinzufügen eines Elements 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 ist das Hinzufügen eines Elements in LinkedList eine O(1)-Operation, da es keine Navigation erfordert.

4) Ein Element aus einer Position entfernen

Um ein Element aus einem bestimmten Index zu entfernen, z. B. durch Aufruf von remove(index) ArrayList führt einen Kopiervorgang durch, wodurch es fast O(n) wird, während LinkedList zu diesem Punkt durchlaufen muss, wodurch es ebenfalls O(n/2) wird, da es je nach Nähe von beiden Richtungen aus durchlaufen 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) Abrufen von Elementen aus einer Position

El get(index) Operation ist O(1) in ArrayList, während sie O(n/2) in LinkedList ist, da sie bis zu diesem Eintrag durchlaufen werden muss. In der Big-O-Notation ist O(n/2) jedoch einfach O(n), da wir dort Konstanten ignorieren.

7) Speicher

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

Der Speicherbedarf scheint also bei ArrayList geringer zu sein als bei LinkedList, außer in dem Fall, in dem Array die Größenänderung durchführt, wenn es den Inhalt von einem Array in ein anderes kopiert.

Wenn das Array groß genug ist, kann es zu diesem Zeitpunkt viel Speicherplatz beanspruchen und die Garbage Collection auslösen, was die Antwortzeit verlangsamen kann.

Aus all den oben genannten Unterschieden zwischen ArrayList und LinkedList sieht es so aus, als ob ArrayList in fast allen Fällen die bessere Wahl ist als LinkedList, außer wenn man eine häufige add() Betrieb als remove() , oder get() .

Es ist einfacher, eine verknüpfte Liste als ArrayList zu ändern, insbesondere wenn Sie Elemente am Anfang oder Ende hinzufügen oder entfernen, da die verknüpfte Liste intern Referenzen auf diese Positionen behält und sie in O(1) Zeit zugänglich sind.

Mit anderen Worten: Sie müssen die verknüpfte Liste nicht durchlaufen, um zu der Position zu gelangen, an der Sie Elemente hinzufügen möchten; in diesem Fall wird die Addition zu einer O(n)-Operation. Zum Beispiel das Einfügen oder Löschen eines Elements in der Mitte einer verknüpften Liste.

Meiner Meinung nach, verwenden ArrayList über LinkedList für die meisten der praktischen Zweck in Java.

Answer 4

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

Jedes Mal, wenn ich eine Methode, die eine Liste von Daten aus einer DB erhalten gibt ich immer eine LinkedList verwenden.

Mein Grundgedanke war, dass, weil es unmöglich ist, genau zu wissen, wie viele Ergebnisse bin ich immer, es wird nicht Speicher verschwendet (wie in ArrayList mit der Differenz zwischen der Kapazität und die tatsächliche Anzahl der Elemente), und es würde keine Zeit verschwendet werden, versuchen, die Kapazität zu duplizieren.

Soweit eine ArrayList, ich stimme zu, dass zumindest Sie immer den Konstruktor mit der anfänglichen Kapazität verwenden sollten, um die Duplizierung der Arrays so weit wie möglich zu minimieren.

Answer 5

Die Operation get(i) in ArrayList ist schneller als LinkedList, weil:
ArrayList: Resizable-Array-Implementierung der List-Schnittstelle
LinkedList: Implementierung der List- und Deque-Schnittstellen in Form einer doppelt verketteten Liste

Operationen, die in die Liste indexieren, durchlaufen die Liste vom Anfang oder vom Ende, je nachdem, was näher am angegebenen Index liegt.