Qual é a complexidade de adicionar um elemento ao ArrayList?

A complexidade de adicionar um elemento ao ArrayList no caso médio é O(1).

Isto é conseguido através do uso de um array dinâmico, e a adição ocorre no final da lista.

// Adicionar ao final da lista
List<String> list = new ArrayList<>();
list.add("elemento"); // O(1) no caso médio

No entanto, se o array interno do ArrayList estiver cheio, é necessária uma operação de aumento de tamanho (resize). Isto envolve criar um novo array maior e copiar todos os elementos existentes para o novo array. A complexidade desta operação é O(n), onde n é o tamanho atual da lista.

// Exemplo onde pode ocorrer resize
List<Integer> numbers = new ArrayList<>(3); // Capacidade inicial de 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Aqui pode ocorrer resize - O(n)

Se o elemento for adicionado não ao final da lista (método add(int index, E element)), mas no meio ou no início, todos os elementos subsequentes precisam ser deslocados uma posição para a direita. A complexidade desta operação é O(n), onde n é a quantidade de elementos que precisam ser deslocados.

// Adicionar ao início da lista
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Adicionar ao início - O(n)

Portanto, a complexidade de adicionar um elemento ao ArrayList depende do local de adição e da necessidade de resize:

Operação de adição	Caso médio	Pior caso (durante resize ou ao não adicionar ao final)
add(E element) (no final)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)