Qual è la complessità di aggiungere un elemento a ArrayList?

La complessità di aggiunta di un elemento a ArrayList nel caso medio è O(1).

Ciò si ottiene utilizzando un array dinamico, e l'aggiunta avviene alla fine della lista.

// Aggiunta alla fine della lista
List<String> list = new ArrayList<>();
list.add("elemento"); // O(1) nel caso medio

Tuttavia, se l'array interno di ArrayList è pieno, è necessaria un'operazione di resize. Questo comporta la creazione di un nuovo array più grande e la copia di tutti gli elementi esistenti nel nuovo array. La complessità di questa operazione è O(n), dove n è la dimensione attuale della lista.

// Esempio in cui può verificarsi resize
List<Integer> numbers = new ArrayList<>(3); // Capacità iniziale di 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Qui può verificarsi resize - O(n)

Se l'elemento viene aggiunto non alla fine della lista (metodo add(int index, E element)), ma nel mezzo o all'inizio, tutti gli elementi successivi devono essere spostati di una posizione verso destra. La complessità di questa operazione è O(n), dove n è il numero di elementi da spostare.

// Aggiunta all'inizio della lista
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Aggiunta all'inizio - O(n)

Pertanto, la complessità di aggiunta di un elemento a ArrayList dipende dal luogo di aggiunta e dalla necessità di resize:

Operazione di aggiunta	Caso medio	Caso peggiore (durante resize o non alla fine)
add(E element) (alla fine)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)