
Eine ArrayList ist eine Liste, die ihre Elemente in einem Array speichert. Ist das Array voll, legt sie ein größeres an und kopiert die Elemente in das neue Array – du musst die Größe also nicht im Voraus kennen.
Das folgende Programm legt eine leere ArrayList an, fügt drei Namen hinzu und liest den zweiten Namen, die Anzahl der Elemente und die ganze Liste aus:
List<String> names = new ArrayList<>();
names.add("Ada");
names.add("Grace");
names.add("Alan");
System.out.println(names.get(1));
System.out.println(names.size());
System.out.println(names);
Grace
3
[Ada, Grace, Alan]
Der Index beginnt wie beim Array bei 0, get(1) liefert also das zweite Element.
In diesem Artikel erfährst du,
- worin sich eine
ArrayListvon einem Array unterscheidet, - wie du eine
ArrayListerzeugst und warumList.of()undArrays.asList()keineArrayListsind, - mit welchen Methoden du Elemente hinzufügst, liest, änderst und entfernst,
- wie du über eine
ArrayListiterierst und warum dabei eineConcurrentModificationExceptionauftreten kann, - wie du eine
ArrayListin ein Array umwandelst und umgekehrt, - wie die
ArrayListintern arbeitet und wie schnell ihre Operationen sind, - wann du
LinkedList,VectoroderCopyOnWriteArrayListnehmen solltest.
Die Beispiele in diesem Artikel
Den vollständigen Code findest du im GitHub-Repository java-collections-guide, im Package eu.happycoders.collections.arraylist. Jeder Abschnitt hat dort eine eigene Klasse mit einer main()-Methode, die die gezeigten Ausgaben erzeugt.
Die Beispiele arbeiten fast alle mit den Vornamen von Pionier:innen der Informatik – Ada Lovelace, Grace Hopper, Alan Turing, Linus Torvalds und einigen mehr.
Die Klassen im Repository brauchen Java 25, weil sie die vereinfachte main()-Methode ohne String[] args verwenden. Die Listings im Artikel laufen ab Java 21 – sie verwenden getFirst(), addFirst() und reversed(), die es erst seit Java 21 gibt.
Was ist eine ArrayList?
ArrayList ist eine Klasse aus dem Package java.util und implementiert das Interface List. Sie hat die folgenden Eigenschaften:
- Sie behält die Reihenfolge, in der du die Elemente einfügst.
- Du greifst über einen Index auf jedes Element zu, beginnend bei 0.
- Sie darf dasselbe Element mehrfach enthalten, auch
null. - Sie wächst und schrumpft mit ihren Elementen.
- Sie ist nicht threadsicher – wenn mehrere Threads gleichzeitig schreibend zugreifen, musst du selbst synchronisieren.
Bevor du sie verwenden kannst, musst du sie importieren:
import java.util.ArrayList;
import java.util.List;
Seit Java 25 kannst du stattdessen das ganze Modul java.base mit import module java.base; importieren. In einem Compact Source File – einer Quelldatei ohne Klassendeklaration – brauchst du gar keinen Import, denn es importiert java.base automatisch.
Das folgende Klassendiagramm zeigt, wo ArrayList in der Hierarchie der Collections steht. Blau umrandet sind ArrayList und die Interfaces, die sie implementiert – List erweitert seit Java 21 das Interface SequencedCollection. Grau steht daneben zum Vergleich die LinkedList, die ebenfalls List implementiert:
RandomAccess ist ein sogenanntes Marker-Interface ohne Methoden. Algorithmen wie Collections.binarySearch() prüfen mit instanceof RandomAccess, ob der Zugriff per Index schnell ist, und greifen nur dann per Index zu. LinkedList implementiert dieses Interface nicht.
Array vs. ArrayList
Ein Array hat eine feste Länge, die du beim Anlegen festlegst. Eine ArrayList wächst mit jedem add() und schrumpft mit jedem remove().
Das folgende Listing legt ein Array für drei Namen an und eine ArrayList, in die anschließend vier Namen passen, ohne dass du vorher eine Größe angeben musst:
String[] array = new String[3];
array[0] = "Ada";
array[1] = "Grace";
array[2] = "Alan";
System.out.println(array.length + " " + Arrays.toString(array));
List<String> list = new ArrayList<>();
list.add("Ada");
list.add("Grace");
list.add("Alan");
list.add("Linus");
System.out.println(list.size() + " " + list);
3 [Ada, Grace, Alan]
4 [Ada, Grace, Alan, Linus]
Ein viertes Element hätte im Array keinen Platz – array[3] = "Linus" würde eine ArrayIndexOutOfBoundsException werfen.
Die folgende Tabelle stellt die Unterschiede gegenüber:
| Array | ArrayList | |
|---|---|---|
| Länge | fest | wächst und schrumpft |
| Elementtypen | primitive Typen und Objekte | nur Objekte |
| Anzahl der Elemente | array.length | list.size() |
| Element lesen | array[i] | list.get(i) |
| Element schreiben | array[i] = x | list.set(i, x) |
| Element hinzufügen | ✗ | list.add(x) |
| Element entfernen | ✗ | list.remove(i) |
| Ausgabe als String | Arrays.toString(array) | list.toString() |
Ein Array ist dann die bessere Wahl, wenn die Anzahl der Elemente feststeht und es um primitive Werte geht. Ein int[] mit einer Million Zahlen belegt 4 MB, eine ArrayList<Integer> mit denselben Zahlen rund 20 MB – warum, zeigt der Abschnitt Speicherbedarf der ArrayList.
Wie du Arrays anlegst und mit Werten füllst, zeigt der Artikel Arrays in Java initialisieren, wie du ihre Länge bestimmst, der Artikel Array-Länge in Java.
List oder ArrayList als Variablentyp?
Die Beispiele in diesem Artikel deklarieren ihre Variablen mit dem Interface List und erzeugen das Objekt mit new ArrayList:
List<String> names = new ArrayList<>();
So hängt der Code, der names verwendet, nur von den Methoden des Interfaces ab. Wenn du später eine andere List-Implementierung einsetzen willst, brauchst du nur die eine Zeile mit new zu ändern.
Den Typ ArrayList brauchst du für die Variable nur, wenn du eine der drei öffentlichen Methoden aufrufst, die das Interface nicht hat: ensureCapacity() und trimToSize() steuern die Länge des internen Arrays, clone() erzeugt eine Kopie.
Eine ArrayList erzeugen
Eine leere ArrayList erzeugst du mit dem parameterlosen Konstruktor. Den Elementtyp musst du rechts nicht wiederholen, der Diamond-Operator <> übernimmt ihn von der linken Seite:
List<String> names = new ArrayList<>();
Eine ArrayList mit Elementen erzeugen
Eine ArrayList, die schon Elemente enthält, erzeugst du, indem du dem Konstruktor eine andere Collection übergibst – am kürzesten eine mit List.of() erzeugte:
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan"));
names.add("Linus");
System.out.println(names);
[Ada, Grace, Alan, Linus]
List.of() allein liefert keine ArrayList, sondern eine unveränderliche Liste. Und Arrays.asList() liefert eine Liste mit fester Größe, die auf das übergebene Array zugreift: set() funktioniert, add() und remove() dagegen nicht.
Das folgende Listing versucht, jeweils ein Element hinzuzufügen:
List<String> fixed = List.of("Ada", "Grace", "Alan");
try {
fixed.add("Linus");
} catch (UnsupportedOperationException e) {
System.out.println("List.of(): " + e);
}
List<String> backedByArray = Arrays.asList("Ada", "Grace", "Alan");
backedByArray.set(0, "Linus");
System.out.println("Arrays.asList() after set(): " + backedByArray);
try {
backedByArray.add("Barbara");
} catch (UnsupportedOperationException e) {
System.out.println("Arrays.asList(): " + e);
}
System.out.println(backedByArray.getClass().getName());
List.of(): java.lang.UnsupportedOperationException
Arrays.asList() after set(): [Linus, Grace, Alan]
Arrays.asList(): java.lang.UnsupportedOperationException
java.util.Arrays$ArrayList
Die letzte Zeile zeigt: Arrays.asList() liefert ein Objekt einer gleichnamigen inneren Klasse von Arrays, nicht die ArrayList aus java.util. Brauchst du eine veränderbare Liste, übergibst du die Ergebnisse von List.of() oder Arrays.asList() an new ArrayList<>(…).
Eine Kopie einer anderen Collection erzeugen
Der Konstruktor mit Collection-Parameter kopiert die Elemente in ein neues Array. Änderungen an der Kopie wirken sich daher nicht auf das Original aus:
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan", "Linus"));
List<String> copy = new ArrayList<>(names);
copy.removeFirst();
System.out.println(names);
System.out.println(copy);
[Ada, Grace, Alan, Linus]
[Grace, Alan, Linus]
Die Kopie ist allerdings flach: Beide Listen verweisen auf dieselben Element-Objekte. Was das bedeutet, zeigt der Abschnitt Eine ArrayList kopieren.
Eine ArrayList mit Anfangskapazität erzeugen
Weißt du im Voraus, wie viele Elemente die Liste aufnehmen wird, kannst du dem Konstruktor die Größe des internen Arrays mitgeben:
List<String> names = new ArrayList<>(1_000);
Die Liste ist danach trotzdem leer – size() liefert 0. Was die Anfangskapazität bringt, steht im Abschnitt Wie die ArrayList wächst.
Eine ArrayList mit Zahlen
Eine ArrayList speichert nur Objekte. ArrayList<int> kompiliert nicht, du schreibst stattdessen die Wrapper-Klasse Integer als Elementtyp. Beim Einfügen wandelt der Compiler ein int automatisch in ein Integer-Objekt um und beim Auslesen zurück – das nennt sich Autoboxing bzw. Unboxing:
List<Integer> numbers = new ArrayList<>();
numbers.add(42);
numbers.add(7);
int sum = numbers.get(0) + numbers.get(1);
System.out.println(sum);
49
Für long und double gilt dasselbe mit Long und Double.
Eine Liste von Listen
Eine zweidimensionale ArrayList gibt es nicht, aber eine ArrayList, deren Elemente selbst Listen sind. Anders als ein 2D-Array muss sie die Größe keiner Zeile vorher kennen.
Das folgende Programm baut so die ersten fünf Zeilen des Pascalschen Dreiecks auf. Jede Zeile ist um ein Element länger als die vorige, und jedes innere Element ist die Summe der beiden Elemente darüber:
List<List<Integer>> triangle = new ArrayList<>();
for (int n = 0; n < 5; n++) {
List<Integer> row = new ArrayList<>();
for (int k = 0; k <= n; k++) {
if (k == 0 || k == n) {
row.add(1);
} else {
List<Integer> previous = triangle.get(n - 1);
row.add(previous.get(k - 1) + previous.get(k));
}
}
triangle.add(row);
}
triangle.forEach(System.out::println);
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
triangle.get(n - 1) liefert die vorige Zeile als List<Integer>, auf die du wieder mit get() zugreifst.
Die Methoden der ArrayList im Überblick
Die folgende Tabelle zeigt die Methoden der ArrayList, gruppiert wie die folgenden Abschnitte. Die Spalte „Aufwand“ nennt die Zeitkomplexität, mit n für die Größe der Liste und m für die Größe der übergebenen Collection – woher die Werte kommen, erklärt der Abschnitt Zeitkomplexität der ArrayList. Die Spalte „seit“ bleibt leer bei Methoden, die es schon in Java 1.2 gab, mit dem die ArrayList kam.
| Methode | Was sie tut | Aufwand | seit |
|---|---|---|---|
| Hinzufügen | |||
add(e) | hängt ein Element an | O(1) amortisiert | |
addLast(e) | hängt ein Element an | O(1) amortisiert | Java 21 |
add(i, e) | fügt ein Element an Position i ein | O(n) | |
addFirst(e) | fügt ein Element am Anfang ein | O(n) | Java 21 |
addAll(c) | hängt alle Elemente einer Collection an | O(m) | |
addAll(i, c) | fügt alle Elemente einer Collection an Position i ein | O(n + m) | |
| Lesen | |||
get(i) | liefert das Element an Position i | O(1) | |
getFirst(), getLast() | liefert das erste bzw. letzte Element | O(1) | Java 21 |
size(), isEmpty() | liefert die Anzahl der Elemente bzw. ob die Liste leer ist | O(1) | |
contains(o) | prüft, ob die Liste ein gleiches Element enthält | O(n) | |
indexOf(o), lastIndexOf(o) | liefert die erste bzw. letzte Position eines gleichen Elements | O(n) | |
| Ändern | |||
set(i, e) | ersetzt das Element an Position i | O(1) | |
replaceAll(op) | ersetzt jedes Element durch das Ergebnis einer Funktion | O(n) | Java 8 |
sort(c) | sortiert die Liste | O(n log n) | Java 8 |
| Entfernen | |||
remove(i) | entfernt das Element an Position i | O(n) | |
remove(o) | entfernt das erste gleiche Element | O(n) | |
removeFirst() | entfernt das erste Element | O(n) | Java 21 |
removeLast() | entfernt das letzte Element | O(1) | Java 21 |
removeIf(p) | entfernt alle Elemente, auf die eine Bedingung zutrifft | O(n) | Java 8 |
removeAll(c), retainAll(c) | entfernt alle bzw. behält nur die Elemente, die in c enthalten sind | O(n · m)* | |
clear() | entfernt alle Elemente | O(n) | |
| Iterieren | |||
iterator(), listIterator() | liefert einen Iterator | O(1) | |
forEach(action) | führt eine Aktion für jedes Element aus | O(n) | Java 8 |
reversed() | liefert eine View in umgekehrter Reihenfolge | O(1) | Java 21 |
| Umwandeln | |||
toArray(), toArray(a) | kopiert die Elemente in ein Array | O(n) | |
toArray(generator) | kopiert die Elemente in ein Array, das generator erzeugt | O(n) | Java 11 |
subList(from, to) | liefert eine View auf einen Bereich | O(1) | |
| Kapazität | |||
ensureCapacity(k) | vergrößert das interne Array auf mindestens k Plätze | O(n) | |
trimToSize() | verkleinert das interne Array auf die Größe der Liste | O(n) |
* removeAll() und retainAll() rufen für jedes Element der Liste contains() der übergebenen Collection auf. Ist diese ein HashSet, kostet das jeweils nur O(1), und die Methoden laufen in O(n).
Elemente hinzufügen
Elemente fügst du einer ArrayList mit add() und addAll() hinzu, seit Java 21 zusätzlich mit addFirst() und addLast().
Das folgende Listing hängt einen Namen an, fügt einen an zweiter Stelle ein, hängt zwei weitere an, fügt zwei an dritter Stelle ein und setzt schließlich einen an den Anfang:
List<String> names = new ArrayList<>(List.of("Ada", "Alan"));
names.add("Linus");
System.out.println(names);
names.add(1, "Grace");
System.out.println(names);
names.addAll(List.of("James", "Barbara"));
System.out.println(names);
names.addAll(2, List.of("Ken", "Dennis"));
System.out.println(names);
names.addFirst("Charles");
System.out.println(names);
[Ada, Alan, Linus]
[Ada, Grace, Alan, Linus]
[Ada, Grace, Alan, Linus, James, Barbara]
[Ada, Grace, Ken, Dennis, Alan, Linus, James, Barbara]
[Charles, Ada, Grace, Ken, Dennis, Alan, Linus, James, Barbara]
add(e) und addLast(e) tun dasselbe: Sie hängen das Element ans Ende. add() liefert dabei immer true zurück – der Rückgabewert stammt aus dem Interface Collection, wo ein Set mit false meldet, dass es das Element schon enthielt.
add(index, e), addAll(index, c) und addFirst(e) müssen dagegen alle Elemente ab der Einfügeposition nach hinten verschieben – um so viele Stellen, wie neue Elemente hinzukommen. Bei einer langen Liste kostet das Zeit – wie viel, steht im Abschnitt Zeitkomplexität der ArrayList.
Fügst du mehrere Elemente ein, ist addAll(index, c) deshalb schneller als eine Schleife mit add(index, e): Es verschiebt jedes Element hinter der Einfügeposition nur einmal. Das folgende Diagramm zeigt beide Wege für das addAll(2, …) aus dem Listing oben:
Als Position ist jeder Index von 0 bis einschließlich size() erlaubt. add(names.size(), x) hängt also ans Ende an, ein größerer Index wirft eine IndexOutOfBoundsException:
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan"));
names.add(names.size(), "Linus");
System.out.println(names);
try {
names.add(20, "Guido");
} catch (IndexOutOfBoundsException e) {
System.out.println(e);
}
[Ada, Grace, Alan, Linus]
java.lang.IndexOutOfBoundsException: Index: 20, Size: 4
Elemente lesen
Ein Element an einer bestimmten Position liest du mit get(), das erste und das letzte seit Java 21 mit getFirst() und getLast():
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan", "Grace"));
System.out.println(names.get(2));
System.out.println(names.getFirst() + " " + names.getLast());
System.out.println(names.size() + " " + names.isEmpty());
Alan
Ada Grace
4 false
size() statt length
Die Anzahl der Elemente liefert size(). Ein Feld length wie beim Array und eine Methode length() wie bei String hat die ArrayList nicht. isEmpty() liefert true, wenn die Liste keine Elemente enthält.
Elemente suchen
Ob die Liste ein Element enthält, prüfst du mit contains(). indexOf() liefert die Position des ersten passenden Elements, lastIndexOf() die des letzten, beide liefern -1, wenn sie keines finden:
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan", "Grace"));
System.out.println(names.contains("Alan"));
System.out.println(names.indexOf("Grace") + " " + names.lastIndexOf("Grace"));
System.out.println(names.indexOf("Linus"));
true
1 3
-1
Alle drei Methoden vergleichen mit equals(), nicht mit ==. Für Strings und Wrapper-Klassen wie Integer funktioniert das ohne dein Zutun. Für eigene Klassen musst du equals() überschreiben – sonst findet contains() nur genau dasselbe Objekt, wie der Abschnitt Häufige Fehler zeigt.
Dazu gehen die drei Methoden die Liste Element für Element durch. Bei einer Million Elementen sind das bis zu eine Million equals()-Aufrufe. Suchst du oft, ist ein HashSet oder eine HashMap die bessere Datenstruktur.
Ungültiger Index und leere Liste
Ein Index außerhalb von 0 bis size() - 1 führt bei get() zu einer IndexOutOfBoundsException. getFirst() und getLast() werfen auf einer leeren Liste dagegen eine NoSuchElementException:
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan", "Grace"));
try {
names.get(4);
} catch (IndexOutOfBoundsException e) {
System.out.println(e);
}
List<String> empty = new ArrayList<>();
try {
empty.getFirst();
} catch (NoSuchElementException e) {
System.out.println(e);
}
try {
empty.get(0);
} catch (IndexOutOfBoundsException e) {
System.out.println(e);
}
java.lang.IndexOutOfBoundsException: Index 4 out of bounds for length 4
java.util.NoSuchElementException
java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
Die Meldung nennt mit „length“ die Größe der Liste, nicht die Länge des internen Arrays. Beim Einfügen mit add(index, e) lautet die Meldung übrigens anders („Index: 20, Size: 4“, siehe oben), weil add() den Index mit einer eigenen Methode der ArrayList prüft und get() mit Objects.checkIndex().
Elemente ändern
Ein Element an einer bestimmten Position ersetzt du mit set(). Die Methode liefert das Element zurück, das vorher dort stand. Alle Elemente auf einmal ersetzt du seit Java 8 mit replaceAll(), das jedes Element durch das Ergebnis einer Funktion ersetzt:
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan"));
String replaced = names.set(1, "Linus");
System.out.println(replaced + " -> " + names);
names.replaceAll(String::toUpperCase);
System.out.println(names);
Grace -> [Ada, Linus, Alan]
[ADA, LINUS, ALAN]
set() ändert die Größe der Liste nicht und kann daher nur an Positionen schreiben, an denen schon ein Element steht – auch das zeigt der Abschnitt Häufige Fehler.
Elemente entfernen
Ein einzelnes Element entfernst du mit remove() – entweder über seine Position oder über das Element selbst. remove(int) liefert das entfernte Element zurück, remove(Object) liefert true, wenn es ein gleiches Element gefunden und entfernt hat. Seit Java 21 kommen removeFirst() und removeLast() hinzu:
List<String> names =
new ArrayList<>(List.of("Ada", "Grace", "Alan", "Linus", "James", "Barbara"));
String removed = names.remove(1);
System.out.println(removed + " -> " + names);
boolean found = names.remove("Linus");
System.out.println(found + " -> " + names);
names.removeFirst();
System.out.println(names);
Grace -> [Ada, Alan, Linus, James, Barbara]
true -> [Ada, Alan, James, Barbara]
[Alan, James, Barbara]
remove(Object) entfernt nur das erste gleiche Element. Wie beim Einfügen muss die ArrayList dabei alle Elemente dahinter verschieben – hier um eine Stelle nach vorn.
remove(int) oder remove(Object)?
Bei einer List<Integer> ist nicht offensichtlich, welche der beiden Methoden ein Aufruf trifft. Das folgende Listing will aus der Liste [10, 20, 30, 1] die Zahl 1 entfernen:
List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30, 1));
numbers.remove(1);
System.out.println(numbers);
numbers.remove(Integer.valueOf(1));
System.out.println(numbers);
[10, 30, 1]
[10, 30]
Der erste Aufruf entfernt die 20. Der Compiler wählt für das Argument 1 vom Typ int die Methode remove(int), weil sie ohne Autoboxing passt – und entfernt das Element an Position 1. Erst remove(Integer.valueOf(1)) übergibt ein Objekt und trifft remove(Object).
Mehrere Elemente entfernen
Seit Java 8 kannst du mit removeIf() alle Elemente entfernen, auf die eine Bedingung zutrifft. Mit removeAll() kannst du alle Elemente entfernen, die in einer anderen Collection enthalten sind, mit retainAll() behältst du alle Elemente, die in einer anderen Collection enthalten sind:
List<String> pioneers =
new ArrayList<>(List.of("Ada", "Grace", "Alan", "Linus", "James", "Barbara"));
pioneers.removeIf(name -> name.startsWith("A"));
System.out.println(pioneers);
pioneers.removeAll(List.of("Grace", "James"));
System.out.println(pioneers);
pioneers.retainAll(List.of("Barbara", "Ken"));
System.out.println(pioneers);
[Grace, Linus, James, Barbara]
[Linus, Barbara]
[Barbara]
Alle drei Methoden verschieben jedes verbleibende Element höchstens einmal. Sie sind daher schneller als eine Schleife, die die Elemente einzeln mit remove() entfernt – dort rücken die hinteren Elemente bei jedem Aufruf erneut auf. Das folgende Diagramm zeigt beide Wege für das removeIf() aus dem Listing oben:
Einen Bereich oder alle Elemente entfernen
Einen zusammenhängenden Bereich entfernst du, indem du clear() auf einer mit subList() erzeugten View aufrufst. Alle Elemente entfernst du mit clear() auf der Liste selbst:
List<Integer> digits = new ArrayList<>(List.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
digits.subList(2, 5).clear();
System.out.println(digits);
digits.clear();
System.out.println(digits + " " + digits.size());
[0, 1, 5, 6, 7, 8, 9]
[] 0
subList(2, 5) umfasst die Positionen 2, 3 und 4 – der erste Index gehört dazu, der zweite nicht. Was eine View ist, steht im Abschnitt subList() liefert eine View.
Über eine ArrayList iterieren
Für das Durchlaufen einer ArrayList gibt es fünf Wege. Das folgende Listing zeigt die ersten drei – die for-each-Schleife, die Schleife über den Index und die Methode forEach():
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan"));
for (String name : names) {
System.out.println(name);
}
for (int i = 0; i < names.size(); i++) {
System.out.println(i + ": " + names.get(i));
}
names.forEach(System.out::println);
Ada
Grace
Alan
0: Ada
1: Grace
2: Alan
Ada
Grace
Alan
Ich empfehle dir die for-each-Schleife. Die Schleife über den Index brauchst du nur, wenn du die Position des Elements benötigst.
Der vierte Weg ist der ListIterator. Mit ihm kannst du beim Durchlaufen das aktuelle Element ersetzen und hinter ihm neue Elemente einfügen. Das folgende Listing ersetzt „Grace“ durch „Grace Hopper“ und fügt dahinter „Linus“ ein:
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan"));
ListIterator<String> iterator = names.listIterator();
while (iterator.hasNext()) {
String name = iterator.next();
if (name.equals("Grace")) {
iterator.set("Grace Hopper");
iterator.add("Linus");
}
}
System.out.println(names);
[Ada, Grace Hopper, Linus, Alan]
Der fünfte Weg ist ein Stream. Er lohnt sich, wenn du die Elemente filtern, umwandeln oder zusammenfassen willst. Das folgende Listing sammelt alle Namen mit höchstens vier Zeichen in einer neuen Liste:
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan"));
List<String> shortNames = names.stream()
.filter(name -> name.length() <= 4)
.toList();
System.out.println(shortNames);
[Ada, Alan]
Rückwärts iterieren
Rückwärts durchläufst du eine ArrayList seit Java 21 mit reversed(). Die Methode liefert eine View in umgekehrter Reihenfolge, ohne die Elemente zu kopieren:
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan"));
for (String name : names.reversed()) {
System.out.println(name);
}
Alan
Grace
Ada
Mehr zu reversed() und den anderen mit Java 21 eingeführten Methoden zeigt der Artikel Sequenced Collections.
ConcurrentModificationException
Wenn du in einer for-each-Schleife ein Element mit remove() entfernst, dann wirft die nächste Iteration eine ConcurrentModificationException. Das folgende Listing versucht, alle Namen zu entfernen, die mit „A“ beginnen:
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan", "Linus"));
try {
for (String name : names) {
if (name.startsWith("A")) {
names.remove(name);
}
}
} catch (ConcurrentModificationException e) {
System.out.println(e);
}
System.out.println(names);
java.util.ConcurrentModificationException
[Grace, Alan, Linus]
„Ada“ ist entfernt, „Alan“ nicht – die Schleife bricht beim nächsten Element ab.
Der Grund: Die for-each-Schleife läuft über einen Iterator. Die ArrayList zählt in einem Feld modCount jede Änderung ihrer Größe mit, außerdem jedes sort() und replaceAll() – ein set() dagegen nicht. Wenn der Iterator erzeugt wird, merkt er sich diesen Wert, und bei jedem next() vergleicht er diesen Wert mit dem aktuellen Wert von modCount. Stimmen die Werte nicht überein, wirft er die ConcurrentModificationException. Diesen Mechanismus nennt die Dokumentation fail-fast: Der Iterator bricht sofort ab, statt mit einem veralteten Stand weiterzuarbeiten.
Das folgende Diagramm zeigt die Schritte des Listings oben:
Nebenläufig ist in diesem Beispiel nichts – ein einziger Thread ändert die Liste, während er über sie iteriert. Gedacht ist der Mechanismus aber auch für den nebenläufigen Fall: Ändert ein anderer Thread die Liste, während ein Thread über sie iteriert, bricht der Iterator ebenfalls mit einer ConcurrentModificationException ab. Garantiert ist das allerdings nicht – ohne Synchronisierung bemerkt der Iterator die Änderung nicht immer, denn modCount ist nicht volatile, und so sieht der iterierende Thread den neuen Wert unter Umständen nicht. Die Dokumentation rät deshalb, sich nicht auf die Exception zu verlassen, sondern sie nur zu nutzen, um Fehler zu erkennen.
Gefährlicher ist der Fall, in dem keine Exception geworfen wird. Entfernst du das vorletzte Element, endet die Schleife ohne Fehler – und das letzte Element wird nie besucht:
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan", "Linus"));
for (String name : names) {
System.out.println("Visiting " + name);
if (name.equals("Alan")) {
names.remove(name);
}
}
System.out.println(names);
Visiting Ada
Visiting Grace
Visiting Alan
[Ada, Grace, Linus]
Das liegt an hasNext(): Die Methode vergleicht nur die Position des Iterators mit der Größe der Liste und prüft modCount nicht. Nach dem Entfernen ist die Liste drei Elemente lang, und der Iterator steht hinter dem dritten Element. hasNext() liefert false, und das next(), das die Änderung bemerkt hätte, wird nie aufgerufen.
Es gibt drei Wege, um beim Durchlaufen Elemente richtig zu entfernen:
-
removeIf(): der kürzeste Weg, wenn eine Bedingung entscheidet, welche Elemente entfernt werden sollen:names.removeIf(name -> name.startsWith("A")); -
Iterator.remove(): entfernt das zuletzt mitnext()gelieferte Element und passt den gemerktenmodCountdes Iterators an:Iterator<String> iterator = names.iterator(); while (iterator.hasNext()) { if (iterator.next().startsWith("A")) { iterator.remove(); } } -
Schleife über den Index, von hinten: Das Entfernen verschiebt nur die Elemente hinter der aktuellen Position – und die hat die Schleife schon besucht:
for (int i = names.size() - 1; i >= 0; i--) { if (names.get(i).startsWith("A")) { names.remove(i); } }
Alle drei Wege liefern für die Liste [Ada, Grace, Alan, Linus] das Ergebnis [Grace, Linus]. Ich empfehle dir removeIf(): Es ist am kürzesten, und es verschiebt jedes verbleibende Element nur einmal, wie im Abschnitt Mehrere Elemente entfernen beschrieben.
Eine ArrayList sortieren und durchsuchen
Eine ArrayList sortierst du mit sort(). Mit null als Argument sortiert die Methode nach der natürlichen Ordnung der Elemente, mit einem Comparator in jeder anderen Reihenfolge. Das folgende Listing sortiert fünf Namen erst alphabetisch und dann nach ihrer Länge:
List<String> names =
new ArrayList<>(List.of("Grace", "Ada", "Linus", "Barbara", "Alan"));
names.sort(null);
System.out.println(names);
names.sort(Comparator.comparing(String::length)
.thenComparing(Comparator.naturalOrder()));
System.out.println(names);
[Ada, Alan, Barbara, Grace, Linus]
[Ada, Alan, Grace, Linus, Barbara]
Wie du absteigend, nach mehreren Feldern und mit Umlauten sortierst, zeigt der Artikel Liste sortieren in Java.
In einer sortierten Liste findest du ein Element mit Collections.binarySearch() in O(log n) – indexOf() würde O(n) benötigen:
List<String> names =
new ArrayList<>(List.of("Ada", "Alan", "Barbara", "Grace", "Linus"));
System.out.println(Collections.binarySearch(names, "Grace"));
System.out.println(Collections.binarySearch(names, "Ken"));
3
-5
„Grace“ steht in [Ada, Alan, Barbara, Grace, Linus] an Position 3. Für „Ken“, das fehlt, liefert die Methode -(Einfügeposition + 1): „Ken“ gehörte an Position 4, vor „Linus“. Wie die Suche funktioniert, erklärt der Artikel über die binäre Suche.
Eine ArrayList umwandeln und kopieren
ArrayList in ein Array umwandeln
In ein Array umwandeln kannst du eine ArrayList mit toArray(). Ohne Parameter liefert die Methode ein Object[], auch bei einer List<String>. Ein String[] bekommst du, wenn du ein leeres Array des gewünschten Typs übergibst oder – seit Java 11 – den Konstruktor eines solchen Arrays als Methodenreferenz:
List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan"));
Object[] array1 = names.toArray();
String[] array2 = names.toArray(new String[0]);
String[] array3 = names.toArray(String[]::new);
System.out.println(array1.getClass().getSimpleName() + " " + Arrays.toString(array1));
System.out.println(array2.getClass().getSimpleName() + " " + Arrays.toString(array2));
System.out.println(array3.getClass().getSimpleName() + " " + Arrays.toString(array3));
Object[] [Ada, Grace, Alan]
String[] [Ada, Grace, Alan]
String[] [Ada, Grace, Alan]
Ein int[] kannst du mit toArray() nicht erzeugen – dafür brauchst du einen Stream, der die Integer-Objekte mit mapToInt() in int-Werte umwandelt:
List<Integer> numbers = new ArrayList<>(List.of(3, 1, 4, 1, 5));
int[] ints = numbers.stream()
.mapToInt(Integer::intValue)
.toArray();
System.out.println(Arrays.toString(ints));
[3, 1, 4, 1, 5]
Ein Array in eine ArrayList umwandeln
Ein Array von Objekten machst du mit Arrays.asList() zur Liste und übergibst diese an den Konstruktor der ArrayList. Bei einem int[] musst du zunächst mit boxed() die int-Werte in einem Stream in Integer-Objekte umwandeln und den Stream mit toList() zu einer Liste machen:
String[] languages = {"Java", "Kotlin", "Scala"};
List<String> languageList = new ArrayList<>(Arrays.asList(languages));
languageList.add("Groovy");
System.out.println(languageList);
int[] primes = {2, 3, 5, 7};
List<Integer> primeList = new ArrayList<>(Arrays.stream(primes)
.boxed()
.toList());
primeList.add(11);
System.out.println(primeList);
[Java, Kotlin, Scala, Groovy]
[2, 3, 5, 7, 11]
Beide Listen nehmen danach neue Elemente auf – anders als die Listen, die Arrays.asList() und Stream.toList() selbst liefern.
Eine ArrayList kopieren
Eine Kopie erzeugst du mit dem Konstruktor new ArrayList<>(original). Eine unveränderliche Kopie liefert seit Java 10 List.copyOf(original). Auch clone() kopiert die Liste. Die Methode kannst du aber nur über eine Variable vom Typ ArrayList aufrufen – List hat sie nicht. Über eine List-Variable findet der Compiler die Methode gar nicht:
List<String> names = new ArrayList<>(List.of("Ada", "Grace"));
List<String> copy = names.clone();
error: cannot find symbol
List<String> copy = names.clone();
^
symbol: method clone()
Außerdem gibt clone() ein Object zurück, du musst das Ergebnis also casten. Weil der Compiler den Cast auf ArrayList<String> nicht prüfen kann, warnt er davor – die Annotation @SuppressWarnings("unchecked") unterdrückt die Warnung:
ArrayList<String> pioneers = new ArrayList<>(List.of("Ada", "Grace"));
@SuppressWarnings("unchecked")
ArrayList<String> pioneersCopy = (ArrayList<String>) pioneers.clone();
System.out.println(pioneersCopy);
[Ada, Grace]
Der Konstruktor new ArrayList<>(original) ist deutlich einfacher.
Alle drei Kopien sind übrigens flach: Sie kopieren die Referenzen, nicht die Objekte dahinter. Das folgende Listing verlängert über die Kopie einen StringBuilder – und das Original zeigt die Änderung ebenfalls:
List<StringBuilder> original = new ArrayList<>(List.of(new StringBuilder("Ada")));
List<StringBuilder> copy = new ArrayList<>(original);
copy.getFirst().append(" Lovelace");
System.out.println("original: " + original);
System.out.println("copy: " + copy);
original: [Ada Lovelace]
copy: [Ada Lovelace]
Originalliste und Kopie zeigen auf denselben StringBuilder:
Bei unveränderlichen Elementen wie String oder Integer spielt das keine Rolle, denn niemand kann sie über die Kopie verändern.
subList() liefert eine View
subList(from, to) kopiert nichts, sondern liefert eine View – eine Sicht auf einen Bereich der ursprünglichen Liste. Was du über die View änderst, ändert die ursprüngliche Liste:
List<Integer> digits = new ArrayList<>(List.of(0, 1, 2, 3, 4, 5));
List<Integer> middle = digits.subList(2, 4);
middle.set(0, 20);
System.out.println(digits);
[0, 1, 20, 3, 4, 5]
Die View ist nur ein Fenster auf zwei Positionen der ursprünglichen Liste: Ihr Index 0 ist Index 2 von digits.
Über die View kannst du sogar ihre Größe ändern, z. B. mit add(), remove() oder clear(). Auch diese Änderungen kommen in der ursprünglichen Liste an, und die View bleibt dabei gültig. clear() auf der View entfernt so den ganzen Bereich aus der ursprünglichen Liste – davon macht auch der Abschnitt Einen Bereich oder alle Elemente entfernen Gebrauch:
List<Integer> digits = new ArrayList<>(List.of(0, 1, 2, 3, 4, 5));
List<Integer> middle = digits.subList(2, 4);
middle.add(99);
System.out.println(digits + " " + middle);
middle.remove(0);
System.out.println(digits + " " + middle);
middle.clear();
System.out.println(digits + " " + middle);
[0, 1, 2, 3, 99, 4, 5] [2, 3, 99]
[0, 1, 3, 99, 4, 5] [3, 99]
[0, 1, 4, 5] []
add(99) hängt die 99 ans Ende der View, in digits landet sie also hinter der 3 an Position 4.
Änderst du dagegen die Größe der ursprünglichen Liste, wird die View ungültig:
List<Integer> digits = new ArrayList<>(List.of(0, 1, 2, 3, 4, 5));
List<Integer> middle = digits.subList(2, 4);
digits.add(6);
try {
System.out.println(middle);
} catch (ConcurrentModificationException e) {
System.out.println(e);
}
java.util.ConcurrentModificationException
Wenn du den Bereich länger brauchst und Änderungen daran nicht auf die ursprüngliche Liste durchgreifen sollen, kopierst du ihn am besten mit new ArrayList<>(digits.subList(2, 4)).
Wie die ArrayList intern arbeitet
Die ArrayList speichert ihre Elemente in einem Array vom Typ Object[] im Feld elementData. Ein zweites Feld, size, zählt, wie viele Plätze davon belegt sind.
Die Länge des Arrays heißt Kapazität (capacity). Sie ist immer mindestens so groß wie size, meistens größer. Das folgende Diagramm zeigt eine ArrayList mit fünf Elementen in einem Array mit zehn Plätzen. Die Zahlen über den Plätzen sind die Indizes, die Klammern darunter markieren size und die Kapazität:
Die leeren Plätze sind die Reserve für die nächsten Aufrufe von add().
Kapazität sichtbar machen
Die Kapazität gibt die ArrayList nicht preis. Das Beispiel-Repository liest sie daher in der Klasse Ch10Capacity per Reflection aus dem privaten Feld elementData. Dafür musst du das Package java.util beim Start mit der VM-Option --add-opens java.base/java.util=ALL-UNNAMED öffnen – ohne die Option wirft setAccessible(true) eine InaccessibleObjectException.
Das folgende Listing fügt einer leeren ArrayList 100 Elemente hinzu und gibt die Kapazität jedes Mal aus, wenn sie sich ändert:
ArrayList<Integer> list = new ArrayList<>();
System.out.println("size 0, capacity " + capacity(list));
int lastCapacity = capacity(list);
for (int i = 1; i <= 100; i++) {
list.add(i);
if (capacity(list) != lastCapacity) {
lastCapacity = capacity(list);
System.out.println("size " + list.size() + ", capacity " + lastCapacity);
}
}
size 0, capacity 0
size 1, capacity 10
size 11, capacity 15
size 16, capacity 22
size 23, capacity 33
size 34, capacity 49
size 50, capacity 73
size 74, capacity 109
Die Methode capacity() steht in der Klasse Ch10Capacity und liefert die Länge von elementData.
Nach welcher Regel die Kapazität von 10 auf 15, 22, 33 und so weiter steigt, erkläre ich im Abschnitt Wie die ArrayList wächst.
Die leere Liste und das erste add()
Die erste Zeile der Ausgabe im vorherigen Abschnitt zeigt: Eine mit new ArrayList<>() erzeugte Liste hat die Kapazität 0. Sie hat also noch kein Array mit Plätzen, sondern verweist auf ein leeres Array, die Konstante DEFAULTCAPACITY_EMPTY_ELEMENTDATA. Jede mit new ArrayList<>() erzeugte Liste verweist auf dieses eine leere Array. Erst das erste add() legt ein Array mit zehn Plätzen an – so viele, wie die Konstante DEFAULT_CAPACITY vorgibt.
Viele leere Listen kosten so nur ihre eigenen Objekte, kein Array.
Einfügen und Entfernen in der Mitte
Fügst du ein Element mit add(index, e) ein, verschiebt die ArrayList alle Elemente ab index mit System.arraycopy() um einen Platz nach hinten und schreibt das neue Element in die Lücke. Das folgende Diagramm zeigt add(2, "Ken") auf der Liste [Ada, Grace, Alan, Linus, James] in einem Array mit sieben Plätzen, vorher und nachher. Die gestrichelten Pfeile zeigen, welche Elemente System.arraycopy() verschiebt:
remove(index) verschiebt umgekehrt alle Elemente hinter index um einen Platz nach vorn und setzt den frei gewordenen letzten Platz auf null. Dort stünde sonst noch eine Kopie der Referenz auf das letzte Element. Solange das Array diese Kopie hält, kann der Garbage Collector das Objekt nicht aufräumen – auch dann nicht, wenn es später aus der Liste entfernt wird und sonst nirgends mehr referenziert ist.
Je weiter vorn die Position liegt, desto mehr Elemente muss die ArrayList verschieben. Bei add(0, e) und remove(0) sind es alle. Und je mehr Elemente sie verschieben muss, desto länger dauert das Einfügen oder Entfernen – wie sich das in Zahlen ausdrückt, steht im Abschnitt Zeitkomplexität der ArrayList.
Wie die ArrayList wächst
Ist das Array voll, legt die ArrayList beim nächsten add() ein um die Hälfte größeres Array an und kopiert die Elemente mit Arrays.copyOf() in das neue Array. Aus 10 Plätzen werden 15, aus 15 werden 22 (15 plus 15 / 2 = 7, abgerundet), aus 22 werden 33.
Das folgende Diagramm zeigt den Schritt von 10 auf 15 Plätze beim elften add(). Die Liste enthält wie im Listing unter Kapazität sichtbar machen die Zahlen 1 bis 10. Die gestrichelten Pfeile zeigen, wohin Arrays.copyOf() die Elemente kopiert und wo die 11 aus add(11) landet:
Das alte Array wird danach nicht mehr referenziert, und der Garbage Collector gibt es frei.
Im JDK-Quellcode berechnet die private Methode grow() die neue Länge mit ArraysSupport.newLength(): die alte Länge plus den größeren von zwei Zuwächsen – dem bevorzugten, der halben alten Länge (oldCapacity >> 1), und dem mindestens nötigen. Der mindestens nötige gewinnt, wenn addAll() mehr Elemente auf einmal hinzufügt, als die Hälfte hergibt: Fügst du einer vollen Liste mit zehn Elementen 100 weitere hinzu, wächst das Array direkt auf 110 Plätze.
Der Zuwachs um die Hälfte ist ein Implementierungsdetail. Die Dokumentation der ArrayList legt nur fest, dass add() in amortisiert konstanter Zeit läuft. Amortisiert konstant bedeutet: Ein einzelnes add() kann teuer sein, weil es das ganze Array kopiert. Weil aber jede Kopie die Kapazität um die Hälfte erhöht, folgen auf eine Kopie von n Elementen mindestens n / 2 add()-Aufrufe ohne Kopie. Über alle Aufrufe gerechnet kostet jedes add() also eine konstante Zeit, O(1).
Eine mit new ArrayList<>(0) erzeugte Liste wächst übrigens anders: Sie startet mit dem zweiten leeren Array EMPTY_ELEMENTDATA und wächst über 1, 2, 3, 4, 6, 9 und 13 Plätze – immer um die Hälfte, aber mindestens um einen Platz.
Das Array schrumpft nicht von selbst
Wenn das interne Array voll ist, ersetzt die ArrayList es automatisch durch ein größeres – durch ein kleineres ersetzt sie es nie. Entfernst du Elemente, behält das Array also seine Länge.
Das kann Speicher kosten: War eine Liste einmal sehr groß und hast du danach die meisten Elemente entfernt, belegt sie weiterhin das große Array – mit lauter leeren Plätzen, die auf null stehen. Bei einem Array mit einer Million Plätzen sind das rund 4 MB, auch wenn nur noch zehn Elemente darin liegen.
Mit trimToSize() verkleinerst du das Array auf die Größe der Liste:
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 11; i++) {
list.add(i);
}
System.out.println("size " + list.size() + ", capacity " + capacity(list));
for (int i = 0; i < 8; i++) {
list.removeLast();
}
System.out.println("size " + list.size() + ", capacity " + capacity(list));
list.trimToSize();
System.out.println("size " + list.size() + ", capacity " + capacity(list));
size 11, capacity 15
size 3, capacity 15
size 3, capacity 3
Mit ensureCapacity() vergrößerst du das Array im Voraus:
ArrayList<Integer> list = new ArrayList<>(List.of(0, 1, 2));
System.out.println("size " + list.size() + ", capacity " + capacity(list));
list.ensureCapacity(1_000);
System.out.println("size " + list.size() + ", capacity " + capacity(list));
size 3, capacity 3
size 3, capacity 1000
Beide Methoden gibt es nur in der Klasse ArrayList, nicht im Interface List.
Kennst du die Anzahl der Elemente im Voraus, gibst du sie am besten gleich dem Konstruktor mit, z. B. new ArrayList<>(1_000). Dann legt die ArrayList ein einziges Array an. Mit Standardkapazität legt sie beim Füllen bis zum 1.000. Element 13 Arrays an und kopiert die Elemente zwölfmal um – das letzte Array hat 1.234 Plätze.
Speicherbedarf der ArrayList
Das interne Array einer ArrayList enthält nur Referenzen. Die Elemente selbst sind eigene Objekte im Heap. Bei einer ArrayList<Integer> kostet jedes Element daher zweimal Speicher: 4 Byte für die Referenz im Array und 16 Byte für das Integer-Objekt. Ein int[] speichert dieselbe Zahl in 4 Byte:
Für eine Million Zahlen sind das rund 20 MB gegen 4 MB. Eine Ausnahme bilden die Zahlen von -128 bis 127: Für sie liefert das Autoboxing Integer-Objekte aus einem Cache, die sich alle Listen teilen.
Mit Project Valhalla wird Integer zu einer Value Class. Was das für Integer-Arrays bedeutet und warum eine ArrayList davon zunächst nicht profitiert, steht im Abschnitt Wann die JVM ein Value Object flach ablegt des Valhalla-Artikels.
Zeitkomplexität der ArrayList
Die folgende Tabelle zeigt die Zeitkomplexität der wichtigsten Operationen einer ArrayList mit n Elementen. Die Begründungen stehen in den Abschnitten Wie die ArrayList intern arbeitet und Wie die ArrayList wächst:
| Operation | Zeitkomplexität | Begründung |
|---|---|---|
get(i), set(i, e) | O(1) | ein Zugriff auf das interne Array |
size(), isEmpty() | O(1) | liest das Feld size |
add(e) am Ende | O(1) amortisiert | meist nur ein Schreibzugriff, selten zusätzlich eine Kopie des ganzen Arrays |
add(i, e),remove(i) in der Mitte | O(n) | verschiebt die Elemente hinter Index i |
add(0, e),remove(0) am Anfang | O(n) | verschiebt alle Elemente |
remove(size() - 1) am Ende | O(1) | verschiebt nichts |
contains(o), indexOf(o) | O(n) | vergleicht Element für Element mit equals() |
Beim Verschieben fasst die ArrayList die Elemente nicht einzeln an: System.arraycopy() kopiert die Referenzen als einen zusammenhängenden Speicherbereich.
Was O(1) und O(n) bedeutet, erklärt der Artikel über die O-Notation.
ArrayList vs. LinkedList, Vector und CopyOnWriteArrayList
ArrayList vs. LinkedList
Eine LinkedList speichert jedes Element in einem eigenen Knoten, der auf seinen Vorgänger und seinen Nachfolger zeigt. Das Einfügen selbst kostet sie O(1): Steht sie schon an der richtigen Stelle, z. B. mit einem ListIterator, hängt sie den neuen Knoten nur zwischen zwei andere. Die ArrayList braucht dafür O(n), weil sie alle Elemente dahinter verschiebt.
Um zu dieser Position zu gelangen, muss die LinkedList allerdings von einem Ende aus den Verweisen von Knoten zu Knoten folgen – das kostet selbst O(n). Dazu kommt ein eigenes Knoten-Objekt pro Element, und die Knoten liegen meist nicht nebeneinander im Speicher – der CPU-Cache lädt also mit einem Knoten keine Nachbarn mit. Wie sich Arrays und verkettete Listen in Speicher und Lokalität unterscheiden, zeigt der Artikel Array vs. Linked List.
Ich empfehle dir die ArrayList als Standard für Listen. Brauchst du eine Queue oder einen Stack, der an beiden Enden in O(1) einfügt und entnimmt, nimm ein ArrayDeque.
Vector
Vector ist der Vorgänger der ArrayList aus Java 1.0. Die Klasse arbeitet ebenfalls mit einem Array, verdoppelt es beim Wachsen aber, und alle ihre Methoden sind synchronized. Die Javadoc der Klasse empfiehlt die ArrayList, wenn du keine threadsichere Liste brauchst. Brauchst du eine threadsichere Liste, nimm einen der beiden Wege aus dem nächsten Abschnitt.
Threadsichere Listen
Eine ArrayList ist nicht threadsicher. Ändern mehrere Threads sie gleichzeitig, können Elemente verloren gehen, oder es werden Exceptions geworfen. Für Listen, die mehrere Threads teilen, gibt es zwei Wege:
Collections.synchronizedList(new ArrayList<>()): umhüllt die Liste und synchronisiert jeden Methodenaufruf. Iterierst du über die Liste, musst du die Schleife zusätzlich selbst in einensynchronized-Block auf der Liste setzen.CopyOnWriteArrayList: kopiert bei jeder Änderung das ganze Array. Ein Iterator arbeitet auf dem Stand, den das Array bei seiner Erzeugung hatte, und wirft nie eineConcurrentModificationException. Das lohnt sich für Listen, die selten geändert und oft gelesen werden – etwa eine Liste von Event-Listenern.
Häufige Fehler
Die folgenden Fehler zeigen die Abschnitte oben ausführlich oder das folgende Listing:
remove(1)auf einerList<Integer>: entfernt das Element an Position 1, nicht die Zahl 1. Die Zahl entfernst du mitremove(Integer.valueOf(1)).remove()in einer for-each-Schleife: wirft eineConcurrentModificationExceptionoder überspringt still das letzte Element. Entferne stattdessen mitremoveIf().add()auf einer Liste ausList.of()oderArrays.asList(): wirft eineUnsupportedOperationException. Kopiere sie zuerst in eine neueArrayList.set()auf einer Liste mit Anfangskapazität: Die Kapazität ist nicht die Größe –new ArrayList<>(10)ist leer, undset(0, …)wirft eineIndexOutOfBoundsException. Fülle die Liste mitadd().Integer-Elemente mit==vergleichen: vergleicht Referenzen, nicht Werte. Für -128 bis 127 stimmt das Ergebnis nur, weil Autoboxing diese Zahlen aus einem Cache holt – ab 128 nicht mehr. Vergleiche mitequals().contains()mit eigenen Klassen ohneequals(): findet nur dasselbe Objekt, kein gleiches. Überschreibeequals()undhashCode()oder nimm einen Record, der beide mitbringt.add(0, …)in einer Schleife über viele Elemente: verschiebt bei jedem Aufruf die ganze Liste. Hänge mitadd()an und kehre die Liste am Ende mitCollections.reverse()um – oder nimm einArrayDeque.
Das folgende Listing zeigt die Fehler mit der Kapazität, mit == und mit contains(). Es verwendet zwei Typen mit denselben Feldern – eine Klasse ohne equals() und einen Record:
class Point {
final int x;
final int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
record PointRecord(int x, int y) {}
So wirken sich die drei Fehler aus:
List<String> names = new ArrayList<>(10);
try {
names.set(0, "Ada");
} catch (IndexOutOfBoundsException e) {
System.out.println(e);
}
List<Integer> small = new ArrayList<>(List.of(127, 127));
List<Integer> large = new ArrayList<>(List.of(128, 128));
System.out.println(small.get(0) == small.get(1));
System.out.println(large.get(0) == large.get(1));
System.out.println(large.get(0).equals(large.get(1)));
List<Point> points = new ArrayList<>(List.of(new Point(1, 2)));
System.out.println(points.contains(new Point(1, 2)));
List<PointRecord> records = new ArrayList<>(List.of(new PointRecord(1, 2)));
System.out.println(records.contains(new PointRecord(1, 2)));
java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
true
false
true
false
true
Zusammenfassung
Eine ArrayList speichert ihre Elemente in einem Array und liest und schreibt sie per Index in O(1). Ist das Array voll, wird es durch ein um die Hälfte größeres ersetzt. So erfolgt das Hinzufügen von Elementen am Ende in amortisiert O(1). Einfügen und Entfernen am Anfang oder in der Mitte hingegen kostet O(n), weil die Elemente dahinter verschoben werden müssen.
Eine mit new ArrayList<>() erzeugte Liste legt ihr Array erst beim ersten add() an, mit zehn Plätzen. Das Array schrumpft nicht von selbst; trimToSize() verkleinert es.
List.of() und Arrays.asList() liefern keine ArrayList. Eine veränderbare Liste bekommst du erst, indem du das Ergebnis von List.of() und Arrays.asList() an new ArrayList<>(…) übergibst.
Eine ArrayList<Integer> braucht pro Element 20 Byte – fünfmal so viel wie ein int[], weil jede Zahl ein eigenes Integer-Objekt ist, das aus dem Array referenziert wird.
Meine Empfehlungen:
- Nimm die
ArrayListals Standard für Listen und deklariere die Variable mit dem InterfaceList. - Kennst du die Anzahl der Elemente, gib sie dem Konstruktor als Anfangskapazität mit.
- Willst du Elemente nach einer Bedingung entfernen, nimm
removeIf()– nieremove()in einer for-each-Schleife. - Vergleiche Elemente mit
equals(), nie mit==, und implementiere in eigenen Elementklassenequals()undhashCode()– besser noch: nimm einen Record. - Nimm für Queues und Stacks ein
ArrayDeque, für große Mengen primitiver Zahlen ein Array.
Wie du eine Liste sortierst, zeigt der Artikel Liste sortieren in Java. Wie du auf das erste und letzte Element zugreifst und rückwärts iterierst, zeigt der Artikel Sequenced Collections. Was eine LinkedList anders macht als die ArrayList, zeigt der Artikel Java LinkedList.
Konntest du etwas aus diesem Artikel mitnehmen? Mit einer Bewertung auf meinem ProvenExpert-Profil hilfst du anderen Entwickler:innen einzuschätzen, ob sich das Lesen lohnt – und mir zu verstehen, welche Inhalte dir weiterhelfen.




