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

Ja, ich weiß, das ist eine uralte Frage, aber ich werde meinen Senf dazugeben:

LinkedList ist fast immer die falsche Wahl, was die Leistung angeht. Es gibt einige sehr spezifische Algorithmen, bei denen eine LinkedList erforderlich ist, aber diese sind sehr, sehr selten und der Algorithmus wird in der Regel speziell von der Fähigkeit der LinkedList abhängen, Elemente in der Mitte der Liste relativ schnell einzufügen und zu löschen, sobald man mit einem ListIterator dorthin navigiert hat.

Es gibt einen häufigen Anwendungsfall, in dem LinkedList besser abschneidet als ArrayList: der einer Warteschlange. Wenn Ihr Ziel jedoch die Leistung ist, sollten Sie anstelle von LinkedList auch eine ArrayBlockingQueue in Betracht ziehen (wenn Sie im Voraus eine Obergrenze für die Größe der Warteschlange festlegen können und es sich leisten können, den gesamten Speicher im Voraus zuzuweisen), oder dies Implementierung von CircularArrayList . (Ja, es ist von 2001, also müssen Sie es generieren, aber ich habe vergleichbare Leistungskennzahlen wie die im Artikel genannten in einer aktuellen JVM erhalten)

Answer 2

Es ist eine Frage der Effizienz. LinkedList ist schnell beim Hinzufügen und Löschen von Elementen, aber langsam beim Zugriff auf ein bestimmtes Element. ArrayList ist schnell, wenn es um den Zugriff auf ein bestimmtes Element geht, kann aber langsam sein, wenn es um das Hinzufügen an einem der Enden geht, und besonders langsam beim Löschen in der Mitte.

Array vs. ArrayList vs. LinkedList vs. Vektor geht mehr in die Tiefe, ebenso wie die Verknüpfte Liste .

Answer 3

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

Bearbeiten/Entfernen ist schneller in LinkedList als ArrayList .

ArrayList unterstützt durch Array die doppelt so groß sein muss, ist bei großvolumigen Anwendungen schlechter.

Nachfolgend finden Sie die Ergebnisse der Einheitstests für jeden Vorgang, wobei die Zeitangaben in Nanosekunden erfolgen.

---

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

Answer 4

ArrayList ist im Wesentlichen ein Array. LinkedList ist als doppelt verkettete Liste implementiert.

El get ist ziemlich klar. O(1) für ArrayList denn ArrayList einen zufälligen Zugriff über einen Index ermöglichen. O(n) für LinkedList weil es zuerst den Index finden muss. Hinweis: Es gibt verschiedene Versionen von add y remove .

LinkedList ist schneller bei add und remove, aber langsamer bei get. Kurz und gut, LinkedList sollte bevorzugt werden, wenn:

1. es gibt keine große Anzahl von Zufallszugriffen auf Elemente
2. es gibt eine große Anzahl von Hinzufügen/Entfernen-Vorgängen

\=== ArrayList \===

• add(E e)
  • am Ende von ArrayList hinzufügen
  • Kosten für die Änderung der Speichergröße erfordern.
  • O(n) schlechteste, O(1) amortisiert
• add(int index, E element)
  • zu einer bestimmten Indexposition hinzufügen
  • Kosten für die Verschiebung und mögliche Größenänderung des Speichers erfordern
  • O(n)
• remove(int index)
  • ein bestimmtes Element entfernen
  • Kosten für die Verschiebung und mögliche Größenänderung des Speichers erfordern
  • O(n)
• entfernen(Objekt o)
  • das erste Vorkommen des angegebenen Elements aus dieser Liste entfernen
  • Zuerst muss das Element gesucht werden, dann werden die Kosten für die Verschiebung und die eventuelle Änderung der Speichergröße berechnet.
  • O(n)

\=== LinkedList \===

• add(E e)

  • an das Ende der Liste anfügen
  • O(1)

• add(int index, E element)

  • an der angegebenen Position einfügen
  • Sie müssen zuerst die Position finden
  • O(n)
• entfernen()
  • erstes Element der Liste entfernen
  • O(1)
• remove(int index)
  • Element mit angegebenem Index entfernen
  • Sie müssen zuerst das Element finden
  • O(n)
• entfernen(Objekt o)
  • das erste Vorkommen des angegebenen Elements entfernen
  • Sie müssen zuerst das Element finden
  • O(n)

Hier ist eine Zahl aus programcreek.de ( add y remove sind vom ersten Typ, d. h. sie fügen ein Element am Ende der Liste hinzu und entfernen das Element an der angegebenen Position in der Liste):

Answer 5

TL;DR aufgrund der modernen Computerarchitektur, ArrayList für nahezu jeden möglichen Anwendungsfall deutlich effizienter sein - und daher LinkedList sollte außer in einigen sehr speziellen und extremen Fällen vermieden werden.

---

Theoretisch hat LinkedList eine 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 ganz anders, denn LinkedList ist eine Cache Feind Datenstruktur. Aus Sicht der Leistung gibt es nur sehr wenige Fälle, in denen LinkedList könnte leistungsfähiger sein als die Cache-freundlich 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 jedes Einfügen in der Mitte der Liste ein "Verschieben" der n spätere Elemente des Arrays (kleinere Werte sind besser):

Bei der Arbeit mit einer neueren Hardware-Generation (größere, effizientere Caches) sind die Ergebnisse noch aussagekräftiger:

LinkedList braucht viel mehr Zeit, um die gleiche Aufgabe zu erfüllen. Quelle Quellcode

Hierfür gibt es zwei Hauptgründe:

1. Hauptsächlich - dass die Knotenpunkte des LinkedList nach dem Zufallsprinzip über den Speicher verstreut sind. RAM ("Random Access Memory") ist nicht wirklich zufällig und Speicherblöcke müssen in den Zwischenspeicher geholt werden. Dieser Vorgang nimmt Zeit in Anspruch, und wenn solche Abrufe häufig erfolgen, müssen die Speicherseiten im Cache ständig ersetzt werden -> Cache-Misses -> Cache ist nicht effizient. ArrayList Elemente werden in einem kontinuierlichen Speicher gespeichert - und das ist genau das, wofür die moderne CPU-Architektur optimiert ist.

2. Sekundäres LinkedList erforderlich, um Rückwärts-/Vorwärtszeiger zu halten, was den dreifachen Speicherverbrauch pro gespeichertem Wert bedeutet im Vergleich zu ArrayList .

DynamicIntArray ist übrigens eine eigene ArrayList-Implementierung, die Int (primitiver Typ) und nicht Objekte - daher werden alle Daten wirklich nebeneinander gespeichert, was noch effizienter ist.

Ein Schlüsselelement, das man sich merken 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 das Lesen von 1 MB sequentiellem Speicher 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 die Sache noch deutlicher zu machen, prüfen Sie bitte den Benchmark für das Hinzufügen von Elementen am Anfang der Liste. Dies ist ein Anwendungsfall, bei dem theoretisch die LinkedList sollte wirklich glänzen, und ArrayList sollten schlechte oder sogar schlechtere Ergebnisse aufweisen:

Hinweis: Dies ist ein Benchmark der C++ Std lib, aber meine bisherigen Erfahrungen zeigen, dass die Ergebnisse in C++ und Java sehr ähnlich sind. Quellcode

Das Kopieren einer sequentiellen Speichermenge ist ein Vorgang, der von den modernen CPUs optimiert wurde - was wiederum die Theorie und die Praxis verändert, ArrayList / Vector wesentlich effizienter

---

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