Каква е сложността при добавяне на елемент към 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)