unterschied - linked list java




Wann sollte LinkedList über ArrayList in Java verwendet werden? (20)

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?


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.


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)

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


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);
    }
}

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.

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.


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.


TL; DR ist aufgrund der modernen Computerarchitektur ArrayListfür nahezu jeden möglichen Anwendungsfall wesentlich effizienter - und LinkedListsollte daher mit Ausnahme einiger sehr eindeutiger und extremer Fälle vermieden werden.

In der Theorie hat LinkedList ein O (1) für das 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- Struktur für feindliche Daten ist. Vom POV für die Leistung - es gibt sehr wenige Fälle, in denen LinkedListbessere Ergebnisse erzielt werden könnten als mit dem Cache-freundlichen ArrayList .

Hier sind die Ergebnisse eines Benchmark-Tests, der Elemente an zufälligen Positionen einfügt. Wie Sie sehen können, ist die Array-Liste viel effizienter, obwohl theoretisch jede Einfügung in der Mitte der Liste die n späteren Elemente des Arrays "verschieben" muss (niedrigere Werte sind besser):

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

LinkedList benötigt viel mehr Zeit, um denselben Job auszuführen. source Source Code

Dafür gibt es zwei Hauptgründe:

  1. Hauptsächlich - dass die Knoten der Knoten LinkedListzufällig im Speicher verteilt sind. RAM ("Random Access Memory") ist nicht wirklich zufällig und Speicherblöcke müssen in den Cache geladen werden. Dieser Vorgang benötigt Zeit, und wenn solche Abrufe häufig ausgeführt werden, müssen die Speicherseiten im Cache ständig ersetzt werden. ArrayListElemente werden im Dauerspeicher gespeichert - genau dafür optimiert die moderne CPU-Architektur.

  2. Secondary LinkedList erforderlich Vor / Zurück - Zeiger zu halten, was bedeutet , 3 - mal den Speicherverbrauch gespeichert pro Wert im Vergleich zu ArrayList.

DynamicIntArray , btw, ist eine benutzerdefinierte ArrayList-Implementierung, die Int(primitiver Typ) und keine Objekte enthält. Daher werden alle Daten wirklich nebeneinander gespeichert.

Zu beachten ist, dass die Kosten für das Abrufen des Speicherblocks höher sind als die Kosten für den Zugriff auf eine einzelne Speicherzelle. Daher ist der 1 MB große sequentielle 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 klarer zu machen, überprüfen Sie bitte den Benchmark, wenn Sie Elemente am Anfang der Liste hinzufügen. Dies ist ein Anwendungsfall, bei dem in der Theorie der LinkedListwirklich leuchten sollte und ArrayListschlechte oder sogar schlechtere Ergebnisse liefern sollte:

Hinweis: Dies ist ein Benchmark der C ++ Std-Bibliothek, aber meine bisherigen Erfahrungen haben gezeigt, dass die Ergebnisse von C ++ und Java sehr ähnlich sind. Quellcode

Eine sequentielle Massenspeicher Kopieren ist eine Operation , durch die moderne CPUs optimiert - Theorie verändert und tatsächlich machen, wieder ArrayList/ Vectorviel effizienter

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


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.


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.


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.


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


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.


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?


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;
}

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


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.


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.


Wenn Ihr Code add(0)und hat remove(0), verwenden Sie ein LinkedListund es ist hübscher addFirst()und removeFirst()Methoden. Ansonsten verwenden ArrayList.

Und Guava 's ImmutableList ist natürlich Ihr bester Freund.


Zusätzlich zu den anderen guten Argumenten oben sollten Sie die ArrayListimplements RandomAccessinterface und LinkedListimplements beachten Queue.

Irgendwie adressieren sie etwas unterschiedliche Probleme, mit unterschiedlichen Effizienz- und Verhaltensunterschieden (siehe Methodenliste).





linked-list