Neste artigo veremos como funciona a classe que modela a principal estrutura de dados da computação: o array. Com uma abordagem voltada para Java, veremos o que acontece por trás do que a classe ArrayList nos fornece.

Frequentemente utilizamos listas em nossos programas, porém talvez não saibamos a facilidade que o computador tem pra armazenar esses dados na memória. Estamos, às vezes, pouco preocupados com o funcionamento interno das classes que utilizamos, e geralmente usamos o import na que oferece uma interface mais simples, ou importamos as que já usamos há mais tempo.

No caso das classes ArrayList e LinkedList, apesar de oferecerem praticamente a mesma interface ao programador, uma vez que ambas implementam a interface List, e terem quase os mesmos métodos, elas têm comportamentos absolutamente diferentes.

Então, quando usar cada uma? A diferença de desempenho é grande? Para quais operações? E o gasto de memória? Como os dados ficarão armazenados? Tendo respondido todas essas perguntas, poderemos analisar quando é melhor utilizar arrays, e quando é preferencial usar listas encadeadas. Neste artigo teremos foco no funcionamento da classe ArrayList.

Array (ou arranjo; ou ainda vetor) é uma estrutura de dados que armazena elementos geralmente de mesmo tamanho e mesmo tipo. Nos arranjos, os elementos ficam agrupados em grandes blocos na memória de forma sequencial, ou seja, o N-ésimo elemento ficará salvo na memória logo após o (N-1)-ésimo. Então, para acharmos qualquer item de um array, basta que saibamos onde está o primeiro.

Por exemplo, se quisermos o terceiro item, a posição da memória dele é igual à posição do primeiro elemento somado com duas posições. Então, dizemos que a operação de acesso em um array tem complexidade constante, isto é, demoramos sempre (ou quase sempre, mas isso é assunto pra outro artigo) o mesmo tempo para acessar tanto o primeiro quanto o último elemento ou qualquer outro elemento, independente do tamanho do vetor.

Veja na figura 1 a organização dos dados em um vetor.

 Organização dos dados de um array na memória

Figura 1: Organização dos dados de um array na memória.

O número de somas necessárias para acharmos um elemento é denominado índice.

Talvez você já tenha se perguntado por que os índices das listas começam em zero, e não em um. Isso acontece porque os índices representam as somas necessárias para se acessar o elemento desejado. No caso do primeiro elemento, não é necessário somar, então, utiliza-se array[0] - ou array.get(0), em ArrayLists de Java.

Agora vamos supor que nosso vetor de 9 posições esteja cheio. Se utilizarmos o método add para inserirmos um novo elemento, o que acontece? É provável que o elemento seja inserido “normalmente”, pelo menos para os olhos do programador. Entretanto, talvez a posição de memória logo adiante não esteja reservada para nosso programa. O que a classe ArrayList faz? Primeiro realoca memória em outro lugar; com mais espaço, obviamente - geralmente o dobro. Depois copia todos os elementos para esse novo local (o que gera um grande overhead pra vetores c) e então adiciona o novo elemento. Esta técnica é conhecida como doubleVector.

No nosso exemplo, teríamos um novo vetor em outro lugar da memória com 18 posições livres para mais inserções. Quando a capacidade fosse esgotada, o vetor dobraria e copiaria os dados mais uma vez.

Então, a fim de evitar esse overhead com o método add da classe ArrayList, fica aqui a minha primeira dica:

Se você já sabe quantos elementos vai adicionar no seu array, use o construtor em que você passa a capacidade inicial por parâmetro. Com isso, ainda acabamos com o desperdício de memória gerado em cada doubleVector. Veja na listagem 1 a utilização desse construtor.

Listagem 1: utilização do construtor ArrayList(int initialCapacity)

public class main {
	public static void main(String[] args) {
		ArrayList meuVetor = new ArrayList(35);
		ArrayList meuVetor2 = new ArrayList(); 
	}
}

Neste caso, o meuVetor é criado com capacidade 35 (trinta e cinco), e o meuVetor2 é criado com capacidade 10 (dez) , padrão da classe.

No caso da inserção de elementos no meio do vetor, contando que ainda há capacidade para armazenamento, há um grande overhead também para copiarmos cada elemento posterior para a direita.

Seja myVector um vetor de capacidade 1.000 que contenha 800 elementos ocupados. O que acontece se quisermos adicionar um elemento no início de myVector, utilizando o método add(int index,E element) ? Este é também um caso crítico dos arrays. O primeiro passo para executar tal operação é arrastar cada elemento uma posição para a direita, liberando o índice desejado para inserção, e só então inserir o elemento.

Com isso, podemos ver que a inserção em posições aleatórias de um vetor não é bom negócio.

E quanto à remoção? É eficiente? Que algoritmo utiliza?

Não, a remoção também não é uma beleza de eficiência, pois sofre do mesmo problema citado um pouco acima na inserção em uma posição arbitrária: o shift de elementos. Contando que tenhamos o mesmo myVector com 800 elementos, uma remoção de um elemento do início do vetor seria algo catastrófico, pois teríamos que deslizar todos os elementos seguintes, dessa vez para a esquerda, para que o array mantenha a consistência. Para a exclusão dos elementos no final do arranjo, o shift de elementos seria um pouco menor. Entretanto, na análise de complexidade de algoritmos, dizemos que a remoção em um array tem complexidade linear, pois a quantidade de operações necessárias é diretamente proporcional ao tamanho da lista, no pior caso (remoção do primeiro elemento).

Para diminuir a complexidade da remoção, podemos propor uma solução diferente, mas esta só funcionará em vetores que a ordem dos elementos não é importante.

Listagem 2: Reimplementação do método remove(int index)

public class noOrderList extends ArrayList {
	public noOrderList() {
		super();
	}
	public noOrderList(int initialCapacity) {
		super(initialCapacity);
	}
	public E remove(int index) {
		E item_para_remover = super.get(index);
		super.set(index, super.get(super.size()-1));
		super.remove(super.size()-1);
		return item_para_remover;
	}
}

O que o método remove mostrado na listagem 2 faz é o seguinte:

  1. Cria uma cópia do item que vamos remover, e salva em item_para_remover.
  2. Em seguida, copia o último elemento para a posição que queríamos remover.
  3. Remove o último elemento.
  4. Retorna o elemento removido.

Resumindo: removemos um elemento na posição N, e colocamos o último elemento da lista em seu lugar. Então, fica claro que esta solução só funciona para vetores em que a ordem dos elementos pode ser levemente alterada. Nesse caso temos que a complexidade dessa remoção é constante, uma vez que temos um número fixo de operações, independente do tamanho do vetor.

Então, concluímos aqui nosso artigo sobre o que acontece por dentro de arraylists, nas operações de inserção e remoção. Após toda essa análise, espero que esteja claro para vocês que arrayslists não foram pensados para inserção e remoção de elementos em posições aleatórias, mas sim para o acesso imediato a qualquer posição dele, além do rápido acesso sequencial do vetor inteiro, facilitado pelas estratégias de utilização eficiente da memória cache dos processadores, das quais pretendo falar em outro artigo.

Bem, galera, espero que tenham entendido a mensagem, e até o próximo!