Kokia yra sudėtingumas pridėti elementą į ArrayList?

Vidutiniškai, elemento pridėjimo sudėtingumas į ArrayList yra O(1).

Tai pasiekiama naudojant dinaminius masyvus, ir pridėjimas vyksta į sąrašo pabaigą.

// Pridėjimas į sąrašo pabaigą
List<String> list = new ArrayList<>();
list.add("element"); // Vidutiniškai O(1)

Tačiau, jei ArrayList vidinis masyvas yra pilnas, reikalinga jo dydžio didinimo operacija (resize). Tai apima naujo, didesnio masyvo sukūrimą ir visų esamų elementų kopijavimą į naują masyvą. Šios operacijos sudėtingumas yra O(n), kur n yra sąrašo dabartinis dydis.

// Pavyzdys, kur gali įvykti resize
List<Integer> numbers = new ArrayList<>(3); // Pradinė talpa 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Čia gali įvykti resize - O(n)

Jei elementas yra pridėtas ne į sąrašo pabaigą (metodu add(int index, E element)), o į vidurį ar pradžią, reikalingas visų vėlesnių elementų perstumimas viena pozicija į dešinę. Šios operacijos sudėtingumas yra O(n), kur n yra perstumtų elementų skaičius.

// Pridėjimas į pradžią
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Pridėjimas į pradžią - O(n)

Taigi, ArrayList elemento pridėjimo sudėtingumas priklauso nuo pridėjimo vietos ir ar reikalingas resize:

Pridėjimo operacija	Vidutinis atvejis	Blogiausias atvejis (resize arba pridėjimas ne į pabaigą)
add(E element) (į pabaigą)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)