Kāda ir sarežģītība, pievienojot elementu uz ArrayList?

Vidēji, elementa pievienošanas sarežģītība ArrayList ir O(1).

Tas tiek panākts, izmantojot dinamiskus masīvus, un pievienošana notiek saraksta beigās.

// Pievienošana saraksta beigās
List<String> list = new ArrayList<>();
list.add("element"); // Vidēji O(1)

Tomēr, ja ArrayList iekšējais masīvs ir pilns, nepieciešama tā izmēra palielināšana (resize). Tas ietver jauna, lielāka masīva izveidi un visu esošo elementu pārkopēšanu jaunajā masīvā. Šīs operācijas sarežģītība ir O(n), kur n ir saraksta pašreizējais izmērs.

// Piemērs, kur var notikt resize
List<Integer> numbers = new ArrayList<>(3); // Sākotnējā ietilpība 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Šeit var notikt resize - O(n)

Ja elements tiek pievienots ne saraksta beigās (metodē add(int index, E element)), bet vidū vai sākumā, nepieciešams pārvietot visus sekojošos elementus par vienu pozīciju uz labo pusi. Šīs operācijas sarežģītība ir O(n), kur n ir pārvietojamo elementu skaits.

// Pievienošana sākumā
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Pievienošana sākumā - O(n)

Tādējādi, ArrayList pievienošanas sarežģītība ir atkarīga no pievienošanas vietas un nepieciešamības pēc resize:

Pievienošanas operācija	Vidējais gadījums	Sliktākais gadījums (resize vai pievienošana ne beigās)
add(E element) (beigā)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)