A estrutura de um ArrayList - uma explicação a partir de uma perspectiva técnica

Bom, quero trazer para vocês como funciona, por baixo dos panos, o redimensionamento de uma ArrayList.

Na programação, uma ArrayList, ou simplesmente Lista, se trata de uma estrutura dinâmica que pode ser redimensionada, podendo aumentar ou diminuir sua capacidade de armazenamento.

Dentro da linguagem Java, quando declaramos uma ArrayList :

ArrayList<String> lista = new ArrayList<>();

Internamente, na memória, vai ser instanciado um objeto de capacidade x (inicialmente 0) e de tamanho y (inicialmente 0). Para exemplificar isso, vamos abaixar um pouco o nível e trabalhar diretamente com um Array.

Um array se trata de uma estrutura de dados homogênea e de tamanho fixo, ou seja, ela armazena elementos de um mesmo tipo e possui um limite de armazenamento.

Em todas as linguagens que trabalham com Arrays, ocorre o seguinte processo ao se declarar um array, uma variável é instanciada na memória stack e o seu valor será o endereço de memória de um objeto do tipo Array dentro da memória heap:

Certo, isso eu entendi, mas como isso me mostra o funcionamento de um ArrayList?

Por baixo dos panos, uma ArrayList se trata de uma gama de operações envolvendo um array, então vamos dar um zoom dentro desse Array.

Para manipularmos um Array de forma que ele seja uma estrutura dinâmica, precisamos manipular especificamente dois elementos:

• Capacidade
• Tamanho

A capacidade de um Array representa a quantidade de elementos que podem ser armazenados dentro do Array. Se declararmos um Array de Strings passando em seu argumento o valor 5, será instanciado na memória do computador um objeto Array de capacidade 5, sem elementos armazenados em seus índices.

String[] lista = new String[5];

O tamanho de um Array representa o número real de índices preenchidos com algum elemento do tipo T neste nosso exemplo. Se colocarmos lista[0] = "s", o tamanho do Array será 1.

Então, vamos implementar uma classe chamada CustomArray para podermos manipular um array de forma lúdica, a fim de esclarecer como funciona uma ArrayList.

UML CustomArray

Vamos ver a implementacao do metodo construtor da classe CustomArray():

public CustomArray(int capacity) {
  if (capacity < 0) {
      throw new IllegalArgumentException("O tamanho deve ser um numero positivo ou zero");
  }
  this.elements = new String[capacity];
}

Ao instanciarmos, por exemplo, um CustomArrayxpto de tamanho 5, a sua capacidade de armazenamento será 5, porém o seu tamanho real (size) será 0.

CustomArray xpto = new CustomArray(5);

Ao executarmos o método addElement para adicionar um elemento x aos elementos do CustomArray, o elemento será inserido no índice para o qual o ponteiro está apontando, curiosamente sendo o próprio size.

public void addElement(String element) {
  if (size == this.elements.length) {
      grow();
  }

  this.elements[size] = element;
  size++;
}

Então, sempre que adicionamos um elemento ao Array, o ponteiro vai para a próxima posição (próximo índice), pois o size está sendo incrementado em 1.

xpto.addElement("a");

Se executarmos novamente o método, o elemento não será adicionado ao primeiro índice dos elementos, mas sim à última posição apontada pelo ponteiro.

Show, compreendi como um ponteiro funciona dentro do Array, mas sua capacidade ainda está fixa; isso não parece um ArrayList.

É neste ponto que entra a “mágica” do redimensionamento e do deslocamento de bits.

Um array dinâmico deve aumentar sua capacidade quando o ponteiro chega ao limite do array, ou seja, quando size == elements.length.

Se o size (quantidade real de itens armazenados em um array) for igual ao length do array (capacidade total do array), devemos copiar o array existente para um novo array com uma capacidade maior.

Ao executarmos o método addElement, e o nosso size (ponteiro) equivale à capacidade máxima do array (length), o método grow() é executado.

private void grow() {
  String[] tempArr = new String[this.elements.length + (this.elements.length >> 2) + 1];
  System.arraycopy(this.elements, 0, tempArr, 0, this.elements.length);
  this.elements = tempArr;
}

Logicamente, nós pensamos: “poxa, vou dobrar a capacidade do meu array original”. Isso está correto, mas custa memória. Em um array de capacidade 5 o computador não sente a diferença, mas agora vamos escalar isso para 1 bilhão: dobrar a capacidade ficaria custoso.

O Java é inteligente o suficiente para fazer isso de forma eficiente, utilizando o deslocamento de bits.

Então, a implementação acima exemplifica como isso funciona. O novo array tempArray vai possuir a capacidade original + o deslocamento de dois dígitos binários para a direita (quase como um “dividir por 2”, digamos) + 1, ou seja:

5 + (0101 (5 em binário) >> 2 — isso em binário se torna 0001, ou 1 em decimal) + 1 =

5 + 1 + 1 = 7

Logo, a capacidade do tempArray será 7.

Após o aumento da capacidade, copiamos todos os elementos do array original para o novo.

 System.arraycopy(this.elements, 0, tempArr, 0, this.elements.length);

e atribuimos o novo Array ao array original elements. e a operacao addElement prossegue normalmente sem existir um estouro de limite do array.