Leistungsunterschiede zwischen ArrayList und LinkedList

https://stackoverflow.com//questions/10656471

11-12-2019
|

Frage

Ja, das ist ein altes Thema, aber ich habe immer noch einige Verwirrungen.

In Java sagt man:

ArrayList ist schneller als LinkedList, wenn ich zufällig auf seine Elemente zugreife.Ich denke, Direktzugriff bedeutet „Gib mir das n-te Element“.Warum ist ArrayList schneller?
LinkedList ist beim Löschen schneller als ArrayList.Ich verstehe das.ArrayList ist langsamer, da das interne Backup-Array neu zugewiesen werden muss.Eine Code-Erklärung:
```
List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.remove("b");
System.out.println(list.get(1)); //output "c"
```
LinkedList ist beim Einfügen schneller als ArrayList.Was bedeutet hier Einfügen?Wenn es darum geht, einige Elemente nach hinten zu verschieben und das Element dann an der mittleren leeren Stelle zu platzieren, sollte ArrayList langsamer sein als LinkedList.Wenn das Einfügen nur eine Add(Object)-Operation bedeutet, wie könnte das langsam sein?

Lösung

ArrayList ist schneller als LinkedList, wenn ich zufällig auf seine Elemente zugreife.Ich denke, Direktzugriff bedeutet „Gib mir das n-te Element“.Warum ist ArrayList schneller?

ArrayList hat direkte Verweise auf jedes Element in der Liste, sodass das n-te Element in konstanter Zeit abgerufen werden kann. LinkedList muss die Liste von Anfang an durchlaufen, um zum n-ten Element zu gelangen.

LinkedList ist beim Löschen schneller als ArrayList.Ich verstehe das.ArrayList ist langsamer, da das interne Backup-Array neu zugewiesen werden muss.

ArrayList ist langsamer, da ein Teil des Arrays kopiert werden muss, um den frei gewordenen Steckplatz zu entfernen.Wenn das Löschen mit der erfolgt ListIterator.remove() API, LinkedList muss nur ein paar Referenzen manipulieren;ob die Löschung nach Wert oder nach Index erfolgt, LinkedList Möglicherweise muss zuerst die gesamte Liste durchsucht werden, um die zu löschenden Elemente zu finden.

Wenn das bedeutet, dass einige Elemente nach hinten verschoben und das Element dann an der mittleren leeren Stelle platziert werden, sollte ArrayList langsamer sein.

Ja, das ist es, was es bedeutet. ArrayList ist in der Tat langsamer als LinkedList weil es einen Steckplatz in der Mitte des Arrays freimachen muss.Dies beinhaltet das Verschieben einiger Referenzen und im schlimmsten Fall die Neuzuweisung des gesamten Arrays. LinkedList Ich muss nur einige Referenzen manipulieren.

Andere Tipps

diese Antwort jetzt ignorieren. Die anderen Antworten, insbesondere der von aix , sind meistens korrekt. Im Laufe der Langzeit sind sie den Weg zur Wette. Und wenn Sie genügend Daten haben (auf einem Benchmark auf einer Maschine, schien es ungefähr eine Million Einträge zu sein) ArrayList und LinkedList funktionieren derzeit wie Werbung. Es gibt jedoch einige schöne Punkte, die sich im frühen 21. Jahrhundert anwenden.

Die moderne Computertechnologie scheint durch meine Prüfung eine enorme Kante in Arrays zu geben. Elemente eines Arrays können verschoben und bei verrückten Geschwindigkeiten kopiert werden. Infolgedessen werden Arrays und Arraylist in den meisten praktischen Situationen, in den meisten praktischen Situationen, die Linkedliste auf Einsätzen und Löschungen, oft dramatisch. Mit anderen Worten, Arraylist wird die Linkedlist in seinem eigenen Spiel schlagen.

Der Nachteil von ArrayList ist, dass es dient dazu neigt, nach dem Löschen auf dem Speicherplatz zu hängen, wobei LinkedList den Platz aufgibt, da er Einträge aufgibt.

der größere Nachtreiter von Arrays und ArrayList ist der Fragment-freie Speicher und überarbeiten den Müllsammler. Als Arraylist erweitert, erstellt es neue, größere Arrays, kopiert das alte Array an das neue, und fört den alten. Der Speicher füllt sich mit großen zusammenhängenden Brocken des freien Gedächtnisses, die für die nächste Zuteilung nicht groß genug sind. Schließlich gibt es keinen geeigneten Raum für diese Zuteilung. Obwohl 90% der Erinnerung frei ist, ist kein individuelles Stück groß genug, um den Job zu erledigen. Das GC wird dadurch verzweifelt arbeiten, um Dinge herumzuziehen, aber wenn es zu lange dauert, um den Raum neu zu ordnen, wird es eine OutofMemoryException werfen. Wenn es nicht aufgibt, kann es immer wieder das Programm nach unten verlangsamen.

Das Schlimmste ist, dass dieses Problem schwer vorherzusagen kann. Ihr Programm läuft einmal in Ordnung. Dann, mit etwas weniger Speicher verfügbar, ohne Warnung, verlangsamt oder stoppt es.

Linkedlist verwendet kleine, zierliche Memory-Bits und GCs Liebe. Es läuft immer noch gut, wenn Sie 99% Ihres verfügbaren Speicherplatzes verwenden. Verwenden Sie also im Allgemeinen Arraylist für kleinere Datensätze, die den größten Teil ihrer Inhalte nicht gelöscht haben, oder wenn Sie eine enge Kontrolle über die Schaffung und Wachstum haben. (Erstellen eines Arrayslisten, der 90% des Speichers verwendet und verwendet wird, ohne ihn für die Dauer des Programms zu füllen, ist in Ordnung. Erstellen und Befreiung von Arraylist-Instanzen, die 10% des Gedächtnisses verwenden, töten Sie. (oder eine Karte, wenn Sie einen zufälligen Zugriff benötigen). Wenn Sie sehr große Sammlungen haben (sagen Sie über 100.000 Elemente), keine Bedenken hinsichtlich des GC, und planen viele Einsätze und Löschungen und keinen zufälligen Zugang, führen Sie ein paar Benchmarks aus, um zu sehen, was schnellste ist.

Der ArrayList Klasse ist eine Wrapper-Klasse für ein Array.Es enthält ein inneres Array.

public ArrayList<T> {
    private Object[] array;
    private int size;
}

A LinkedList ist eine Wrapper-Klasse für eine verknüpfte Liste mit einem inneren Knoten zum Verwalten der Daten.

public LinkedList<T> {
    class Node<T> {
        T data;
        Node next;
        Node prev;
    }
    private Node<T> first;
    private Node<T> last;
    private int size;
}

Beachten Sie, dass der vorliegende Code verwendet wird, um zu zeigen, wie die Klasse aussehen könnte, nicht die tatsächliche Implementierung.Da wir wissen, wie die Umsetzung aussehen könnte, können wir die weitere Analyse durchführen:

ArrayList ist schneller als LinkedList, wenn ich zufällig auf seine Elemente zugreife.Ich denke, Direktzugriff bedeutet „Gib mir das n-te Element“.Warum ist ArrayList schneller?

Zugriffszeit für ArrayList:O(1).Zugriffszeit für LinkedList:An).

In einem Array können Sie mit auf jedes Element zugreifen array[index], während Sie in einer verknüpften Liste beginnend durch die gesamte Liste navigieren müssen first bis Sie das Element erhalten, das Sie benötigen.

LinkedList ist beim Löschen schneller als ArrayList.Ich verstehe das.ArrayList ist langsamer, da das interne Backup-Array neu zugewiesen werden muss.

Löschzeit für ArrayList:Zugriffszeit + O(n).Löschzeitpunkt für LinkedList:Zugriffszeit + O(1).

Die ArrayList muss alle Elemente verschieben array[index] Zu array[index-1] Beginnend mit dem zu löschenden Elementindex.Die LinkedList sollte bis zu diesem Element navigieren und dann diesen Knoten löschen, indem sie ihn von der Liste entkoppelt.

LinkedList ist beim Löschen schneller als ArrayList.Ich verstehe das.ArrayList ist langsamer, da das interne Backup-Array neu zugewiesen werden muss.

Einfügezeit für ArrayList:An).Einfügezeit für LinkedList:O(1).

Warum kann die ArrayList O(n) annehmen?Denn wenn Sie ein neues Element einfügen und das Array voll ist, müssen Sie ein neues Array mit größerer Größe erstellen (Sie können die neue Größe mit einer Formel wie 2 * Größe oder 3 * Größe / 2 berechnen).Die LinkedList fügt einfach einen neuen Knoten neben dem letzten hinzu.

Diese Analyse erfolgt nicht nur in Java, sondern auch in anderen Programmiersprachen wie C, C++ und C#.

Weitere Infos hier:

Beide () und Insert () haben eine Laufzeiteffizienz von o (n) für Arraylisten und Linkedlisten. Der Grund hinter der linearen Bearbeitungszeit stammt jedoch aus zwei sehr unterschiedlichen Gründen:

In einer Arraylist gelangen Sie mit dem Element in O (1), aber eigentlich das Entfernen oder Einsetzen von etwas macht es arbeitet, da alle folgenden Elemente geändert werden müssen.

In einer LinkedList nimmt es o (n), um tatsächlich zum gewünschten Element zu gelangen, da wir am Anfang beginnen müssen, bis wir den gewünschten Index erreichen. Entfernen oder Einfügen ist konstant, sobald wir dort gelangen, da wir nur 1 Referenz für Remove () und 2 Referenzen für Insert () ändern müssen.

Welcher der beiden ist schneller zum Einsetzen und Entfernen hängt davon ab, wo es passiert. Wenn wir an der Beginn näher sind, ist die Linkedliste schneller, da wir relativ wenige Elemente durchlaufen müssen. Wenn wir an dem Ende näher am Ende sind, ist eine Arrayliste schneller, da wir in ständiger Zeit dorthin gelangen und nur die wenigen verbleibenden Elemente ändern müssen, die ihm folgen.

Bonus: Während es keine Möglichkeit gibt, diese beiden Methoden o (1) für eine Arraylist zu machen, ist es tatsächlich eine Möglichkeit, dies in Linkedlisten zu tun. Nehmen wir an, wir wollen die gesamte Liste durchgehen und Elemente auf unserem Weg einfügen. Normalerweise beginnen Sie von Anfang an für jede Elemente mit der LinkedList, wir könnten auch das aktuelle Element "speichern", an denen wir mit einem Iterator arbeiten, "speichern". Mit Hilfe des Iterators erhalten wir eine O (1) Effizienz für Entfernen () und Insert (), wenn sie in einer LinkedList arbeiten. Ich bin der einzige Leistungsnutzen, dessen, woher ein LinkedList immer besser ist als eine Arraylist.

Arraylist

ArrayList ist die beste Wahl, wenn unsere häufige Operation ein Abrufvorgang ist.
ArrayList ist die schlechteste Wahl, wenn unser Betrieb in der Mitte ein Insertieren und Löschen in der Mitte ist, da intern mehrere Schichtvorgänge durchgeführt werden.
In ArrayList-Elemente werden in aufeinanderfolgenden Speicherplätzen gespeichert, somit wird der Abrufvorgang einfach.
linkedlist: -

Antwort auf 1: ArrayList verwendet ein Array unter der Haube.Das Zugriff auf ein Mitglied eines ArrayList-Objekts ist so einfach, wie er auf das Array auf dem bereitgestellten Index zugreifen kann, vorausgesetzt, der Index befindet sich innerhalb der Grenzen des Backing-Arrays.Eine Linkedliste muss durch seine Mitglieder iterieren, um zum n-ten Element zu gelangen.Das ist o (n) für eine Linkedliste, gegenüber O (1) für Arraylist.

In einer LinkedList haben die Elemente einen Bezug auf das Element vor und danach.In einer Arraylist ist die Datenstruktur nur ein Array.

Eine Linkedlist muss über n Elemente iterieren, um das n-ten Element zu erhalten.Eine Arraylist muss nur Element n des Backing-Arrays zurückgeben.
Das Backing-Array muss entweder für die neue Größe neu aufgerufen werden, und das über das gelöschte Element kopierte Array, nachdem das gelöschte Element aufgerückt werden muss, um den leeren Raum zu füllen.Eine LinkedList muss nur die vorherige Referenz auf das Element einstellen, nachdem das entfernte entfernte und die nächste Referenz auf dem Element vor dem entfernten Element nach dem entfernten Element nach dem entfernten Element entfernt ist.Länger zu erklären, aber schneller zu tun.
derselbe Grund wie Deletion hier.

Arraylist : ArrayList hat eine Struktur wie ein Array, es hat einen direkten Bezug auf jedes Element.Der Rendom-Zugriff ist also schnell in Arraylist.

linkedlist : In Linkedlist Für das Erhalten von NTH ELENNT müssen Sie die gesamte Liste durchqueren, dauert im Vergleich zu Arraylist Zeit.Jedes Element hat einen Link zu seinem vorherigen & Nest-Element, so dass das Deletion schnell ist.

arraylist: Die Arraylist-Klasse erweitert AbstractList und implementiert die Listenschnittstelle und die RandomAccess (Marker-Schnittstelle).ArrayList unterstützt dynamische Arrays, die nach Bedarf wachsen können. Es gibt uns erste Iteration über Elemente.

linkedlist: Eine LinkedList wird durch Indexposition wie Arraylist bestellt, mit der Ausnahme, dass die Elemente doppelt miteinander verknüpft sind.Mit dieser Verbindung können Sie neue Methoden (über das hinaus, was Sie von der Listenoberfläche abrufen) zum Hinzufügen und Entfernen von Anfang oder Ende, was eine einfache Wahl für die Implementierung eines Stapels oder Warteschlangens ermöglicht.Beachten Sie, dass eine Linkedliste langsamer als eine Arraylist, , aber es ist eine gute Wahl, wenn Sie ein schnelles Einfügen und Löschen benötigen. AB JAVA 5 ist die Linkedlist-Klasse, um die Java zu implementieren.util.queue-Schnittstelle.Somit unterstützt es nun die gängigen Warteschlangenmethoden: PEEK (), Umfrage () und Angebot ().

Ich möchte ihr eine zusätzliche Information über den Leistungsunterschied hinzufügen.

Wir wissen das bereits, weil ArrayList Die Umsetzung wird durch eine unterstützt Object[] Es unterstützt Direktzugriff und dynamische Größenänderung LinkedList Die Implementierung verwendet Verweise auf Head und Tail, um darin zu navigieren.Es verfügt über keine Direktzugriffsfunktionen, unterstützt aber auch die dynamische Größenänderung.

Das erste ist, dass Sie mit einer ArrayList sofort auf den Index zugreifen können, während Sie mit einer LinkedList die Objektkette entlang iterieren müssen.

Zweitens ist das Einfügen in ArrayList im Allgemeinen langsamer, da es wachsen muss, sobald Sie seine Grenzen erreichen.Es muss ein neues, größeres Array erstellt und die Daten vom Original kopiert werden.

Aber die interessante Sache ist das, wenn du Erstellen Sie eine ArrayList, die bereits groß genug ist Um alle Ihre Einfügungen unterzubringen, sind natürlich keine Array-Kopiervorgänge erforderlich.Das Hinzufügen geht sogar noch schneller als mit LinkedList, da LinkedList sich mit seinen Zeigern auseinandersetzen muss, während die große ArrayList den Wert nur auf den gegebenen Index setzt.

Weitere Informationen finden Sie hier Unterschiede zwischen ArrayList und LinkedList.

Selbst sie scheinen identisch zu sein (gleiche implementierte Inteface-Liste - Nicht-Thread-Safe), ergeben sie unterschiedliche Ergebnisse in Bezug auf die Leistung in der Hinzufügung / Löschung und den Suchzeiten und den Verbrauchsspeicher (Linkedlist verbraucht mehr).

Linkedlisten können verwendet werden, wenn Sie mit der Leistung O (1) ein starkes Einfügen / Deletion verwenden. Arraylisten können verwendet werden, wenn Sie direkte Zugriffsvorgänge mit Leistung O (1) verwenden,

Dieser Code kann von diesen Kommentaren eindeutig sein, und Sie können versuchen, Leistungsergebnisse zu verstehen.(Entschuldigung für Kesselscheibencode) generasacodicetagpre.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow