A hierarquia das coleções no Java

O ArrayList é uma implementação concreta da interface List, pertencente ao pacote java.util. A interface List faz parte do Java Collections Framework e herda de Collection, que por sua vez herda de Iterable. A partir do Java 21, List também estende SequencedCollection.

Propriedades e custos

Como implementação da interface List, o ArrayList possui características que o diferenciam de um array convencional. Essas características influenciam diretamente o desempenho das operações realizadas sobre a estrutura.

• Inserção no final: O(1) amortizado
• Inserção em qualquer outra posição: O(n)
• Remoção no final: O(1)
• Remoção em posições intermediárias: O(n)
• Redimensionamento dinâmico da capacidade do array

Além de disponibilizar diversos métodos para manipulação de listas, o ArrayList gerencia automaticamente sua capacidade de armazenamento por meio de uma estratégia de redimensionamento dinâmico. Esse mecanismo elimina a necessidade de o desenvolvedor criar manualmente um novo array sempre que a capacidade da estrutura é atingida, assunto que veremos no próximo tópico..

Declarando um ArrayList

Podemos criar uma instância de um ArrayList utilizando o construtor padrão:

List<Tipo> nomeVar = new ArrayList<>();

O ArrayList utiliza Generics, permitindo armazenar qualquer tipo por referência (reference type). Isso inclui classes como String, wrappers (Integer, Double, Boolean), objetos personalizáveis e até mesmo outras coleções.

List<Tipo> nomeVar = new ArrayList<>(20);

Esse construtor é útil quando já conhecemos aproximadamente a quantidade de elementos que serão armazenados, reduzindo a necessidade de redimensionamentos durante a execução. Caso essa capacidade seja totalmente utilizada, o ArrayList executará sua rotina de redimensionamento, criando um novo array interno com maior capacidade para continuar armazenando novos elementos.

O Redimensionamento Dinâmico

A principal diferença entre um array convencional e um ArrayList está na forma como cada um lida com sua capacidade de armazenamento.Enquanto um array possui tamanho fixo após sua criação, o ArrayList utiliza uma estratégia de redimensionamento dinâmico, permitindo que novos elementos sejam adicionados sem que o desenvolvedor precise gerenciar manualmente a criação de um novo array.

Quando a capacidade atual é atingida, o ArrayList cria um novo array interno com uma capacidade maior. Na implementação atual do OpenJDK, esse crescimento ocorre, em geral, aumentando aproximadamente 50% da capacidade anterior. Seguindo a seguinte fórmula:

É importante destacar que o array interno não cresce de tamanho. Como arrays possuem tamanho fixo, isso simplesmente não é possível. Quando a capacidade disponível é esgotada, o ArrayList cria um novo array com maior capacidade, copia todos os elementos do array antigo para esse novo espaço e passa a utilizá-lo como armazenamento interno.

Por que tempo O(1) amortizado?

Uma das principais características do ArrayList é que a inserção de elementos ao final da lista possui complexidade O(1) amortizada. Mas o que isso significa? O termo amortizado indica que estamos analisando o custo médio de uma sequência de operações, e não apenas o custo de uma única inserção. Na maioria das vezes, adicionar um novo elemento ao final da lista consiste apenas em armazená-lo na próxima posição disponível do array interno, uma operação de custo constante, ou seja, O(1).

Entretanto, quando toda a capacidade do array interno é utilizada, o ArrayList precisa executar sua rotina de redimensionamento. Nesse momento, um novo array com maior capacidade é criado, todos os elementos do array antigo são copiados para ele e, somente então, o novo elemento é inserido. Como essa operação exige percorrer todos os elementos existentes, seu custo é O(n). Apesar disso, esse redimensionamento ocorre apenas ocasionalmente.

Após a criação do novo array, diversas inserções podem ser realizadas sem que uma nova cópia de elementos seja necessária. Em outras palavras, o custo de uma operação mais cara é distribuído entre várias operações muito mais baratas. Por esse motivo, embora algumas inserções apresentem custo O(n), o custo médio de uma sequência de inserções permanece constante. É justamente essa análise que chamamos de complexidade amortizada, resultando em uma inserção ao final da lista com tempo O(1) amortizado.

Conclusão

O ArrayList encapsula a complexidade de gerenciar a memória manualmente, unindo a velocidade de leitura de um array convencional com a flexibilidade de uma estrutura dinâmica. O custo do redimensionamento e da cópia de elementos - que ocorre por baixo dos panos - é diluído ao longo do tempo, resultando em uma performance de O(1) amortizada para inserções ao final da lista.