0Pricing
Java Academy · Lektion

LinkedList vs. ArrayList: Abwägungen

Vergleichen Sie die Performance von Einfügen, Löschen und wahlfreiem Zugriff, um den passenden Listentyp auszuwählen.

LinkedList vs. ArrayList: Abwägungen ist eine kostenlose Java Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Java Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Java Academy-Kurs umfasst insgesamt 4 Lektionen.

Die zentrale Frage

ArrayList und LinkedList implementieren beide List und verfügen daher über dieselbe API. Der Unterschied liegt in ihren internen Datenstrukturen und darin, welche Operationen jeweils effizient ausgeführt werden.

Interna von ArrayList

ArrayList speichert Elemente in einem zusammenhängenden Array. Wenn das Array voll ist, wird es durch ein neues Array ersetzt, das 1,5-mal größer ist, und alle Elemente werden kopiert.

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

Interna von LinkedList erneut betrachtet

Jedes Element befindet sich in einem eigenen Node-Objekt mit prev-/next-Zeigern. Es gibt keinen zusammenhängenden Speicher – die Knoten können sich an beliebigen Stellen im Heap befinden.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

Wahlfreier Zugriff: ArrayList gewinnt

ArrayList.get(i) hat die Komplexität O(1) – direkter Zugriff über den Arrayindex. LinkedList.get(i) hat die Komplexität O(n) – es werden bis zu n/2 Knoten durchlaufen.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

Einfügen am Anfang: LinkedList gewinnt

Das Einfügen an Index 0 in ArrayList erfordert das Verschieben aller Elemente – O(n). LinkedList aktualisiert lediglich zwei Zeiger – O(1).

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

Einfügen am Ende: ungefähr gleich

Sowohl ArrayList als auch LinkedList bieten amortisiert O(1) beim Anhängen am Ende. ArrayList löst gelegentlich das Kopieren beim Vergrößern aus, bleibt amortisiert jedoch bei O(1). LinkedList reserviert einen neuen Knoten – eine Größenänderung ist nicht erforderlich.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

Speicherverbrauch

ArrayList: etwa 8 Byte pro Element (eine Referenz im Array). LinkedList: etwa 48 Byte pro Element (Node-Objekt mit Daten, prev, next und Objekt-Header). Für große Datenmengen benötigt ArrayList deutlich weniger Speicher.

Leistung bei der Iteration

Die sequenzielle Iteration (for-each oder Iterator) hat bei beiden die Komplexität O(n). ArrayList profitiert jedoch vom Prefetching des CPU-Caches, da die Elemente zusammenhängend im Speicher liegen. Die Knoten von LinkedList sind über den Heap verteilt, was zu Cache Misses führt.

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

Einfügen und Löschen in der Mitte

Bei beiden sind zum Auffinden der Position O(n) erforderlich. Sobald sie gefunden wurde, verschiebt ArrayList Elemente in O(n), während LinkedList lediglich die Verknüpfung in O(1) entfernt. Bei häufigen Änderungen in der Mitte ist LinkedList daher im Vorteil, wenn Sie bereits einen Iterator halten; andernfalls sind beide ähnlich.

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

Entscheidungshilfe

Wählen Sie die Datenstruktur anhand der vorherrschenden Operation:

  • ArrayList: wahlfreier Zugriff, Iteration, Anhängen am Ende – deckt 90 % der Anwendungsfälle ab
  • LinkedList: häufiges Einfügen und Entfernen am Anfang oder Ende, Implementierung von Queue/Deque/Stack
  • ArrayDeque: wenn Sie eine reine Queue oder einen reinen Stack benötigen (besser als LinkedList)

Zusammenfassung des Benchmarks

Leistungsmodell:

  • get(i): ArrayList O(1) gegenüber LinkedList O(n)
  • add(0,x): ArrayList O(n) gegenüber LinkedList O(1)
  • add(x): Bei beiden amortisiert O(1)
  • Entfernen über den Iterator: Bei beiden O(1), sobald die Position erreicht ist
  • Speicher pro Element: ArrayList etwa 8 B gegenüber LinkedList etwa 48 B

Kurztest

Sie erstellen eine Aufgabenwarteschlange, in der Aufgaben millionenfach pro Sekunde am Ende hinzugefügt und am Anfang entfernt werden. Welche Datenstruktur ist am besten geeignet?

Zusammenfassung: LinkedList vs. ArrayList

Wichtigste Erkenntnisse:

  • ArrayList eignet sich hervorragend für den wahlfreien Zugriff (O(1)) und cachefreundliche Iteration
  • LinkedList eignet sich hervorragend für O(1)-Operationen am Anfang und Ende
  • Speicherbedarf: ArrayList ca. 8 B/Element; LinkedList ca. 48 B/Element
  • Verwenden Sie für Warteschlangen und Stapel vorzugsweise ArrayDeque statt LinkedList
  • ArrayList ist in den meisten Fällen die richtige Standardwahl

Häufig gestellte Fragen

Ist die Lektion „LinkedList vs. ArrayList: Abwägungen“ kostenlos?

Ja — der vollständige Text von „LinkedList vs. ArrayList: Abwägungen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Java Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Java Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „LinkedList vs. ArrayList: Abwägungen“?

Vergleichen Sie die Performance von Einfügen, Löschen und wahlfreiem Zugriff, um den passenden Listentyp auszuwählen. Du übst Java Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um Java Academy zu starten?

Keine Vorkenntnisse erforderlich. Java Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.

Wie lange dauert die Lektion „LinkedList vs. ArrayList: Abwägungen“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser Java Academy-Lektion Code schreiben und ausführen?

Ja. Jede Java Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Interna von LinkedList
  2. Deque-Operationen: Stack und Queue
  3. LinkedList vs. ArrayList: Abwägungen
  4. PriorityQueue für geordnete Verarbeitung
← Zurück zu Java Academy