1.ArrayList implementiert eine Datenstruktur basierend auf dynamischen Arrays und LinkedList implementiert eine Datenstruktur basierend auf verknüpften Listen.
2. Für den wahlfreien Zugriff zum Abrufen und Festlegen ist ArrayList besser als LinkedList, da ArrayList zufällig positioniert werden kann, während LinkedList den Zeiger Schritt für Schritt auf den Knoten bewegen muss. (Denken Sie in Bezug auf Arrays und verknüpfte Listen)
3. Für das Hinzufügen und Entfernen von Neu- und Löschvorgängen ist LinedList vorteilhafter. Es muss nur der Zeiger geändert werden, während ArrayList Daten verschieben muss, um den Platz des gelöschten Objekts zu füllen.
ArrayList und LinkedList sind zwei Sammlungsklassen, die zum Speichern einer Reihe von Objektreferenzen verwendet werden. Beispielsweise können wir ArrayList verwenden, um eine Reihe von Zeichenfolgen oder Ganzzahlen zu speichern. Was ist also der Leistungsunterschied zwischen ArrayList und LinkedList? Wann sollten Sie ArrayList und wann LinkedList verwenden?
eins. Zeitkomplexität
Der erste wichtige Punkt ist, dass die interne Implementierung von ArrayList auf einem grundlegenden Objektarray basiert. Daher ist sie schneller als LinkedList, wenn sie die get-Methode verwendet, um auf ein beliebiges Element in der Liste zuzugreifen (Zufallszugriff). Die get-Methode in LinkedList prüft der Reihe nach von einem Ende der Liste zum anderen Ende. Für LinkedList gibt es keine schnellere Möglichkeit, auf ein bestimmtes Element in der Liste zuzugreifen.
Angenommen, wir haben eine große Liste und die darin enthaltenen Elemente sind möglicherweise vom Typ ArrayList oder LinkedList. Jetzt führen wir eine binäre Suche für diese Liste durch. Für die Abfragegeschwindigkeit von ArrayList und LinkedList. siehe folgendes Programm:
Verbrauchte LinkedList-Zeit: 2596
Dieses Ergebnis ist nicht festgelegt, aber grundsätzlich ist die Zeit von ArrayList deutlich kürzer als die von LinkedList. Daher sollte LinkedList in diesem Fall nicht verwendet werden. Die binäre Suchmethode verwendet eine Direktzugriffsstrategie (Randomaccess), und LinkedList unterstützt keinen schnellen Direktzugriff. Die Zeit, die durch den Direktzugriff auf eine LinkedList verbraucht wird, ist proportional zur Größe der Liste. Dementsprechend ist die Zeit, die für den Direktzugriff in ArrayList benötigt wird, festgelegt.
Bedeutet das, dass ArrayList immer eine bessere Leistung als LinkedList erbringt? Dies ist nicht unbedingt der Fall, da LinkedList in einigen Fällen eine bessere Leistung als ArrayList erbringt und einige Algorithmen effizienter sind, wenn sie in LinkedList implementiert werden. Beispielsweise ist die Leistung besser, wenn die Collections.reverse-Methode zum Umkehren einer Liste verwendet wird.
Schauen Sie sich ein solches Beispiel an: Wenn wir eine Liste haben und eine große Anzahl von Einfüge- und Löschvorgängen darauf ausführen möchten, ist LinkedList in diesem Fall die bessere Wahl. Betrachten Sie das folgende extreme Beispiel, bei dem wir wiederholt ein Element am Anfang einer Liste einfügen:
Zu diesem Zeitpunkt lautet meine Ausgabe: ArrayList braucht: 2463
LinkedList dauert: 15
Dies ist das völlige Gegenteil zum Ergebnis des vorherigen Beispiels. Wenn ein Element am Anfang der ArrayList hinzugefügt wird, werden alle vorhandenen Elemente nach hinten verschoben, was einen Mehraufwand für das Verschieben und Kopieren von Daten bedeutet. Im Gegensatz dazu wird beim Hinzufügen eines Elements am Anfang einer LinkedList einfach ein Datensatz dem Element zugewiesen und dann die beiden Links angepasst. Die Kosten für das Hinzufügen eines Elements am Anfang einer LinkedList sind fest, während die Kosten für das Hinzufügen eines Elements am Anfang einer ArrayList proportional zur Größe der ArrayList sind.
zwei. Raumkomplexität
In LinkedList gibt es eine private innere Klasse, die wie folgt definiert ist:
privater statischer Klasseneintrag {
Objektelement;
Eintrag weiter;
Eintrag vorher;
}
Jedes Entry-Objekt verweist auf ein Element in der Liste sowie auf sein vorheriges und nächstes Element in der LinkedList. Ein LinkedList-Objekt mit 1000 Elementen verfügt über 1000 miteinander verknüpfte Eintragsobjekte, wobei jedes Objekt einem Element in der Liste entspricht. In diesem Fall entsteht in einer LinkedList-Struktur viel Platzbedarf, da die relevanten Informationen dieser 1000 Entity-Objekte gespeichert werden müssen.
ArrayList verwendet ein integriertes Array zum Speichern von Elementen. Die Startkapazität dieses Arrays beträgt 10. Wenn das Array wachsen muss, wird die neue Kapazität gemäß der folgenden Formel ermittelt: neue Kapazität = (alte Kapazität*3)/2+ 1, das heißt, die Kapazität erhöht sich jedes Mal um etwa 50 %. Das heißt, wenn Sie ein ArrayList-Objekt mit einer großen Anzahl von Elementen haben, wird am Ende viel Platz verschwendet. Diese Verschwendung wird durch die Art und Weise verursacht, wie ArrayList funktioniert. Wenn nicht genügend Speicherplatz zum Speichern des neuen Elements vorhanden ist, muss das Array neu zugewiesen werden, damit das neue Element hinzugefügt werden kann. Eine Neuzuweisung des Arrays führt zu einem drastischen Leistungsabfall. Wenn wir wissen, wie viele Elemente eine ArrayList haben wird, können wir die Kapazität über den Konstruktor angeben. Wir können auch die Methode trimToSize verwenden, um den verschwendeten Speicherplatz zu entfernen, nachdem die ArrayList zugewiesen wurde.
drei. Zusammenfassen
ArrayList und LinkedList haben jeweils ihre eigenen Vor- und Nachteile in Bezug auf die Leistung und jede hat ihre eigene Anwendung. Im Allgemeinen kann sie wie folgt beschrieben werden:
Leistungsübersicht:
| - | add()-Operation | delete()-Vorgang | Einfügevorgang | Indexwertoperation | Iteratorwertoperation |
|---|---|---|---|---|---|
| ArrayList/Vektor/Stapel | Gut | Unterschied | Unterschied | Exzellent | Exzellent |
| LinkedList | Gut | Gut | Gut | Unterschied | Exzellent |
1. Sowohl für ArrayList als auch für LinkedList sind die Kosten für das Hinzufügen eines Elements am Ende der Liste festgelegt. Bei ArrayList wird hauptsächlich ein Element zum internen Array hinzugefügt, das auf das hinzugefügte Element zeigt, was gelegentlich dazu führen kann, dass das Array neu zugewiesen wird. Bei LinkedList ist dieser Overhead einheitlich und weist ein internes Eintragsobjekt zu.
2. Das Einfügen oder Löschen eines Elements in der Mitte einer ArrayList bedeutet, dass die verbleibenden Elemente in der Liste verschoben werden, während das Einfügen oder Löschen eines Elements in der Mitte einer LinkedList mit festen Kosten verbunden ist.
3． LinkedList unterstützt keinen effizienten zufälligen Elementzugriff.
4. Die Platzverschwendung von ArrayList spiegelt sich hauptsächlich in der Reservierung einer bestimmten Menge Platz am Ende der Liste wider, während sich der Platzverbrauch von LinkedList darin widerspiegelt, dass jedes Element davon eine beträchtliche Menge Platz beanspruchen muss.
Man kann es so sagen: Wenn die Operation Daten nach einer Datenspalte und nicht in der Mitte hinzufügen soll und Sie zufällig auf die Elemente zugreifen müssen, bietet die Verwendung von ArrayList eine bessere Leistung, wenn sich Ihre Operation davor befindet eine Datenspalte Wenn Sie Daten in der Mitte hinzufügen oder löschen und der Reihe nach auf die Elemente zugreifen, sollten Sie LinkedList verwenden.
Der Unterschied zwischen ArrayList und List in Java
Listensammlung
Die Liste erbt von der Collection-Schnittstelle. Die Liste ist eine geordnete Sammlung. Die Elemente in der Liste können basierend auf dem Index (Sequenznummer: die Positionsinformationen des Elements in der Sammlung) abgerufen/gelöscht/eingefügt werden.
Im Gegensatz zur Set-Sammlung erlaubt List doppelte Elemente. Für e1- und e2-Objektelemente, die die Bedingungen von e1.equals(e2) erfüllen, können sie gleichzeitig in der List-Sammlung vorhanden sein. Natürlich gibt es auch List-Implementierungsklassen, die keine doppelten Elemente zulassen.
Gleichzeitig stellt List auch eine listIterator()-Methode bereit, die ein ListIterator-Schnittstellenobjekt zurückgibt. Im Vergleich zur Iterator-Schnittstelle fügt ListIterator Methoden zum Hinzufügen, Löschen und Festlegen von Elementen hinzu und kann auch vorwärts oder rückwärts durchlaufen.
Die Beziehung zwischen Liste und Sammlung:
java.util.Collection[I]
+--java.util.List[I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vector [C]
+--java.util.Stack [C]
Zu den Implementierungsklassen der List-Schnittstelle gehören hauptsächlich ArrayList, LinkedList, Vector, Stack usw.
Vater-Sohn-Beziehung.
List ist eine Schnittstelle, und ArrayList erbt diese Schnittstelle und implementiert sie.
Wenn ich es verwende, verwende ich normalerweise ArrayList. Sie können es wie folgt verwenden: List list = new ArrayList();
Sammlungsschnittstelle
Collection ist die grundlegendste Collection-Schnittstelle. Eine Collection stellt eine Reihe von Objekten dar, also die Elemente der Collection. Einige Sammlungen erlauben identische Elemente, andere nicht. Manche sortieren, andere nicht. Das Java SDK stellt keine Klassen bereit, die direkt von Collection erben. Die vom Java SDK bereitgestellten Klassen sind alle „Unterschnittstellen“, die von Collection erben, wie z. B. List und Set.
Alle Klassen, die die Collection-Schnittstelle implementieren, müssen zwei Standardkonstruktoren bereitstellen: einen parameterlosen Konstruktor zum Erstellen einer leeren Collection und einen Collection-Parameterkonstruktor zum Erstellen einer neuen Collection. Die Eingabesammlung enthält dieselben Elemente. Der letztere Konstruktor ermöglicht dem Benutzer das Kopieren einer Sammlung.
Wie kann ich jedes Element in der Sammlung durchlaufen? Unabhängig vom tatsächlichen Typ der Sammlung unterstützt sie eine iterator()-Methode, die einen Iterator zurückgibt, mit dem nacheinander auf jedes Element in der Sammlung zugegriffen werden kann. Typische Verwendung ist wie folgt:
Iterator it =collection.iterator(); // Holen Sie sich einen Iterator
while(it.hasNext()) {
Object obj = it.next(); // Das nächste Element abrufen
}
Die beiden von der Collection-Schnittstelle abgeleiteten Schnittstellen sind List und Set.
Listenschnittstelle:
List ist eine geordnete Sammlung. Mit dieser Schnittstelle können Sie die Einfügeposition jedes Elements genau steuern. Benutzer können über den Index (die Position des Elements in der Liste, ähnlich einem Array-Index), der einem Java-Array ähnelt, auf Elemente in der Liste zugreifen.
Im Gegensatz zum unten erwähnten Set erlaubt List die gleichen Elemente.
Zusätzlich zur iterator()-Methode, die für die Collection-Schnittstelle erforderlich ist, bietet List auch eine listIterator()-Methode, die eine ListIterator-Schnittstelle zurückgibt. Im Vergleich zur Standard-Iterator-Schnittstelle verfügt ListIterator über einige weitere add()- und andere Methoden, die Ergänzungen ermöglichen. Elemente löschen, festlegen und vorwärts oder rückwärts bewegen.
Gängige Klassen, die die List-Schnittstelle implementieren, sind LinkedList, ArrayList, Vector und Stack.
LinkedList-Klasse
LinkedList implementiert die List-Schnittstelle und lässt Nullelemente zu. Darüber hinaus bietet LinkedList zusätzliche Get-, Remove- und Insert-Methoden am Anfang oder Ende von LinkedList. Diese Operationen ermöglichen die Verwendung von LinkedList als Stack, Warteschlange oder Deque.
Beachten Sie, dass LinkedList keine synchronisierten Methoden hat. Wenn mehrere Threads gleichzeitig auf eine Liste zugreifen, müssen sie die Zugriffssynchronisierung selbst implementieren. Eine Problemumgehung besteht darin, beim Erstellen der Liste eine synchronisierte Liste zu erstellen:
Liste list = Collections.synchronizedList(new LinkedList(...));
ArrayList-Klasse
ArrayList implementiert Arrays variabler Größe. Es erlaubt alle Elemente, einschließlich null. ArrayList ist nicht synchronisiert.
Die Laufzeit der Methoden size, isEmpty, get und set ist konstant. Allerdings sind die Kosten der Add-Methode eine amortisierte Konstante, und das Addieren von n Elementen erfordert O(n) Zeit. Andere Methoden haben eine lineare Laufzeit.
Jede ArrayList-Instanz verfügt über eine Kapazität (Capacity), die der Größe des Arrays entspricht, das zum Speichern von Elementen verwendet wird. Diese Kapazität erhöht sich automatisch, wenn neue Elemente hinzugefügt werden, der Wachstumsalgorithmus ist jedoch nicht definiert. Wenn eine große Anzahl von Elementen eingefügt werden muss, kann die Methode „sichsureCapacity“ aufgerufen werden, um die Kapazität der ArrayList vor dem Einfügen zu erhöhen und so die Einfügeeffizienz zu verbessern.
Wie LinkedList ist auch ArrayList nicht synchronisiert.
Zusammenfassung: Wenn Vorgänge wie Stapel und Warteschlangen beteiligt sind, sollten Sie die Verwendung von List in Betracht ziehen. Wenn Sie Elemente schnell einfügen und löschen müssen, sollten Sie LinkedList verwenden. Wenn Sie schnellen Direktzugriff auf Elemente benötigen, sollten Sie ArrayList verwenden.
Versuchen Sie, die Schnittstelle anstelle des tatsächlichen Typs zurückzugeben, z. B. List anstelle von ArrayList, sodass der Clientcode nicht geändert werden muss, wenn Sie ArrayList in Zukunft durch LinkedList ersetzen müssen. Das ist Programmierung zur Abstraktion.