Jaka jest złożoność dodawania elementu do ArrayList?

Złożoność dodania elementu do ArrayList w przypadku średnim wynosi O(1).

Osiąga się to dzięki użyciu dynamicznej tablicy, a dodanie odbywa się na końcu listy.

// Dodanie na koniec listy
List<String> list = new ArrayList<>();
list.add("element"); // O(1) w przypadku średnim

Jednakże, jeśli wewnętrzna tablica ArrayList jest pełna, konieczna jest operacja powiększenia rozmiaru (resize). Polega ona na utworzeniu nowej, większej tablicy i skopiowaniu wszystkich istniejących elementów do nowej tablicy. Złożoność tej operacji to O(n), gdzie n to obecny rozmiar listy.

// Przykład, gdzie może wystąpić resize
List<Integer> numbers = new ArrayList<>(3); // Początkowa pojemność 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Może wystąpić resize - O(n)

Jeśli element jest dodawany nie na koniec listy (metoda add(int index, E element)), lecz w środek lub na początek, konieczne jest przesunięcie wszystkich kolejnych elementów o jedną pozycję w prawo. Złożoność tej operacji to O(n), gdzie n to liczba elementów do przesunięcia.

// Dodanie na początek listy
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Dodanie na początek - O(n)

Zatem złożoność dodania elementu do ArrayList zależy od miejsca dodania i konieczności resize:

Operacja dodania	Średni przypadek	Najgorszy przypadek (przy resize lub dodaniu nie na koniec)
add(E element) (na koniec)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)