Java ArrayList

ArrayList<E> ist die meistgenutzte List-Implementierung. Intern ist sie ein einfaches Java-Array (Object[]) mit einem Längenzähler und etwas Wachstumslogik obendrauf. Das verleiht ihr das Leistungsprofil, das die meisten Programme benötigen: O(1) wahlfreier Zugriff, amortisiertes O(1) Anhängen am Ende und nur gelegentliche Pausen, wenn das Backing-Array wachsen muss. Wenn jemand „verwende eine Liste" sagt, ohne anzugeben welche, meint er fast immer ArrayList. Dieses Kapitel erklärt warum, welche Abwägungen es gibt und die wenigen Methoden, die nur für diese Klasse spezifisch sind.

Was steckt drin

Eine ArrayList enthält drei Zustandsvariablen:

• Object[] elementData — das Backing-Array. Größer als size mit etwas Puffer.
• int size — wie viele dieser Slots belegt sind.
• int modCount — ein Zähler, der Iteratoren fehlschlagen lässt, wenn du während der Iteration veränderst.

Das Javadoc ist präzise bezüglich der Komplexität: size, isEmpty, get, set, iterator, listIterator und add (am Ende) laufen alle in konstanter Zeit. Einfügen und Entfernen an anderer Stelle ist linear, weil der Rest des Arrays verschoben werden muss. Darauf kommen wir zurück.

Eine erstellen

List<String> a = new ArrayList<>();             // default capacity (10)
List<String> b = new ArrayList<>(1_000_000);    // pre-size — avoids re-grows
List<String> c = new ArrayList<>(otherList);    // copy of any Collection
List<String> d = new ArrayList<>(List.of("a", "b", "c"));   // from a small literal

Wenn du ungefähr weißt, wie viele Elemente du hinzufügen wirst, übergib die Kapazität dem Konstruktor. Die Standardkapazität ist 10, und jedes Mal, wenn das Array voll ist, wächst es um etwa 50 % — was bei Millionen von Elementen zu vielen Allokationen und Kopien führt, wenn man mit dem Standard beginnt. Einzeilige Lösung:

List<Row> rows = new ArrayList<>(expectedSize);

Für „aus dieser festen Menge" bevorzuge die List.of(...)-Factory (später in diesem Kapitel behandelt) — sie ist kleiner und unveränderlich.

Hinzufügen und Entfernen — der Aufwand hängt von der Position ab

Jedes List.add(E), add(int, E), remove(int) und remove(Object) hat im schlimmsten Fall O(n), wenn es die Mitte des Arrays berührt. Der Grund ist mechanisch: Ein Array ist zusammenhängender Speicher, also bedeutet das Einfügen am Anfang, dass jedes vorhandene Element um einen Slot nach rechts verschoben werden muss. Der amortisierte Aufwand des Anhängens am Ende ist O(1) (kein Verschieben), aber jede andere Position ist linear in der Anzahl der Elemente nach dem Einfügepunkt.

In der Praxis bedeutet das:

• Eine Liste durch wiederholtes list.add(x) aufbauen → schnell, unabhängig von der Größe. Anhängen am Ende ist der Zweck von ArrayList.
• list.add(0, x) in einer Schleife aufrufen → quadratisch. Nicht tun.
• list.remove(0) wiederholt aufrufen, um zu leeren → quadratisch. Verwende eine Deque oder iteriere rückwärts.

Wenn du ständig am Anfang einfügst oder entfernst, ist ArrayDeque das richtige Werkzeug.

Kapazität vs. Größe

Das sind zwei verschiedene Zahlen:

• size() ist die öffentliche, vertragliche Anzahl der Elemente.
• Die Kapazität — die Länge des Backing-Arrays — ist intern und größer als size.

Wenn der Puffer aufgebraucht ist, allokiert ArrayList ein neues Array mit ungefähr 1,5× der alten Länge und kopiert es. Das ist das „Wachstum", vor dem das Javadoc warnt. Zwei Stellhebel:

• ensureCapacity(int) — das Backing-Array auf mindestens diese Länge erhöhen, bevor eine bekannte Menge von add-Aufrufen kommt.
• trimToSize() — das Backing-Array genau auf size verkleinern. Nützlich, wenn du weißt, dass die Liste nicht weiter wächst (z. B. bevor du sie lange cacht).

Keines davon greifst du oft an, aber es ist gut zu wissen, dass sie existieren, wenn du einen kritischen Pfad optimierst.

ArrayList ist nicht Thread-sicher

Zwei Threads, die dieselbe ArrayList verändern, werden sie irgendwann korrumpieren. Es gibt keine Synchronisation, keine atomaren Operationen, nichts. Wenn du gleichzeitigen Zugriff benötigst, sind deine Optionen:

• Collections.synchronizedList(new ArrayList<>()) — kapselt jeden Mutator in einem Lock. Iteratoren sind trotzdem nicht sicher — du musst extern während der Iteration synchronisieren. Gut für Fälle mit geringem Contention.
• CopyOnWriteArrayList — jede Mutation allokiert eine neue Kopie des Backing-Arrays. Iteration ist lock-frei und sieht einen eingefrorenen Snapshot. Hervorragend für „viele Leser, gelegentlicher Schreiber" (Event-Listener, Konfigurations-Caches). Schlecht für schreibintensive Workloads.
• Vector — ebenfalls synchronisiert, aber ein Design von 1995 mit denselben Schwächen wie synchronizedList. Nicht für neuen Code verwenden.

Threading ist ein eigenes tiefes Thema; für jetzt gilt die Regel: eine ArrayList, die über Threads geteilt wird, braucht einen Wrapper oder eine andere Klasse.

Iteration und ConcurrentModificationException

Das Hinzufügen oder Entfernen aus einer ArrayList während der Iteration über sie mit der for-each-Schleife wirft fast immer ConcurrentModificationException:

List<Integer> xs = new ArrayList<>(List.of(1, 2, 3, 4));
for (int x : xs) {
  if (x % 2 == 0) xs.remove(Integer.valueOf(x));   // throws
}

Die Fail-fast-Prüfung vergleicht den Snapshot von modCount des Iterators mit dem aktuellen modCount der Liste. Die zwei Möglichkeiten, sicher zu mutieren:

xs.removeIf(x -> x % 2 == 0);              // 1. predicate form — cleanest

Iterator<Integer> it = xs.iterator();
while (it.hasNext())                        // 2. explicit Iterator.remove()
  if (it.next() % 2 == 0) it.remove();

removeIf ist der moderne Standard. Greife auf den expliziten Iterator nur zurück, wenn die Bedingung von Zustand abhängt, den du nicht zweimal berechnen möchtest.

Nützliche Methoden, die nicht auf List zu finden sind

ArrayList fügt einige Methoden hinzu, die das List-Interface nicht hat:

• void trimToSize() — auf Maß verkleinern.
• void ensureCapacity(int) — vorab vergrößern.
• Object clone() — flache Kopie. Äquivalent zu new ArrayList<>(this) und fast nie verwendet.

Das war's. Fast alles, was du auf einer ArrayList aufrufst, stammt aus dem List-Interface.

Ein durchgearbeitetes Beispiel: ArrayList in Aktion

Das folgende Programm erstellt eine ArrayList, übt ihre indexbasierten Operationen, leert sie und endet mit dem Timing-Unterschied zwischen vorab größenbestimmtem und standardmäßig größenbestimmtem Aufwand, damit du die Kosten des vergessenen Vorab-Größenbestimmens siehst.

Die Reihenfolge der Operationen, die aus der Ausgabe abzulesen ist:

• fruits.add(1, "avocado") hat jedes spätere Element um einen Slot nach rechts verschoben. Bei vier Elementen ist das unsichtbar; bei einer Million würde es die Laufzeit dominieren.
• removeIf und subList sind die zwei Mechanismen, die den meisten echten ArrayList-Code sauber machen — prädikatbasiertes Bulk-Entfernen und Live-Fenster-Operationen.
• Der Timing-Block ist illustrativ, kein Benchmark-Qualitätstest — bei einem einzigen JIT-Aufwärmlauf können die Zahlen sogar umgekehrt ausfallen. Der strukturelle Punkt: Standard-Kapazitäts-Anhängen vergrößert das Backing-Array beim millionsten Element etwa 30 Mal, und Vorab-Größenbestimmung eliminiert jede dieser Kopien. Für einen stabilen kritischen Pfad gewinnt die vorab dimensionierte Version; messe mit einem ordentlichen Harness, wenn es wichtig ist.

Was kommt als Nächstes

ArrayList ist fast immer die richtige Antwort. Der interessante Fall ist, wenn es das nicht ist — starkes Einfügen und Entfernen am Anfang oder in der Mitte einer langen Liste. Das ist die Nische von LinkedList: dasselbe List-Interface, völlig andere Speicherung. Dasselbe Problem, zwei Antworten — und wir werden messen, wann jede gewinnt.

Übungen