Каква е времевата сложност на основните операции с ArrayList?

Времевата сложност на основните операции с ArrayList в Java:

• Достъп по индекс (get, set): O(1) — директен достъп до елемента по индекс.

• Добавяне на елемент в края (add(E e)): O(1) амортизирано — обикновено бързо, но при препълване на вътрешния масив се извършва копиране, което отнема O(n).

• Вмъкване или изтриване на елемент в средата на списъка (add(index, e), remove(index)): O(n) — заради необходимостта да се преместят елементите след позицията.

• Търсене на елемент (indexOf, contains): O(n) — трябва да се обходят елементите.

Пример:

ArrayList<Integer> list = new ArrayList<>();
list.add(10); // O(1)
int val = list.get(0); // O(1)
list.add(0, 5); // O(n), преместване на елементите
list.remove(0); // O(n), преместване на елементите