Jaká je složitost přidání prvku do ArrayList?

Složitost přidání prvku do ArrayList v průměrném případě je O(1).

Toho je dosaženo použitím dynamického pole a přidání probíhá na konec seznamu.

// Přidání na konec seznamu
List<String> list = new ArrayList<>();
list.add("prvek"); // O(1) v průměrném případě

Nicméně, pokud je vnitřní pole ArrayList plné, je nutná operace zvětšení velikosti (resize). To zahrnuje vytvoření nového, většího pole a zkopírování všech stávajících prvků do nového pole. Tato operace má složitost O(n), kde n je aktuální velikost seznamu.

// Příklad, kde může dojít k resize
List<Integer> numbers = new ArrayList<>(3); // Počáteční kapacita 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Zde může dojít k resize - O(n)

Pokud je prvek přidáván nikoli na konec seznamu (metoda add(int index, E element)), ale do středu nebo na začátek, je třeba posunout všechny následující prvky o jednu pozici doprava. Složitost této operace je O(n), kde n je počet prvků, které je třeba posunout.

// Přidání na začátek seznamu
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Přidání na začátek - O(n)

Tedy složitost přidání prvku do ArrayList závisí na místě přidání a na nutnosti resize:

Operace přidání	Průměrný případ	Nejhorší případ (při resize nebo nepřidání na konec)
add(E element) (na konec)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)