Java ArrayList vs LinkedList

1. Übersicht

Wenn es um Sammlungen geht, bietet die Java-Standardbibliothek zahlreiche Optionen zur Auswahl. Unter diesen Optionen befinden sich zwei bekannte List- Implementierungen, die als ArrayList und LinkedList bekannt sind und jeweils ihre eigenen Eigenschaften und Anwendungsfälle haben.

In diesem Tutorial werden wir sehen, wie diese beiden tatsächlich implementiert werden. Anschließend bewerten wir für jede Anwendung unterschiedliche Anwendungen.

2. ArrayList

Intern verwendet ArrayList ein Array, um die List- Schnittstelle zu implementieren . Da Arrays in Java eine feste Größe haben, erstellt ArrayList ein Array mit einer anfänglichen Kapazität. Wenn wir unterwegs mehr Elemente als diese Standardkapazität speichern müssen, wird dieses Array durch ein neues und geräumigeres ersetzt.

Um die Eigenschaften besser zu verstehen, bewerten wir diese Datenstruktur in Bezug auf ihre drei Hauptoperationen: Hinzufügen von Elementen, Abrufen von Elementen nach Index und Entfernen nach Index.

2.1. Hinzufügen

Wenn wir eine leere ArrayList erstellen , wird das Backing-Array mit einer Standardkapazität (derzeit 10) initialisiert:

Das Hinzufügen eines neuen Elements, während dieses Array noch nicht voll ist, ist so einfach wie das Zuweisen dieses Elements zu einem bestimmten Array-Index. Dieser Array-Index wird durch die aktuelle Array-Größe bestimmt, da wir praktisch an die Liste anhängen:

backingArray[size] = newItem; size++;

Also, in besten und mittleren Fällen die Zeitkomplexität für die Additionsoperation ist O (1) , das ist ziemlich schnell. Wenn das Backing-Array jedoch voll wird, wird die Add-Implementierung weniger effizient:

Um ein neues Element hinzuzufügen, sollten wir zuerst ein brandneues Array mit mehr Kapazität initialisieren und alle vorhandenen Elemente in das neue Array kopieren. Erst nach dem Kopieren der aktuellen Elemente können wir das neue Element hinzufügen. Daher ist die Zeitkomplexität im schlimmsten Fall O (n), da wir zuerst n Elemente kopieren müssen .

Theoretisch läuft das Hinzufügen eines neuen Elements in einer amortisierten konstanten Zeit. Das heißt, das Hinzufügen von n Elementen erfordert O (n) Zeit. Einige einzelne Ergänzungen können jedoch aufgrund des Kopieraufwands eine schlechte Leistung erbringen.

2.2. Zugriff per Index

Beim Zugriff auf Elemente über ihre Indizes leuchtet die ArrayList wirklich. Um ein Element am Index i abzurufen , müssen wir nur das Element am i-ten Index aus dem Hintergrundarray zurückgeben. Folglich ist die zeitliche Komplexität für den Zugriff durch Indexoperation immer O (1).

2.3. Nach Index entfernen

Angenommen, wir entfernen den Index 6 aus unserer ArrayList, der dem Element 15 in unserem Hintergrundarray entspricht:

Nachdem wir das gewünschte Element als gelöscht markiert haben, sollten wir alle Elemente danach um einen Index zurück verschieben. Je näher das Element am Anfang des Arrays liegt, desto mehr Elemente sollten wir natürlich verschieben. So ist die Zeitkomplexität ist O (1) im günstigsten Fall und O (n) im Durchschnitt und schlechtesten Fälle.

2.4. Anwendungen und Einschränkungen

Normalerweise ist ArrayList die Standardauswahl für viele Entwickler, wenn sie eine List- Implementierung benötigen . Tatsächlich ist es eine vernünftige Wahl, wenn die Anzahl der Lesevorgänge weit über der Anzahl der Schreibvorgänge liegt .

Manchmal müssen wir gleich häufig lesen und schreiben. Wenn wir eine Schätzung der maximal möglichen Anzahl von Elementen haben, ist es dennoch sinnvoll, ArrayList zu verwenden . In diesem Fall können wir die ArrayList mit einer anfänglichen Kapazität initialisieren :

int possibleUpperBound = 10_000; List items = new ArrayList(possibleUpperBound);

Diese Schätzung kann viele unnötige Kopier- und Arrayzuweisungen verhindern.

Darüber hinaus werden Arrays in Java durch int- Werte indiziert . Es ist also nicht möglich, mehr als 232 Elemente in einem Java-Array und folglich in ArrayList zu speichern .

3. LinkedList

LinkedList verwendet , wie der Name schon sagt, eine Sammlung verknüpfter Knoten zum Speichern und Abrufen von Elementen . So sieht die Java-Implementierung beispielsweise aus, nachdem vier Elemente hinzugefügt wurden:

Jeder Knoten verwaltet zwei Zeiger: einen auf das nächste Element und einen auf das vorherige. Die doppelt verknüpfte Liste enthält zwei Zeiger, die auf das erste und das letzte Element verweisen.

Lassen Sie uns diese Implementierung erneut in Bezug auf dieselben grundlegenden Operationen bewerten.

3.1. Hinzufügen

Um einen neuen Knoten hinzuzufügen, müssen wir zuerst den aktuellen letzten Knoten mit dem neuen Knoten verknüpfen:

Und dann aktualisieren Sie den letzten Zeiger:

Da diese beiden Operationen trivial sind, beträgt die zeitliche Komplexität für die Additionsoperation immer O (1) .

3.2. Zugriff per Index

LinkedList unterstützt im Gegensatz zu ArrayList keinen schnellen Direktzugriff. Um ein Element anhand des Index zu finden, sollten wir einen Teil der Liste manuell durchlaufen .

Im besten Fall wäre die zeitliche Komplexität so schnell wie O (1) , wenn sich das angeforderte Element am Anfang oder Ende der Liste befindet . Im Durchschnitt und im schlimmsten Fall kann es jedoch zu einer O (n) -Zugriffszeit kommen, da wir viele Knoten nacheinander untersuchen müssen.

3.3. Nach Index entfernen

Um einen Artikel zu entfernen, sollten wir zuerst den gewünschten Artikel finden und ihn dann von der Liste trennen . Folglich bestimmt die Zugriffszeit die Zeitkomplexität - das heißt O (1) im besten Fall und O (n) im Durchschnitt und im schlimmsten Fall.

3.4. Anwendungen

LinkedLists sind besser geeignet, wenn die Additionsrate viel höher als die Leserate ist .

Es kann auch in schreibintensiven Szenarien verwendet werden, wenn die meiste Zeit das erste oder letzte Element benötigt wird. Erwähnenswert ist, dass LinkedList auch die Deque- Schnittstelle implementiert und einen effizienten Zugriff auf beide Enden der Sammlung unterstützt.

Wenn wir ihre Implementierungsunterschiede kennen, können wir im Allgemeinen leicht einen für einen bestimmten Anwendungsfall auswählen.

Nehmen wir zum Beispiel an, wir werden viele Zeitreihenereignisse in einer listenartigen Datenstruktur speichern. Wir wissen, dass wir jede Sekunde eine Reihe von Ereignissen erhalten würden.

Außerdem müssen wir alle Ereignisse regelmäßig nacheinander untersuchen und einige Statistiken bereitstellen. Für diesen Anwendungsfall ist LinkedList die bessere Wahl, da die Additionsrate viel höher ist als die Leserate .

Außerdem würden wir alle Elemente lesen, damit wir die O (n) -Obergrenze nicht überschreiten können.

4. Fazit

In diesem Tutorial haben wir uns zunächst mit der Implementierung von ArrayList und LinkLists in Java befasst.

Wir haben auch verschiedene Anwendungsfälle für jeden dieser Fälle bewertet.