Koja je složenost dodavanja elementa u ArrayList?

Сложеност додавања елемента у ArrayList у просечном случају је O(1).

Ово се постиже коришћењем динамичког низа, а додавање се врши на крају листе.

// Додавање на крај листе
List<String> list = new ArrayList<>();
list.add("елемент"); // O(1) у просечном случају

Међутим, ако је унутрашњи низ ArrayList попуњен, потребна је операција повећања величине (resize). То укључује креирање новог, већег низа и копирање свих постојећих елемената у нови низ. Ова операција има сложеност O(n), где је n тренутна величина листе.

// Пример где може доћи до resize
List<Integer> numbers = new ArrayList<>(3); // Почетна капацитет 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Овде може доћи до resize - O(n)

Ако се елемент додаје не на крај листе (метод add(int index, E element)), већ у средину или на почетак, потребно је померити све следеће елементе за једну позицију десно. Сложеност ове операције је O(n), где n представља број елемената који треба померити.

// Додавање на почетак листе
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Додавање на почетак - O(n)

Дакле, сложеност додавања елемента у ArrayList зависи од места додавања и потребе за resize-ом:

Операција додавања	Просечан случај	Најгоре (при resize-у или ако се не додаје на крај)
add(E element) (на крај)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)