Aká je zložitosť pridania prvku do ArrayList?

Zložitosť pridania prvku do ArrayList v priemere je O(1).

Toto sa dosahuje použitím dynamického poľa a pridanie sa vykonáva na konci zoznamu.

// Pridanie na koniec zoznamu
List<String> list = new ArrayList<>();
list.add("prvok"); // O(1) v priemere

Avšak, ak je vnútorné pole ArrayList plné, je potrebná operácia zväčšenia veľkosti (resize). To zahŕňa vytvorenie nového, väčšieho poľa a kopírovanie všetkých existujúcich prvkov do nového poľa. Táto operácia má zložitosť O(n), kde n je aktuálna veľkosť zoznamu.

// Príklad, kde môže dôjsť k resize
List<Integer> numbers = new ArrayList<>(3); // Počiatočná kapacita 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Tu môže dôjsť k resize - O(n)

Ak sa prvok pridáva nie na koniec zoznamu (metóda add(int index, E element)), ale do stredu alebo na začiatok, je potrebné posunúť všetky nasledujúce prvky o jednu pozíciu doprava. Zložitosť tejto operácie je O(n), kde n je počet prvkov, ktoré je potrebné posunúť.

// Pridanie na začiatok zoznamu
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Pridanie na začiatok - O(n)

Teda, zložitosť pridania prvku do ArrayList závisí od miesta pridania a od potreby resize:

Operácia pridania	Priemerný prípad	Najhorší prípad (pri resize alebo nepridaní na koniec)
add(E element) (na koniec)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)