Wie hoch ist die Komplexität beim Hinzufügen eines Elements zu ArrayList?

Die Komplexität, ein Element zu ArrayList im Durchschnitt hinzuzufügen, beträgt O(1).

Dies wird durch die Verwendung eines dynamischen Arrays erreicht, und das Hinzufügen erfolgt am Ende der Liste.

// Hinzufügen am Ende der Liste
List<String> list = new ArrayList<>();
list.add("Element"); // O(1) im Durchschnitt

Wenn jedoch das interne Array von ArrayList voll ist, ist eine Resize-Operation erforderlich. Dabei wird ein neues, größeres Array erstellt und alle bestehenden Elemente in das neue Array kopiert. Die Komplexität dieser Operation ist O(n), wobei n die aktuelle Größe der Liste ist.

// Beispiel, bei dem ein Resize auftreten kann
List<Integer> numbers = new ArrayList<>(3); // Anfangskapazität 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Hier kann ein Resize auftreten - O(n)

Wenn ein Element nicht am Ende der Liste hinzugefügt wird (Methode add(int index, E element)), sondern in der Mitte oder am Anfang, müssen alle nachfolgenden Elemente um eine Position nach rechts verschoben werden. Die Komplexität dieser Operation ist O(n), wobei n die Anzahl der zu verschiebenden Elemente ist.

// Hinzufügen am Anfang der Liste
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Hinzufügen am Anfang - O(n)

Daher hängt die Komplexität, ein Element zu ArrayList hinzuzufügen, vom Ort des Hinzufügens und der Notwendigkeit eines Resize ab:

Operation zum Hinzufügen	Durchschnittlicher Fall	Schlimmster Fall (bei Resize oder Nicht-Hinzufügen am Ende)
add(E element) (am Ende)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)