Java ArrayList

ArrayList<E> é a implementação de List mais utilizada. Internamente é um array Java simples (Object[]) com um contador de comprimento e alguma lógica de crescimento por cima. Isso lhe confere o perfil de desempenho que a maioria do código precisa: acesso aleatório O(1), inserção amortizada O(1) no final, e apenas pausas ocasionais quando o array subjacente precisa crescer. Quando alguém diz "use uma lista" sem especificar qual, quase sempre significa ArrayList. Este capítulo explica o porquê, quais são as trocas e os poucos métodos exclusivos da classe.

O que há dentro

Um ArrayList mantém três partes de estado:

• Object[] elementData — o array subjacente. Maior que size com alguma folga.
• int size — quantos desses slots estão em uso.
• int modCount — um contador que invalida iteradores se você modificar durante a iteração.

O Javadoc é preciso sobre a complexidade: size, isEmpty, get, set, iterator, listIterator e add (no final) são executados em tempo constante. Inserir/remover em qualquer outro lugar é linear porque a cauda do array precisa deslizar. Voltaremos a isso.

Criando um

List<String> a = new ArrayList<>();             // default capacity (10)
List<String> b = new ArrayList<>(1_000_000);    // pre-size — avoids re-grows
List<String> c = new ArrayList<>(otherList);    // copy of any Collection
List<String> d = new ArrayList<>(List.of("a", "b", "c"));   // from a small literal

Se você sabe aproximadamente quantos elementos vai adicionar, passe a capacidade para o construtor. A capacidade padrão é 10 e toda vez que o array fica cheio ele cresce cerca de 50% — o que significa muitas alocações e cópias se você anexar milhões de itens a partir do padrão. Solução de uma linha:

List<Row> rows = new ArrayList<>(expectedSize);

Para "a partir deste conjunto fixo," prefira a fábrica List.of(...) (abordada posteriormente neste capítulo) — ela é menor e imutável.

Adicionar e remover — o custo depende de onde

Cada List.add(E), add(int, E), remove(int) e remove(Object) é O(n) no pior caso se tocar o meio do array. O motivo é mecânico: um array é memória contígua, portanto inserir no início significa que cada elemento existente precisa se mover um slot para a direita. O custo amortizado de inserir no final é O(1) (sem deslocamento), mas qualquer outra posição é linear no número de elementos após o ponto de inserção.

Na prática isso significa:

• Construir uma lista por list.add(x) repetido → rápido, independentemente do tamanho. Inserção no final é para o que ArrayList serve.
• Chamar list.add(0, x) em um loop → quadrático. Não faça.
• Chamar list.remove(0) repetidamente para esvaziar → quadrático. Use um Deque ou itere em sentido inverso.

Se você se encontrar constantemente inserindo ou removendo no início, ArrayDeque é a ferramenta certa.

Capacidade vs. tamanho

Esses são dois números diferentes:

• size() é a contagem pública, em nível de contrato, de elementos.
• A capacidade — o comprimento do array subjacente — é interna e maior que size.

Quando a folga acaba, ArrayList aloca um novo array aproximadamente 1,5× o comprimento antigo e copia. Esse é o "crescimento" sobre o qual o Javadoc avisa. Dois controles disponíveis:

• ensureCapacity(int) — aumentar o array subjacente para pelo menos esse comprimento antes de uma rajada conhecida de chamadas add.
• trimToSize() — encolher o array subjacente para exatamente size. Útil quando você sabe que a lista não vai crescer mais (por exemplo, antes de armazená-la em cache por muito tempo).

Nenhum dos dois é algo que você vai usar com frequência, mas vale a pena saber que existem quando você está ajustando um caminho crítico.

ArrayList não é thread-safe

Duas threads modificando o mesmo ArrayList eventualmente irão corrompê-lo. Não há sincronização, nenhuma operação atômica, nada. Se você precisar de acesso simultâneo, suas opções são:

• Collections.synchronizedList(new ArrayList<>()) — envolve cada método mutador em um bloqueio. Iteradores ainda não são seguros — você precisa sincronizar externamente durante a iteração. Adequado para casos de baixa contenção.
• CopyOnWriteArrayList — cada mutação aloca uma nova cópia do array subjacente. A iteração é sem bloqueio e vê um snapshot congelado. Excelente para "muitos leitores, escritor ocasional" (ouvintes de eventos, caches de configuração). Péssimo para cargas de trabalho com muita escrita.
• Vector — também sincronizado, mas um design de 1995 com as mesmas fraquezas que synchronizedList. Não escolha para código novo.

Threads é um tópico profundo por si só; por enquanto, a regra é: um ArrayList compartilhado entre threads precisa de um wrapper ou de uma classe diferente.

Iteração e ConcurrentModificationException

Adicionar ou remover de um ArrayList enquanto itera sobre ele por meio do loop for-each quase sempre lança ConcurrentModificationException:

List<Integer> xs = new ArrayList<>(List.of(1, 2, 3, 4));
for (int x : xs) {
  if (x % 2 == 0) xs.remove(Integer.valueOf(x));   // throws
}

A verificação fail-fast compara o snapshot de modCount do iterador com o modCount atual da lista. As duas formas de modificar com segurança:

xs.removeIf(x -> x % 2 == 0);              // 1. predicate form — cleanest

Iterator<Integer> it = xs.iterator();
while (it.hasNext())                        // 2. explicit Iterator.remove()
  if (it.next() % 2 == 0) it.remove();

removeIf é o padrão moderno. Recorra ao iterador explícito apenas quando a condição depender de estado que você não quer calcular duas vezes.

Métodos úteis que você não viu em List

ArrayList adiciona alguns métodos que a interface List não possui:

• void trimToSize() — encolher para caber.
• void ensureCapacity(int) — pré-crescer.
• Object clone() — cópia superficial. Equivalente a new ArrayList<>(this) e quase nunca usado.

É isso. Quase tudo que você chamará em um ArrayList vem da interface List.

Um exemplo prático: ArrayList em ação

O programa abaixo constrói um ArrayList, exercita suas operações baseadas em índice, esvazia-o e termina com a diferença de tempo entre pré-crescimento de capacidade vs. crescimento padrão, para que você possa ver o custo de esquecer o pré-dimensionamento.

A ordem das operações para ler na saída:

• fruits.add(1, "avocado") deslocou cada elemento posterior um slot para a direita. Para quatro elementos isso é invisível; para um milhão dominaria o tempo de execução.
• removeIf e subList são as duas peças de maquinaria que tornam a maior parte do código real com ArrayList limpo — remoção em massa baseada em predicado e operações de janela ao vivo.
• O bloco de tempo é ilustrativo, não de nível de benchmark — em uma única execução de aquecimento JIT os números podem até sair ao contrário. O ponto que ele faz é estrutural: a inserção de capacidade padrão faz o array subjacente crescer cerca de 30 vezes até o milionésimo elemento, e o pré-dimensionamento elimina cada uma dessas cópias. Para um caminho crítico em estado estacionário, a versão pré-dimensionada vence; meça com um harness adequado se isso for importante.

O que vem a seguir

ArrayList é a resposta certa quase sempre. O caso interessante é quando não é — inserção e remoção pesadas na frente ou no meio de uma lista longa. Esse é o nicho de LinkedList: mesma interface List, armazenamento completamente diferente. Mesmo problema, duas respostas — e vamos medir quando cada uma vence.

Prática