Care este complexitatea adăugării unui element în ArrayList?

Complexitatea adăugării unui element în ArrayList în cazul mediu este O(1).

Aceasta se realizează prin utilizarea unui array dinamic, iar adăugarea se face la sfârșitul listei.

// Adăugare la sfârșitul listei
List<String> list = new ArrayList<>();
list.add("element"); // O(1) în cazul mediu

Totuși, dacă array-ul intern al ArrayList este plin, este necesară o operație de resize. Aceasta implică crearea unui nou array mai mare și copierea tuturor elementelor existente în noul array. Complexitatea acestei operații este O(n), unde n este dimensiunea curentă a listei.

// Exemplu în care poate avea loc resize
List<Integer> numbers = new ArrayList<>(3); // Capacitate inițială 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Aici poate avea loc resize - O(n)

Dacă elementul este adăugat nu la sfârșitul listei (metoda add(int index, E element)), ci în mijloc sau la început, toate elementele următoare trebuie mutate cu o poziție spre dreapta. Complexitatea acestei operații este O(n), unde n este numărul de elemente care trebuie mutate.

// Adăugare la începutul listei
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Adăugare la început - O(n)

Astfel, complexitatea adăugării unui element în ArrayList depinde de locul de adăugare și de necesitatea resize-ului:

Operație de adăugare	Caz mediu	Caz cel mai rău (în timpul resize-ului sau dacă nu se adaugă la sfârșit)
add(E element) (la sfârșit)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)