Wie ist die zeitliche Komplexität der Operation zum Hinzufügen eines Elements am Ende eines ArrayList-Arrays?

Die zeitliche Komplexität, ein Element am Ende eines ArrayList-Arrays im Durchschnitt hinzuzufügen, beträgt O(1) — amortisierte Konstante.

Dies liegt daran, dass ArrayList die Elemente in einem Array fester Größe speichert. Wenn wir ein Element hinzufügen und im Array Platz ist, wird das Element einfach in die nächste Zelle eingefügt.

Wenn das Array jedoch voll ist, erfolgt eine Erweiterungsoperation — ein neues Array größerer Größe wird erstellt, und alle Elemente werden hineinkopiert. Diese Operation dauert O(n) Zeit, wobei n die Anzahl der Elemente ist.

Beispiel:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Wenn die Kapazität des Arrays erreicht ist, erfolgt eine Erweiterung — O(n)

Daher beträgt die durchschnittliche Komplexität des Hinzufügens — O(1), im schlimmsten Fall — O(n).