Introdução

Nas publicações anteriores vimos como os arrays funcionam, e porque eles oferecem acesso extremamente rápido aos seus elementos. Entretanto, possuem uma limitação, seu tamanho fixo. Também comentamos como o ArrayList por outro lado consegue crescer dinamicamente, conforme novos elementos são adicionados.

Sendo assim, por que não implementarmos nossa própria estrutura baseada em um ArrayList? Sendo essa uma das formas mais interessantes de se aprender vendo como de fato funciona o resize, a adição, remoção de elementos, além de alguns outros métodos úteis.

Criando a interface IndexList

Antes de partirmos para a construção da classe de fato, criaremos uma interface chamada IndexList, que servirá de contrato para a nossa classe Array. A interface contará com os seguintes métodos:

public interface IndexList<E> {
    public int size();

    public boolean isEmpty();

    public void add(int index, E element) throws IndexOutOfBoundsException;

    public E get(int index);

    public E remove(int index) throws IndexOutOfBoundsException;

    public E set(int index, E element);
}

A criação desta interface nos ajuda a manter o baixo acoplamento, permitindo isolar o que a estrutura opera de como a nossa classe Array implementa esses métodos. Imagine que, daqui a algum tempo, desejemos implementar uma Linked List? Poderemos reaproveitar essa mesma interface, preocupando-nos apenas em criar a lógica específica para a nova estrutura de nós.

Primeiro problema: Onde armazenar os elementos?

Antes mesmo de decidir como adicionar ou remover elementos, precisamos decidir como os mesmos serão armazenados. Como abordado no post sobre arrays, a estrutura oferece acesso direto aos elementos através do índice, além de armazená-la de forma contígua na memória. Portanto, faz sentido utilizá-la como base da nossa implementação.

public class Array<E> implements IndexList<E> {
    private E[] array;
    private int capacity = 16;
    private int size;
}

Neste ponto, surgem duas perguntas importantes:

• Por que utilizar um array de objetos?
• Por que armazenamos separadamente a quantidade e a capacidade?

Por que utilizar um array de objetos?

A resposta está no funcionamento dos Generics em Java. Durante a compilação, ocorre um processo chamado Type Erasure, no qual as informações sobre o tipo genérico (E) são removidas. Em tempo de execução, a JVM não conhece mais qual é o tipo representado por E, tornando impossível instanciar diretamente um array genérico.

Por esse motivo, criamos um Object[] e realizamos um cast para E[] em nosso construtor:

public class Array<E> implements IndexList<E> {
    private E[] array;
    private int capacity = 16;
    private int size;

    public Array() {
        array = (E[]) new Object[capacity];
    }
}

Embora esse cast gere um aviso do compilador (unchecked cast), ele é seguro nesse contexto, já que todos os elementos inseridos na estrutura serão do tipo definido pelo parâmetro genérico.

Por que armazenamos separadamente a quantidade e a capacidade?

A estrutura mantém duas informações distintas: a capacidade (capacity) e a quantidade de elementos armazenados (size). Embora pareçam representar a mesma coisa, elas possuem papéis diferentes.

• capacity representa o tamanho do array interno, ou seja, quantas posições estão disponíveis para armazenamento.
• size representa quantos elementos foram efetivamente inseridos na estrutura.

Manter essas informações separadas simplifica a implementação de diversos métodos. Por exemplo, antes de inserir um novo elemento, basta verificar se size == capacity para saber se será necessário executar a rotina de redimensionamento.

Além disso, operações como size(), isEmpty() e as validações de índice podem ser realizadas em tempo constante (O(1)), sem a necessidade de percorrer o array.

A inserção de elementos

O ato de inserir os elementos é bastante interessante: ele recebe como argumentos o índice alvo e o elemento a ser inserido.

@Override
    public void add(int index, E element) throws IndexOutOfBoundsException {
        checkIndex(index, size() + 1);

        if (this.size == capacity) {
            capacity = capacity + (capacity >> 1);
            E[] newArray = (E[]) new Object[capacity];
            for (int i = 0; i < this.size; i++) {
                newArray[i] = this.array[i];
            }
            this.array = newArray;
        }

        for (int i = this.size - 1; i >= index; i--) {
            this.array[i + 1] = this.array[i];
        }

        this.array[index] = element;
        this.size++;
    }

O primeiro passo é verificar se o índice passado é válido, ou seja, se ele não ultrapassa o tamanho atual da estrutura e se não é menor do que zero. Como essa verificação é útil em todo o escopo da classe, delegamos a validação para um método estático privado chamado checkIndex.

    private void checkIndex(int index, int limit) {
        if (index < 0 || index >= limit) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: "+ size());
        }
    }

Após a validação, entramos na lógica de redimensionamento, que é o coração de tudo que discutimos sobre arrays dinâmicos no post anterior sobre a coleção ArrayList.

Verificamos se size se igualou à capacity. Caso verdadeiro, significa que nosso array atingiu a sua capacidade máxima e precisa crescer.

Para tal, atualizamos a capacidade aumentando em 50%. Fazemos isso somando a capacidade atual ao resultado do bit shift de divisão (capacity >> 1). Inicializamos um newArray com essa nova métrica, iteramos sobre o array atual copiando os elementos e, por fim, atualizamos a referência this.array

    if (this.size == capacity) {

        capacity = capacity + (capacity >> 1);
        E[] newArray = (E[]) new Object[capacity];

        for (int i = 0; i < this.size; i++) {
            newArray[i] = this.array[i];
        }

        this.array = newArray;
    }

Com o espaço garantido, passamos para a adição de fato. Caso o usuário deseje inserir o elemento em uma posição já ocupada, utilizaremos um laço para deslocar todos os elementos posteriores uma posição para a direita

   for (int i = this.size - 1; i >= index; i--) {
        this.array[i + 1] = this.array[i];
    }

    this.array[index] = element;
    this.size++;

Como precisamos manipular a lista e deslocar as posições, a complexidade de tempo se torna $O(n)$ no pior caso (inserção no início ou no meio do array). No melhor caso (inserção livre ao final), a complexidade é $O(1)$.

A remoção de elementos

Inserir elementos exige alguns cuidados, mas removê-los também apresenta um desafio importante. Diferentemente de estruturas como listas encadeadas, os elementos de um array ocupam posições contíguas na memória. Isso significa que, ao remover um elemento, não basta simplesmente atribuir null à posição correspondente. Se fizéssemos isso, criaríamos um “buraco” na estrutura, quebrando a sequência lógica dos elementos.

Imagine o seguinte cenário:

Após remover C, o resultado esperado não é este:

Mas sim:

Para que isso aconteça, nossa implementação precisa resolver alguns problemas.

@Override
    public E remove(int index) throws IndexOutOfBoundsException {
        checkIndex(index, size());

        E temp = this.array[index];

        for (int i = index; i < this.size - 1; i++) {
            this.array[i] = this.array[i + 1];
        }

        this.array[this.size - 1] = null;
        this.size--;
        return temp;
    }

Assim como no método add(), a primeira preocupação é garantir que o índice informado seja válido usamos nossa validação de limites para garantir uma operação segura. Em seguida, guardamos o elemento a ser removido em uma variável temporária: temp

    checkIndex(index, size());
    E temp = this.array[index];

Agora chegamos ao ponto mais importante da remoção. Depois que um elemento deixa de existir, todos os elementos posicionados à sua direita precisam ser deslocados uma posição para a esquerda.

    for (int i = index; i < this.size - 1; i++) {
        this.array[i] = this.array[i + 1];
    }

O laço percorre a estrutura a partir do índice removido até o penúltimo elemento válido, copiando sempre o elemento da posição seguinte para a posição atual. Visualmente, o processo acontece da seguinte forma:

Esse deslocamento garante que os elementos permaneçam armazenados de forma contígua, preservando a principal característica dos arrays. Como, no pior caso, praticamente todos os elementos precisam ser movimentados, essa operação possui complexidade $O(n)$. Vale observar que, quando o elemento removido já está na última posição, nenhum deslocamento é necessário. Nesse cenário, a remoção ocorre em tempo $O(1)$.

Depois do deslocamento, a última posição do array ainda contém uma referência para o objeto que foi copiado durante a reorganização.

        this.array[this.size - 1] = null;
        this.size--;
        return temp;

Essa referência já não faz parte da estrutura e precisa ser removida. Ao atribuir null à última posição, permitimos que o Garbage Collector recupere essa memória futuramente, caso não existam outras referências para o objeto.

O método GET

O método get() recebe um índice e devolve o elemento armazenado naquela posição.

@Override
    public E get(int index) {
        checkIndex(index, size());

        return this.array[index];
    }

Antes de realizar o acesso, validamos o índice para garantir que ele pertence aos limites da estrutura.

   checkIndex(index, size());

Uma vez validado, basta acessar diretamente a posição correspondente do array interno.

    this.array[index];

Essa é justamente uma das maiores vantagens dos arrays. Como seus elementos são armazenados em posições contíguas de memória, a JVM consegue calcular diretamente o endereço do elemento desejado a partir do índice informado, sem a necessidade de percorrer a estrutura. Por esse motivo, o método get() possui complexidade $O(1)$, independentemente da quantidade de elementos armazenados.

Atualizando um elemento com o metodo SET

O método set() segue praticamente a mesma ideia. Em vez de inserir um novo elemento na estrutura, ele apenas substitui o valor armazenado em uma posição já existente.

@Override
    public E set(int index, E element) {
        checkIndex(index, size());

        E temp = this.array[index];
        this.array[index] = element;

        return temp;
    }

A primeira etapa consiste em validar o índice informado.

    checkIndex(index, size());

Depois disso, armazenamos temporariamente o elemento atual, realizamos a substituição e retornamos o valor antigo ao final do método.

    E temp = this.array[index];
    this.array[index] = element;

    return temp;

A atualização ocorre por meio de um acesso direto ao índice desejado, sem deslocamentos ou realocações de memória. Por esse motivo, sua complexidade também permanece $O(1)$.

Consultando informações da estrutura

Além das operações de inserção, remoção e acesso aos elementos, uma estrutura de dados também precisa fornecer algumas informações sobre seu estado atual.

Na nossa implementação, isso é feito através dos métodos isEmpty() e size(). Como ambos apenas consultam o valor da variável size, nenhuma modificação é realizada no array interno.

Isso significa que as duas operações possuem complexidade $O(1)$, independentemente da quantidade de elementos armazenados. O método isEmpty() verifica se a estrutura está vazia.

@Override
    public boolean isEmpty() {
        return this.size == 0;
    }

Sua implementação é bastante simples: basta comparar se a variável size é igual a zero. Caso seja, significa que nenhum elemento foi inserido na estrutura até aquele momento.

Já o método size() retorna a quantidade de elementos atualmente armazenados.

@Override
    public int size() {
        return this.size;
    }

Observe que, em nenhum momento, precisamos percorrer o array para descobrir esse valor. Como o atributo size é atualizado a cada inserção ou remoção, a quantidade de elementos está sempre disponível.

Dessa forma, obter o tamanho da estrutura consiste apenas em retornar o valor dessa variável, mantendo a operação em tempo constante $O(1)$.

Conclusão

Implementar uma estrutura de dados é uma experiência completamente diferente de apenas utilizá-la. Ao construir um Array do zero, conceitos como redimensionamento, deslocamento de elementos e análise de complexidade deixam de ser apenas teoria.

Embora a implementação apresentada seja simplificada quando comparada às coleções da biblioteca padrão do Java, ela reproduz os principais mecanismos utilizados por estruturas como o ArrayList e serve como uma excelente base para compreender o que acontece por debaixo dos panos.

O código implementado nesta publicação está disponivel no seguinte repositório: https://github.com/ThalesSilva67/data-structure

Referências

• GOODRICH, Michael T.; TAMASSIA, Roberto. Estruturas de Dados e Algoritmos em Java. 5. ed. Porto Alegre: Bookman, 2013.