Wenn LinkedList über Arraylist in Java zu benutzen?

StackOverflow https://stackoverflow.com/questions/322715

Frage

Ich habe immer gewesen, einfach verwenden: 

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

ich die Schnittstelle als Typnamen verwenden für Portabilität , so dass, wenn ich Fragen wie diese fragen kann ich meinen Code überarbeiten.

Wann sollte LinkedList verwendet werden über ArrayList und umgekehrt?

War es hilfreich?

Lösung

Zusammenfassung ArrayList mit ArrayDeque bevorzugt in viele mehr Anwendungsfälle als LinkedList. Wenn Sie nicht sicher sind, -. Nur mit ArrayList starten

LinkedList und ArrayList sind zwei verschiedene Implementierungen der Liste Schnittstelle. LinkedList implementiert es mit einer doppelt verketteten Liste. ArrayList setzt sie mit einem dynamisch Neudimensionierung Array.

Wie bei Standard verknüpften Liste und Array-Operationen werden die verschiedenen Methoden verschiedene algorithmische Runtimes haben.

LinkedList<E>

  • get(int index) ist O (n) (mit n / 4 Schritten im Durchschnitt)
  • add(E element) ist O (1)
  • add(int index, E element) ist O (n) (mit n / 4 Schritten im Durchschnitt), aber O (1) , wenn index = 0 <--- Hauptvorteil von LinkedList<E>
  • remove(int index) ist O (n) (mit n / 4 Schritten im Durchschnitt)
  • Iterator.remove() ist O (1) . <--- Hauptvorteil von LinkedList<E>
  • ListIterator.add(E element) ist O (1) Dies ist einer der wichtigsten Vorteile von LinkedList<E>

Hinweis: Viele der Operationen benötigen n / 4 Schritte im Durchschnitt Konstante Anzahl der Schritte im besten Fall (zB index = 0), und n / 2 Schritte im schlimmsten Fall (Mitte Liste)

ArrayList<E>

  • get(int index) ist O (1) <--- Hauptvorteil von ArrayList<E>
  • add(E element) ist O (1) abgeschrieben, aber O (n) worst-case da das Array muss der Größe verändert und kopiert werden
  • add(int index, E element) ist O (n) (mit n / 2 Schritten im Durchschnitt)
  • remove(int index) ist O (n) (mit n / 2 Schritten im Durchschnitt)
  • Iterator.remove() ist O (n) (mit n / 2 Schritten im Durchschnitt)
  • ListIterator.add(E element) ist O (n) (mit n / 2 Schritten im Durchschnitt)

Hinweis: Viele der Operationen benötigen n / 2 Schritte im Durchschnitt Konstante Anzahl der Schritte im besten Fall (Ende der Liste), n Schritte im schlimmsten Fall (Anfang der Liste)

LinkedList<E> ermöglicht konstante Zeit Einfügungen oder Umzüge mit Iteratoren , aber nur mit sequenziellem Zugriff von Elementen. Mit anderen Worten, können Sie die Liste vorwärts oder rückwärts zu gehen, aber eine Position in der Liste zu finden, brauchen Zeit proportional zur Größe der Liste. Javadoc sagt "Operationen, den Index in die Liste wird die Liste vom Anfang oder am Ende durchquert je nachdem, was näher ist" , so dass diese Methoden sind O (n) ( n / 4 Stufen) im Durchschnitt, obwohl O (1) für index = 0.

ArrayList<E>, auf der anderen Seite, ermöglichen eine schnellen zufälligen Lesezugriff, so dass Sie jedes Element in konstanter Zeit greifen können. Aber das Hinzufügen oder Entfernen von überall aber das Ende erfordert Verschiebung all letzteren Elemente über, entweder, um eine Öffnung zu machen oder um die Lücke zu füllen. Auch, wenn Sie mehr Elemente als die Kapazität des zugrunde liegenden Array hinzufügen, wird ein neues Array (die 1,5-fache der Größe) zugeordnet, und die alte Array wird auf den neuen kopiert, so dass das Hinzufügen zu einem ArrayList ist O (n ) im schlimmsten Fall aber konstant im Durchschnitt.

So abhängig von den Operationen, die Sie tun möchten, sollten Sie die Implementierungen entsprechend wählen. Iterieren jede Art von Liste ist praktisch gleich billig. (Iterieren über eine ArrayList ist technisch schneller, aber wenn man etwas wirklich leistungs empfindlich tun, sollten Sie sich nicht kümmern -. Sie beide Konstanten sind)

Die wichtigsten Vorteile eines LinkedList Verwendung entstehen, wenn Sie wiederverwenden bestehende iterators einzufügen und Elemente zu entfernen. Diese Operationen können dann in O durchgeführt werden (1) durch die Liste nur lokal zu verändern. In einer Array-Liste, muss der Rest des Feldes sein bewegt (d kopiert). Auf der anderen Seite, in einem LinkedList sucht bedeutet die Links in O (n) ( n / 2 Stufen) für den ungünstigsten Fall, wohingegen in einer ArrayList die gewünschte Position kann mathematisch berechnet werden und der Zugriff in O (1) .

Ein weiterer Vorteil eine LinkedList der Verwendung entstehen, wenn Sie aus dem Kopf der Liste hinzuzufügen oder zu entfernen, da diese Operationen sind O (1) , während sie O (n) für ArrayList. Beachten Sie, dass ArrayDeque kann eine gute Alternative sein, um LinkedList für das Hinzufügen und aus dem Kopf zu entfernen, aber es ist kein List.

Auch wenn Sie große Listen haben, bedenken Sie, dass die Speichernutzung auch unterschiedlich ist. Jedes Element einer LinkedList hat mehr Aufwand, da Zeiger auf die nächsten und vorherigen Elemente werden ebenfalls gespeichert. ArrayLists haben diesen Aufwand nicht. Allerdings ArrayLists so viel Speicher benötigen als für die Kapazität zugeordnet ist, unabhängig davon, ob Elemente tatsächlich hinzugefügt.

Die Standardanfangskapazität eines ArrayList ziemlich klein ist (10 von Java 1,4-1,8). Da aber die zugrunde liegende Implementierung ein Array ist, muss das Array der Größe verändert werden, wenn Sie viele Elemente hinzufügen. Um die hohen Kosten für die Größenänderung zu vermeiden, wenn Sie wissen, dass Sie eine Menge Elemente hinzuzufügen, zu konstruieren die ArrayList mit einer höheren Anfangskapazität.

Andere Tipps

Bisher scheint niemand den Speicher zu haben Fußabdruck jeder dieser Listen neben dem allgemeinen Konsens angegangen, dass ein LinkedList ist „viel mehr“ als ein ArrayList so habe ich einige Zahlknirschens genau zu zeigen, wie viel beide Listen dauern, bis N null Referenzen.

Da Referenzen sind entweder 32 oder 64 Bits (selbst wenn null) auf ihren relativen Systemen I enthalten sind 4 Sätze von Daten für die 32 und 64-Bit-LinkedLists und ArrayLists.

Hinweis: Die Größen für die ArrayList Linien sind für gezeigt getrimmten Listen - In der Praxis ist die Kapazität der Trägermatrix in einem ArrayList im Allgemeinen größer ist als sein aktuelles Element zählen.

Hinweis 2: (dank BeeOnRope) Wie CompressedOops Standard nun ab Mitte JDK6 ist und nach oben, werden die Werte unterhalb von 64-Bit-Maschinen im Grunde ihre 32-Bit-Match Kollegen, es sei denn natürlich wenden Sie sich speziell ihn aus.

Graph von LinkedList und Arraylist Anzahl der Elemente x Bytes

Das Ergebnis zeigt deutlich, dass LinkedList eine ganze Menge mehr als ArrayList ist, vor allem mit einem sehr hohen Elementzählwert. Wenn der Speicher ein Faktor ist, meiden LinkedLists.

Die Formeln I Follow verwendet, lassen Sie mich wissen, ob ich etwas falsch gemacht haben, und ich werde es reparieren. ‚B‘ entweder 4 oder 8 für die 32- oder 64-Bit-Systeme, und ‚n‘ die Anzahl der Elemente. Hinweis der Grund für die Mods ist, weil alle Objekte in Java ein Vielfaches von 8 Bytes Platz in Anspruch nehmen, unabhängig davon, ob es verwendet wird 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 das, was Sie wollen. LinkedList ist fast immer ein (Performance) Fehler.

Warum LinkedList saugt:

  • Es nutzt viele kleine Speicherobjekte und damit Auswirkungen Leistung in den Prozess einzubeziehen.
  • Viele kleine Objekte sind schlecht für Cache-Lokalität.
  • Jede indizierte Operation erfordert eine traversal, d.h. aufweist O (n) Leistung. Dies ist nicht offensichtlich im Quellcode, die führende O (n) Algorithmen langsamer als wenn ArrayList verwendet wurde.
  • gute Leistung zu erhalten ist schwierig.
  • Auch wenn Big-O-Leistung die gleichen wie ArrayList ist, ist es wahrscheinlich deutlich langsamer sowieso zu gehen.
  • Es ist schrill LinkedList in Quelle zu sehen, weil es wahrscheinlich die falsche Wahl ist.

Als jemand, der seit etwa einem Jahrzehnt auf sehr großem Maßstab SOA Web Services operativen Performance Engineering zu tun hat, würde ich das Verhalten von LinkedList über Arraylist bevorzugen. Während der Steady-State-Durchsatz von LinkedList schlechter ist und daher mehr Hardware zu kaufen führen könnte - das Verhalten von Arraylist unter Druck könnte zu Anwendungen in einem Cluster führt ihre Felder in der Nähe von Synchronizität und für große Feldgrößen erweitert Mangel an Reaktions führen könnte in der App und ein Ausfall, während sie unter Druck, was katastrophales Verhalten ist.

Ebenso können Sie einen besseren Durchsatz in einer App aus dem Standard-Durchsatz tenured Garbage Collector zu bekommen, aber wenn Sie Java ™ -Anwendungen erhalten mit 10GB häuft Sie die App für 25 Sekunden während einer Voll GCs, die Timeouts und Ausfälle verursacht Perren aufwickeln kann in SOA-Apps und bläst Ihre SLAs, wenn es zu oft auftritt. Auch wenn die CMS Sammler mehr Ressourcen brauchen und nicht den gleichen rohen Durchsatz nicht erreicht, es ist eine viel bessere Wahl, weil es berechenbare und kleinere Latenz hat.

Arraylist ist nur eine bessere Wahl für Leistung, wenn alles, was Sie durch Leistung bedeuten Durchsatz und Sie können Latenz ignorieren. Nach meiner Erfahrung in meinem Job kann ich nicht Worst-Case-Latenz ignorieren. 

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Algorithmen: Big-Oh Notation

Arraylists sind gut für write-once-read-many oder Appen, aber schlecht Hinzufügen / Entfernen von vorne oder in der Mitte.

Ja, ich weiß, dies ist eine alte Frage, aber ich werde in meinen zwei Cent werfen:

LinkedList ist fast immer die falsche Wahl, Performance-weise. Es gibt einige sehr spezifische Algorithmen, wo ein LinkedList für genannt wird, aber die sind sehr, sehr selten, und der Algorithmus wird in der Regel spezifisch sind abhängig von LinkedList Fähigkeit Elemente in der Mitte der Liste relativ schnell einfügen und löschen, wenn Sie dort gesteuert haben mit einem ListIterator.

Es gibt einen gemeinsamen Anwendungsfall, in der LinkedList Arraylist übertrifft: die eine Warteschlange. Allerdings, wenn Ihr Ziel ist die Leistung, statt LinkedList Sie auch eine ArrayBlockingQueue in Betracht ziehen sollten (falls Sie eine Obergrenze für die Warteschlange Größe vor der Zeit bestimmen kann, und sich leisten können, den gesamten Speicher vorne zuzuteilen), oder das CircularArrayList Implementierung . (Ja, es ist aus dem Jahr 2001, so dass Sie es generify brauchen werden, aber ich habe eine vergleichbare Leistung Verhältnisse zu dem, was in dem Artikel zitiert ist gerade jetzt in einer aktuellen JVM)

Es ist eine Effizienz Frage. LinkedList ist schnell zum Hinzufügen und Löschen von Elementen, aber langsam ein bestimmtes Element zuzugreifen. ArrayList ist schnell für ein bestimmtes Element zugreifen, kann aber langsam zu einem Ende hinzuzufügen, und besonders langsam in der Mitte zu löschen.

Array vs vs LinkedList Arraylist vs Vector mehr in die Tiefe geht, wie auch verlinkte Liste .

richtig oder falsch: Bitte führen Sie Test vor Ort und für sich selbst entscheiden

Bearbeiten / Entfernen ist schneller in LinkedList als ArrayList.

ArrayList, durch Array gesichert, die doppelt so groß sein muss, ist schlimmer in großvolumige Anwendung.

Im Folgenden wird das Gerät Tester für jeden operation.Timing wird in Nanosekunden angegeben. 

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 im Wesentlichen ein Array. LinkedList als doppelt verkettete Liste implementiert.

Die get ist ziemlich klar. O (1) für ArrayList, weil ArrayList random access erlauben durch Index. O (n) für LinkedList, denn es muss zuerst den Index finden. Hinweis: Es gibt verschiedene Versionen von add und remove.

LinkedList ist schneller in hinzuzufügen und zu entfernen, aber langsamer in get. Kurz gesagt, LinkedList bevorzugt, wenn sein sollte:

  1. gibt es keine große Anzahl von Direktzugriff des Elements
  2. gibt es eine große Anzahl von Add / Remove Operationen

=== Arraylist ===

  • add (E e)
    • am Ende der Arraylist hinzufügen
    • erfordern Speicher Redimensionierung Kosten.
    • O (n) am schlechtesten, O (1) abgeschrieben
  • add (int index, E-Element)
    • in der eine bestimmten Indexposition
    • erfordert Verschiebung & mögliche Speicher Ändern der Größe Kosten
    • O (n)
  • entfernen (int index)
    • entfernen, um ein bestimmtes Element
    • erfordert Verschiebung & mögliche Speicher Ändern der Größe Kosten
    • O (n)
  • entfernen (Object o)
    • entfernen Sie das erste Vorkommen des angegebenen Elements aus dieser Liste
    • müssen zuerst das Element suchen, und dann Verschieben & mögliche Speicher Ändern der Größe Kosten
    • O (n)

=== LinkedList ===

  • add (E e)

    • bis zum Ende der Liste hinzufügen
    • O (1)

  • add (int index, E-Element)

    • Einsatz bei bestimmten Position
    • müssen die Position finden erste
    • O (n)
  • remove ()
    • entfernt erstes Element der Liste
    • O (1)
  • entfernen (int index)
    • entfernen Element mit dem angegebenen Index
    • braucht das Element zu finden ersten
    • O (n)
  • entfernen (Object o)
    • entfernen Sie das erste Vorkommen des angegebenen Elements
    • braucht das Element zu finden ersten
    • O (n)

Hier ist eine Figur von programcreek.com (add und remove sind der erste Typ, dh ein Element am Ende der Liste hinzu, und das Element an der angegebenen Position in der Liste entfernen.):

eingeben Bild Beschreibung hier

Joshua Bloch, der Autor von LinkedList:

  

Hat jemand tatsächlich LinkedList benutzen? Ich habe es geschrieben, und ich habe es nie verwenden.

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

Ich bin für die Antwort leid wie die anderen Antworten nicht so informativ, aber ich dachte, es wäre das interessanteste und selbsterklärend sein.

ArrayList ist zufällig zugänglich, während LinkedList wirklich billig zu erweitern und entfernen Elemente aus. In den meisten Fällen ArrayList ist in Ordnung.

Wenn Sie große Listen und gemessen, um einen Engpass erstellt haben, werden Sie wahrscheinlich nie über den Unterschied kümmern.

Wenn Ihr Code hat add(0) und remove(0), verwenden Sie einen LinkedList und es ist schöner addFirst() und removeFirst() Methoden. Andernfalls verwendet ArrayList.

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

Ich weiß, das ist eine alte Post, aber ich kann ehrlich nicht glauben, dass niemand erwähnt, dass LinkedList Deque implementiert. Schauen Sie sich die Methoden in Deque (und Queue); wenn Sie einen fairen Vergleich wollen, versuchen Sie laufen LinkedList gegen ArrayDeque und tun ein Feature-for-Feature-Vergleich.

Hier ist die Big-O-Notation sowohl ArrayList und LinkedList und auch CopyOnWrite-ArrayList:

Arraylist 

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)

Copy-On-Write-Arraylist 

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Auf dieser Grundlage müssen Sie entscheiden, was zu wählen. :)

TL; DR durch moderne Computerarchitektur wird ArrayList deutlich effizienter sein für nahezu alle möglichen Anwendungsfall - und deshalb sollte LinkedList mit Ausnahme einiger sehr einzigartig und extremen Fällen vermieden werden

Theoretisch VerketteteListe hat einen O (1) für die add(E element)

Auch in der Mitte einer Liste ein Element hinzugefügt werden, sollte sehr effizient sein.

Die Praxis ist sehr unterschiedlich, wie LinkedList eine ist Cache Hostile Datenstruktur. Aus Performance POV - es gibt nur sehr wenig Fälle, in denen LinkedList eine bessere Leistung als die sein könnte Cache freundlich ArrayList

.

Hier sind Ergebnisse eines Benchmark-Tests Einlegeelemente in zufälligen Stellen. Wie Sie sehen können - die Array-Liste, wenn viel effizienter, obwohl theoretisch jeder Einsatz in der Mitte der Liste erfordert „move“ die n später Elemente des Arrays (niedrigere Werte sind besser):

image description hier

Die Arbeit an einer späteren Generation Hardware (größere, effizientere Caches) - die Ergebnisse sind noch schlüssig:

image description hier

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

Es gibt zwei Hauptgründe dafür:

  1. Hauptsächlich -, dass die Knoten des LinkedList sind zufällig über den Speicher verstreut. RAM ( „Random Access Memory“) ist nicht wirklich zufällig und Speicherblöcke müssen geholt Cache sein. Dieser Vorgang dauert seine Zeit, und wenn eine solche Fetches häufig geschehen - die Speicherseiten im Cache müssen die ganze Zeit ersetzt werden -> Cache-Misses -> Cache nicht effizient ist. ArrayList Elemente sind auf Dauerspeicher gespeichert -. das ist genau das, was die moderne CPU-Architektur für optimiert

  2. Sekundär 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 kundenspezifische Implementierung Arraylist Halte Int (Urtyp) und nicht Objekte - also alle Daten wirklich nebeneinander gespeichert ist -. damit noch effizienter

Ein Schlüsselelemente zu erinnern ist, dass die Kosten für Speicherblock zu holen, wichtiger als die Kosten ist es, eine einzelne Speicherzelle zugreift. Deshalb Leser 1MB sequentiellen Speicher ist bis zu x400-mal schneller als diese Menge an Daten aus verschiedenen Speicherblöcken zu lesen: 

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: Latency Zahlen sollten jeder Programmierer wissen

Nur der Punkt noch deutlicher zu machen, benutzen Sie bitte den Maßstab von Hinzufügen von Elementen zu Beginn der Liste überprüfen. Dies ist ein Anwendungsfall, wo in-Theorie sollte die LinkedList wirklich glänzen, und ArrayList sollte arm oder noch schlimmer-Case-Ergebnisse vor:

image description hier

Hinweis: Dies ist ein Maßstab für den C ++ Std lib, aber meine bisherigen Erfahrungen der C ++ und Java Ergebnisse sind sehr ähnlich gezeigt. Source Code

ein sequentielles Großteil der Speicher Kopieren ist ein operation durch die moderne CPUs optimiert - Theorie verändert und tatsächlich machen, wieder ArrayList / Vector viel effizienter

Credits: Alle hier gepostet Benchmarks erstellt von Kjell Hedström . Auch können mehr Daten auf seinem Blog gefunden werden

Lassen Sie uns LinkedList und Arraylist w.r.t. vergleichen unter Parametern:

1. Die Umsetzung

  

Arraylist ist die veränderbare Array Umsetzung der Liste Schnittstelle, während

     

LinkedList ist die doppelt verknüpfte Liste Implementierung der Liste Schnittstelle.

2. Performance

  • get (int index) oder Suchoperation

      

    Arraylist get (int index) Betrieb läuft in konstanter Zeit d.h O (1), während

         

    LinkedList get (int index) Betrieb Laufzeit ist O (n).

    Der Grund für Arraylist ist schneller als LinkedList ist, dass Arraylist verwendet einen Index-basiertes System für seine Elemente, da sie eine Array-Datenstruktur intern verwendet, auf der anderen Seite,

    LinkedList bietet keine Index-basierten Zugriff für seine Elemente, wie es entweder vom Anfang oder Ende iteriert (je nachdem, was näher ist), um den Knoten auf dem angegebenen Element-Index abzurufen.

  • insert () oder hinzufügen (Object) Betrieb

      

    Einfügungen in LinkedList ist in der Regel schnell zu Arraylist zu vergleichen. In VerketteteListe Hinzufügen oder Einsetzen O (1) Betrieb.

         

    Während in Arraylist , wenn das Array ist der volle dh schlimmste Fall gibt es ein extra Kosten für die Größenänderung Array und das Kopieren Elemente in das neue Array, das in Arraylist O Laufzeit von Addierungsoperation macht ( n), ansonsten ist es O (1).

  • entfernen (int) Betrieb

    Entfernen Betrieb in VerketteteListe ist im Allgemeinen der gleiche wie Array d O (n).

      

    In LinkedList , gibt es zwei überladene entfernen Methoden. ist () ohne Parameter entfernen, die den Kopf der Liste entfernt und laufen in konstanter Zeit O (1). Die andere Methode in überlasteten remove VerketteteListe ist (int) entfernen oder entfernen (Objekt), die das Objekt oder int als Parameter übergibt entfernt. Diese Methode durchläuft den LinkedList, bis er den Gegenstand und entkoppeln sie aus der ursprünglichen Liste gefunden. Daher ist diese Methode der Laufzeit ist O (n).

         

    Während in Arraylist entfernen (int) -Methode Kopieren Elemente aus dem alten Array beinhaltet, um neuen, aktualisierte Array, daher die Laufzeit ist O (n).

3. Reverse-Iterator

  

LinkedList in umgekehrter Richtung mit descendingIterator (), während

wiederholt werden      

gibt es keinen descendingIterator () in Arraylist , so müssen wir unseren eigenen Code schreiben, über die Arraylist in umgekehrter Richtung zu durchlaufen.

4. Anfangskapazität

  

Wenn der Konstruktor nicht überlastet ist, dann Arraylist erstellt eine leere Liste der anfänglichen Kapazität 10, während

     

LinkedList nur konstruiert die leere Liste ohne Anfangskapazität.

5. Arbeitsspeicher-Overhead

  

Speicher-Overhead in LinkedList ist mehr als zu Arraylist verglichen als ein Knoten in LinkedList die Adressen des nächsten und vorherigen Knoten beibehalten muss. Während

     

In Arraylist jeder Index hält nur das eigentliche Objekt (Daten).

Quelle

Zusätzlich zu den anderen guten Argumenten oben, sollten Sie ArrayList Geräte RandomAccess Schnittstelle bemerken, während LinkedList Queue implementiert.

Also, irgendwie adressieren sie etwas anderen Probleme, mit Unterschied von Effizienz und Verhalten (die Liste der Methoden siehe).

Eine Array Liste ist im Wesentlichen ein Array mit Methoden Artikel hinzufügen usw. (und Sie sollten stattdessen eine generische Liste verwenden). Es ist eine Sammlung von Gegenständen, die durch einen Indexer zugegriffen werden kann (beispielsweise [0]). Es bedeutet eine Progression von einem Punkt zum nächsten.

Eine verkettete Liste gibt einen Übergang von einem Element zum nächsten (Punkt a -> Punkt b). Sie können den gleichen Effekt mit einer Array-Liste, aber eine verkettete Liste sagt absolut welche Artikel soll die vorherige folgen.

Es hängt davon ab, welche Operationen werden Sie mehr auf der Liste tun.

ArrayList ist schneller auf einen indizierten Wert zuzugreifen. Es ist viel schlimmer, wenn das Einfügen oder Löschen von Objekten.

Um mehr zu erfahren, lesen Sie alle Artikel, die zwischen Arrays und verkettete Listen über den Unterschied spricht.

Normalerweise verwende ich einen über den anderen auf der Grundlage der Zeit Komplexität der Operationen, die ich auf dieser bestimmten Liste durchführen würde. 

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|

Ein wichtiges Merkmal einer verknüpften Liste (die ich nicht in einer anderen Antwort gelesen habe) ist die Verkettung von zwei Listen. Mit einer Anordnung ist das O (n) (+ Overhead von einigen Umschichtungen) mit einer verknüpften Liste ist dies nur O (1) oder O (2); -)

Wichtig : Für Java seine LinkedList das ist nicht wahr! Siehe Gibt es eine schnelle concat Methode für verkettete Liste in Java?

Ich habe die Antworten zu lesen, aber es gibt ein Szenario, in dem ich immer einen LinkedList über eine Arraylist verwenden, die ich teilen mögen Meinungen zu hören:

Jedes Mal, wenn ich eine Methode hatte, das eine Liste von Daten aus einer DB erhalten wieder verwende ich immer eine LinkedList.

Meine Begründung war, dass, weil es unmöglich ist, genau zu wissen, wie viele Ergebnisse sind ich immer, wird es (wie in Arraylist mit der Differenz zwischen der Kapazität und den tatsächlichen Anzahl der Elemente), und es gäbe keine Zeit keinen Speicher verschwendet werden vergeudet versucht, die Kapazität zu verdoppeln.

Für eine Arraylist, ich stimme, dass zumindest sollte man immer den Konstruktor mit der Anfangskapazität, verwenden Sie die Vervielfältigung der Arrays so weit wie möglich zu minimieren.

Arraylist und LinkedList haben ihre eigenen Vor- und Nachteile.

Array verwendet zusammenhängende Speicheradresse zu VerketteteListe verglichen, den Zeiger zu dem nächsten Knoten verwendet. Also, wenn Sie ein Element in einem Arraylist nachschlagen mögen schneller als n Iterationen mit LinkedList tun.

Auf der anderen Seite, Einfügen und Löschen in einem LinkedList sind viel einfacher, weil Sie müssen nur die Zeiger ändern, während eine Arraylist die Verwendung von Schichtbetrieb für jede Einfügen oder Löschen bedeutet.

Wenn Sie häufig Auslagerungen in Ihrer Anwendung haben eine Arraylist verwenden. Wenn Sie häufig das Einfügen und Löschen haben verwenden, um eine LinkedList.

ArrayList und LinkedList beiden implementiert List interface und ihre Methoden und Ergebnisse sind fast identisch. Allerdings gibt es nur wenige Unterschiede zwischen ihnen, die über einen anderen besser machen je nach Anforderung.

Arraylist Vs LinkedList

1) Search: ArrayList Suchoperation ziemlich schnell an die LinkedList Suchoperation verglichen. get(int index) in ArrayList gibt die Leistung von O(1) während LinkedList Leistung O(n) ist.

Reason: ArrayList unterhält für seine Elemente indexbasierte System, wie es Array-Datenstruktur verwendet implizit die es schneller macht ein Element in der Liste für die Suche. Auf der anderen Seite LinkedList Arbeitsgeräte Liste doppelt verbunden, die für die Suche ein Element der Traversal durch alle Elemente erfordert.

2) Deletion: LinkedList Entfernungsoperation gibt O(1) Leistung während ArrayList variable Leistung gibt. O(n) im schlimmsten Fall (während der ersten Element zu entfernen) und O(1) in bestem Fall (beim letzten Elemente zu entfernen)

  

Fazit: LinkedList Element Löschung ist schneller im Vergleich zu   Arraylist.

Grund: LinkedList ist jedes Element zwei Zeiger (Adressen) unterhält, die zu den beiden Nachbarelementen in der Liste verweist. Daher erfordert die Entfernung einzige Änderung in der Zeigerposition in den beiden Nachbarknoten (Elemente) des Knotens, der entfernt werden soll. Während in Arraylist alle Elemente verschoben werden müssen, den Raum durch entfernte Element erstellt auszufüllen.

3) Inserts Performance: LinkedList add-Methode gibt O(1) Leistung während ArrayList gibt O(n) im schlimmsten Fall. Grund ist der gleiche wie für entfernen erläutert.

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

hält
  

daher auch der Speicherverbrauch hoch in LinkedList vergleichsweise.

Es gibt nur wenige Ähnlichkeiten zwischen diesen Klassen, die sich wie folgt dar:

  • Sowohl Arraylist und LinkedList ist Implementierung von List-Schnittstelle.
  • Sie halten sowohl die Elemente Anzeigenauftrag, was bedeutet, während der Anzeige von Arraylist und LinkedList Elemente, die die Ergebnismenge die gleiche Reihenfolge aufweisen würde, in der die Elemente in die Liste eingefügt wurde.
  • Beide Klassen sind nicht synchronisiert und können mit Collections.synchronizedList Methode explizit gemacht werden synchronisiert.
  • Die iterator und listIterator von diesen Klassen zurück fail-fast sind (wenn Liste strukturell jederzeit geändert wird, nachdem der Iterator, außer durch das iterator’s eigene entfernen in irgendeiner Weise erstellt oder Methoden hinzufügen, wird throw der Iterator ein ConcurrentModificationException).

Wenn LinkedList zu verwenden und wenn Arraylist verwenden?

  • Wie oberhalb dem Einsatz erklärt und entfernen Operationen geben gute Leistung (O(1)) in LinkedList im Vergleich zu ArrayList(O(n)).
      

    So, wenn es eine Anforderung der häufigen Hinzufügen und Löschen in Anwendung dann LinkedList ist eine beste Wahl.

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

    Also, wenn es weniger hinzufügen und Operationen und mehr Suchoperationen Anforderung entfernen, Arraylist wäre die beste Wahl.

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

Operationen dieser Index in die Liste wird die Liste vom Anfang oder am Ende durchquert je nachdem, was näher an den angegebenen Index.

1) Basiswert Datenstruktur

Der erste Unterschied zwischen Arraylist und LinkedList kommt mit der Tatsache, dass Arraylist von Array unterstützt wird, während LinkedList von LinkedList unterstützt wird. Dies wird zu einer weiteren Unterschiede in der Leistung führen.

2) LinkedList implementiert Deque

Ein weiterer Unterschied zwischen Arraylist und LinkedList ist, dass abgesehen von der Liste Schnittstelle, LinkedList implementiert auch Deque-Schnittstelle, die erste für Add in first out Operationen liefert () und poll () und mehrere andere Deque Funktionen. 3) Hinzufügen von Elementen in Array Addierelement in Arraylist ist O (1) Betrieb, wenn es nicht wieder Größe Array auslöst, wobei in diesem Fall wird es O (log (n)), andererseits ein Element in Anfügen LinkedList ist O (1) Betrieb, da es keine Navigation erforderlich ist.

4) Entfernen eines Elements aus einer Position

Um ein Element aus einem bestimmten Index zu entfernen, z.B. durch Entfernen Aufruf (Index), führt Array einen Kopiervorgang, der es in der Nähe O (n) durchführt, während VerketteteListe zu diesem Punkt zu durchqueren muss, das O macht es auch (n / 2), wie sie aus beiden Richtungen auf proximitätsbasierte durchqueren können .

5) Iterieren über Arraylist oder LinkedList

Iteration ist O (n) Betrieb für beide LinkedList und Array wobei n eine Nummer eines Elements ist.

6) Suchen Element aus einer Position,

Die get (Index) Operation ist O (1) in Arraylist, während seine O (n / 2) in LinkedList, da es bis zu diesem Eintrag zu durchqueren muss. Obwohl in Big O-Notation O (n / 2) ist nur O (n), weil wir Konstanten dort ignorieren.

7) Speicher

LinkedList verwendet ein Wrapper Objekt, eintritt, die eine statische geschachtelte Klasse ist für Daten und zwei Knoten nächsten und vorherigen während Array nur speichert Daten in Array speichert.

So Speicherbedarf scheint weniger im Fall von Arraylist als LinkedList außer für den Fall, dass Array die Operation der Größe neu durchführt, wenn es kopiert Inhalt von einem Array zu einem anderen.

Wenn Array groß genug ist es an diesem Punkt und Trigger-Garbage-Collection viel Speicher in Anspruch nehmen, die Reaktionszeit verlangsamen kann.

Von allen oben genannten Unterschiede zwischen Arraylist vs LinkedList, Es sieht Arraylist ist die bessere Wahl als LinkedList in fast allen Fällen, außer wenn Sie tun, um eine häufige add () Betrieb als remove () oder get ().

Es ist einfacher, eine verkettete Liste als Arraylist zu ändern, vor allem, wenn Sie Elemente von Anfang oder Ende sind das Hinzufügen oder Entfernen, da verkettete Liste intern Referenzen dieser Positionen hält und sie sind zugänglich in O (1) Zeit.

Mit anderen Worten: Sie müssen nicht durch die Liste zu durchqueren, die Position zu erreichen, in dem Sie Elemente hinzufügen möchten, in diesem Fall zusätzlich wird O (n) -Operation. Zum Beispiel das Einfügen oder ein Element in der Mitte einer verknüpften Liste zu löschen.

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

Sowohl remove () und Einsatz () eine Laufzeiteffizienz von O (n), die beide für die Arraylisten und LinkedLists. Allerdings kommt der Grund für die lineare Bearbeitungszeit von zwei sehr unterschiedlichen Gründen:

In einer Arraylist, die Sie das Element in O erhalten (1), aber eigentlich das Entfernen oder Einfügen von etwas macht es O (n), weil alle folgenden Elemente müssen geändert werden.

In einer LinkedList, dauert es O (n), um tatsächlich zu dem gewünschten Elemente zu erhalten, weil wir ganz am Anfang beginnen müssen, bis wir den gewünschten Index erreichen. Eigentlich Entfernen oder Einsetzen konstant ist, weil wir nur 1 Bezug ändern müssen für remove () und 2 Referenzen für insert ().

Welche der beiden ist schneller zum Einsetzen und Entfernen hängt davon ab, wo es passiert. Wenn wir näher am Anfang sind, werden die LinkedList schneller sein, weil wir durch relativ wenige Elemente gehen. Wenn wir näher am Ende sind, wird eine Arraylist schneller sein, weil wir es in konstanter Zeit bekommen und müssen nur die wenigen verbleibenden Elemente ändern, die ihm folgen. Wenn der LinkedList genau in der Mitte getan wird schneller sein, weil n Elemente gehen durch schneller ist als n Werte bewegen.

Bonus: Zwar gibt es keine Möglichkeit, diese beiden Methoden O zur Herstellung (1) für eine Arraylist, gibt es eigentlich eine Möglichkeit, dies in LinkedLists zu tun. Lassen Sie uns sagen, dass wir durch die gesamte Liste hinwollen entfernen und Elemente auf dem Weg stecken. Normalerweise würden Sie von Anfang an für jedes Element starten Sie den LinkedList verwenden, könnten wir auch „Speichern“ das aktuelle Element wir arbeiten mit einem Iterator. Mit Hilfe des Iterator, erhalten wir eine O (1) Effizienz für remove () und insert (), wenn sie in einer LinkedList arbeiten. So dass es die einzige Leistungsvorteil Ich bin mir dessen bewusst, wo ein LinkedList ist immer besser als eine Arraylist.

Arraylist erweitert AbstractList und implementiert die Liste Schnittstelle. Arraylist ist dynamisches Array.
kann gesagt werden, dass es im Grunde, die Nachteile der Anordnungen erstellt wurde zu überwinden
Die LinkedList-Klasse erweitert AbstractSequentialList und implementiert Liste, Deque und Queue-Schnittstelle. -leistung
arraylist.get() ist O (1), während linkedlist.get() ist O (n)
arraylist.add() O (1) und linkedlist.add() 0 (1)
arraylist.contains() ist O (n) andlinkedlist.contains() ist O (n)
arraylist.next() O (1) und linkedlist.next() ist O (1)
arraylist.remove() ist O (n), während linkedlist.remove() O (1) ist
In Array
iterator.remove() ist O (n)
während in VerketteteListe
iterator.remove()is O (1)

Einer der Tests, die ich hier gesehen führt den Test nur einmal. Aber was ich habe bemerkt, ist, dass man diese Tests oft ausgeführt werden müssen und schließlich werden ihre Zeiten zusammenlaufen. Grundsätzlich muss die JVM, um sich aufzuwärmen. Für meinen speziellen Anwendungsfall brauchte ich zum Hinzufügen / Entfernen von Elementen zu einem letzten, die auf etwa 500 Gegenstände wächst. In meinen Tests LinkedList schneller herauskommen, mit verknüpften LinkedList in rund 50.000 NS kommen und ArrayList bei rund 90.000 NS kommt in ... geben oder nehmen. Sehen Sie 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;
}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top