Dynamic Array — The Data Structures Atlas

Categoria: Linear

O problema

Um array comum em Java tem tamanho fixo desde a criação. A maioria dos casos de uso reais não sabe o tamanho final de antemão — os registros chegam um a um, vindos de um arquivo, uma fila, uma requisição. Alocar capacidade "suficiente" significa ou estimar demais (memória desperdiçada) ou de menos (um overflow que você precisa tratar na mão: alocar um array maior, copiar cada elemento para ele, e continuar).

A solução

Envolva um array bruto e faça-o crescer automaticamente: quando um add ultrapassaria a capacidade do array subjacente, aloque um novo array com o dobro da capacidade, copie tudo para ele, e continue adicionando. Um único redimensionamento é O(n), mas ele acontece exponencialmente com menos frequência à medida que o array cresce, então o custo médio por add ao longo de muitos appends — o custo amortizado — permanece O(1). O encolhimento espelha essa lógica: quando a ocupação cai para um quarto da capacidade, ela é reduzida à metade, para que uma carga de trabalho de preencher-depois-esvaziar não fique oscilando, redimensionando a cada remoção perto de um desses limites.

flowchart LR
    A["size == capacity"] -->|add| B["allocate 2x array"]
    B --> C["copy n elements"]
    C --> D["append succeeds"]
    E["size == capacity/4"] -->|remove| F["allocate capacity/2 array"]
    F --> G["copy n elements"]
    G --> H["remove succeeds"]

Operação	Custo	Por quê
`get(index)` / `set(index, v)`	O(1)	offset direto no array
`add(v)` (append)	O(1) amortizado	dobrar a capacidade mantém a frequência de redimensionamento exponencialmente pequena
`remove(index)`	O(n)	desloca cada elemento após `index` uma posição para a esquerda
iteração	O(n)	varredura contígua, amigável ao cache

Exemplo clássico

classic/DynamicArray é construído sobre um Object[] bruto, não sobre java.util.ArrayList — add, get, set, remove e Iterable<T> são todos implementados à mão, incluindo a política de crescimento por duplicação e encolhimento por quarto. DynamicArrayTest cobre o crescimento além da capacidade inicial, o encolhimento após esvaziamento, acesso fora dos limites, e o esgotamento do iterador.

Exemplo aplicado: buffer de registros em lote

applied/BatchRecordBuffer armazena temporariamente linhas de PolicyBatchRecord conforme elas chegam de uma extração em lote de prêmios de seguro, e depois as distribui para workers paralelos em blocos de tamanho fixo via drainInChunksOf. É exatamente o formato que um pipeline de lote de grande porte (3M+ linhas/dia numa grande seguradora) enfrenta: a ingestão é puro append, e o esvaziamento é uma única varredura em massa — o layout contíguo de um array dinâmico atende melhor a ambos do que uma linked list atenderia. BatchRecordBufferTest cobre limites de blocos pares/ímpares e o caso de buffer vazio.

Benchmark

./gradlew :linear:dynamic-array:jmh

Execução real nesta máquina (JMH 1.37, JDK 26.0.2, 2 iterações de warmup + 3 de medição, 1 fork):

Benchmark	size=100	size=10,000	size=1,000,000
`append` (total para N appends)	611 ns	75,047 ns	75.6 ms
`get` (leitura indexada única)	2.50 ns	2.44 ns	2.46 ns

get se mantém estável em ~2.4–2.5 ns independentemente do tamanho — a afirmação de O(1), falseável e confirmada. O custo total de append escala de forma aproximadamente linear com o tamanho (≈6–7.5 ns/elemento em 100 e 10,000), que é o que "O(1) amortizado por elemento" parece quando visto em conjunto; a linha de 1,000,000 teve uma iteração que coincidiu com um redimensionamento grande e distorceu a média para cima, o que é o resultado honesto e não suavizado de um redimensionamento de array por duplicação de fato acontecendo no meio do benchmark, não um erro de medição.

Quando não usar

Inserção/remoção frequente no início ou no meio: toda operação desse tipo é O(n) aqui. Uma linked list duplamente encadeada (ou um buffer circular estilo ArrayDeque para o caso de só mexer no início) é a escolha melhor.
Se o tamanho máximo é conhecido exatamente de antemão e nunca muda, um array fixo comum evita por completo o mecanismo de redimensionamento.
Precisa de consultas por intervalo ou buscas ordenadas de floor/ceiling por chave? Veja o módulo Binary Search Tree deste repositório.

Cobertura de testes

100% de cobertura de instruções, 100% de cobertura de branches (JaCoCo). Reproduza você mesmo:

./gradlew :linear:dynamic-array:jacocoTestReport

Relatório em linear/dynamic-array/build/reports/jacoco/test/html/index.html.

Testes unitários

src/test/java/com/datastructures/linear/dynamicarray/classic/DynamicArrayTest.java

package com.datastructures.linear.dynamicarray.classic;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class DynamicArrayTest {

    @Test
    void startsEmpty() {
        DynamicArray<String> array = new DynamicArray<>();

        assertThat(array.isEmpty()).isTrue();
        assertThat(array.size()).isZero();
    }

    @Test
    void addAppendsAndGetReadsBackInOrder() {
        DynamicArray<String> array = new DynamicArray<>();

        array.add("a");
        array.add("b");
        array.add("c");

        assertThat(array.size()).isEqualTo(3);
        assertThat(array.get(0)).isEqualTo("a");
        assertThat(array.get(1)).isEqualTo("b");
        assertThat(array.get(2)).isEqualTo("c");
    }

    @Test
    void growsPastInitialCapacityWithoutLosingElements() {
        DynamicArray<Integer> array = new DynamicArray<>(2);

        for (int i = 0; i < 100; i++) {
            array.add(i);
        }

        assertThat(array.size()).isEqualTo(100);
        assertThat(array.capacity()).isGreaterThan(2);
        for (int i = 0; i < 100; i++) {
            assertThat(array.get(i)).isEqualTo(i);
        }
    }

    @Test
    void setReplacesElementAndReturnsThePreviousOne() {
        DynamicArray<String> array = new DynamicArray<>();
        array.add("original");

        String previous = array.set(0, "replaced");

        assertThat(previous).isEqualTo("original");
        assertThat(array.get(0)).isEqualTo("replaced");
    }

    @Test
    void removeShiftsSubsequentElementsLeft() {
        DynamicArray<String> array = new DynamicArray<>();
        array.add("a");
        array.add("b");
        array.add("c");

        String removed = array.remove(0);

        assertThat(removed).isEqualTo("a");
        assertThat(array.size()).isEqualTo(2);
        assertThat(array.get(0)).isEqualTo("b");
        assertThat(array.get(1)).isEqualTo("c");
    }

    @Test
    void shrinksCapacityAfterDrainingBelowAQuarterFull() {
        DynamicArray<Integer> array = new DynamicArray<>();
        for (int i = 0; i < 1000; i++) {
            array.add(i);
        }
        int grownCapacity = array.capacity();

        for (int i = 999; i >= 20; i--) {
            array.remove(i);
        }

        assertThat(array.capacity()).isLessThan(grownCapacity);
        for (int i = 0; i < array.size(); i++) {
            assertThat(array.get(i)).isEqualTo(i);
        }
    }

    @Test
    void getAndSetAndRemoveRejectOutOfBoundsIndexes() {
        DynamicArray<String> array = new DynamicArray<>();
        array.add("only");

        assertThatThrownBy(() -> array.get(-1)).isInstanceOf(IndexOutOfBoundsException.class);
        assertThatThrownBy(() -> array.get(1)).isInstanceOf(IndexOutOfBoundsException.class);
        assertThatThrownBy(() -> array.set(5, "x")).isInstanceOf(IndexOutOfBoundsException.class);
        assertThatThrownBy(() -> array.remove(5)).isInstanceOf(IndexOutOfBoundsException.class);
    }

    @Test
    void iteratesInInsertionOrderAndExhaustsCorrectly() {
        DynamicArray<Integer> array = new DynamicArray<>();
        array.add(1);
        array.add(2);
        array.add(3);

        List<Integer> collected = new ArrayList<>();
        for (int value : array) {
            collected.add(value);
        }

        assertThat(collected).containsExactly(1, 2, 3);
    }

    @Test
    void constructorRejectsNonPositiveInitialCapacity() {
        assertThatThrownBy(() -> new DynamicArray<Integer>(0)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void isEmptyReportsFalseOnceAnElementHasBeenAdded() {
        DynamicArray<String> array = new DynamicArray<>();

        array.add("a");

        assertThat(array.isEmpty()).isFalse();
    }

    @Test
    void iteratorNextThrowsOnceExhausted() {
        DynamicArray<Integer> array = new DynamicArray<>();
        array.add(1);
        Iterator<Integer> iterator = array.iterator();
        iterator.next();

        assertThatThrownBy(iterator::next).isInstanceOf(NoSuchElementException.class);
    }
}

src/test/java/com/datastructures/linear/dynamicarray/applied/BatchRecordBufferTest.java

package com.datastructures.linear.dynamicarray.applied;

import org.junit.jupiter.api.Test;

import java.math.BigDecimal;
import java.time.Instant;
import java.util.ArrayList;
import java.util.List;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class BatchRecordBufferTest {

    @Test
    void drainInChunksOfSplitsRecordsIntoFixedSizeChunksWithASmallerLastChunk() {
        BatchRecordBuffer buffer = new BatchRecordBuffer();
        for (int i = 0; i < 25; i++) {
            buffer.ingest(record("policy-" + i));
        }

        List<List<PolicyBatchRecord>> chunks = new ArrayList<>();
        buffer.drainInChunksOf(10, chunks::add);

        assertThat(chunks).hasSize(3);
        assertThat(chunks.get(0)).hasSize(10);
        assertThat(chunks.get(1)).hasSize(10);
        assertThat(chunks.get(2)).hasSize(5);
        assertThat(chunks.get(0).get(0).policyId()).isEqualTo("policy-0");
        assertThat(chunks.get(2).get(4).policyId()).isEqualTo("policy-24");
    }

    @Test
    void drainInChunksOfProducesExactlyOneFullChunkWhenSizeDividesEvenly() {
        BatchRecordBuffer buffer = new BatchRecordBuffer();
        buffer.ingest(record("policy-a"));
        buffer.ingest(record("policy-b"));

        List<List<PolicyBatchRecord>> chunks = new ArrayList<>();
        buffer.drainInChunksOf(2, chunks::add);

        assertThat(chunks).hasSize(1);
        assertThat(chunks.get(0)).hasSize(2);
    }

    @Test
    void drainClearsTheBufferAfterwards() {
        BatchRecordBuffer buffer = new BatchRecordBuffer();
        buffer.ingest(record("policy-a"));
        buffer.ingest(record("policy-b"));

        buffer.drainInChunksOf(10, chunk -> { });

        assertThat(buffer.size()).isZero();
    }

    @Test
    void drainOnAnEmptyBufferInvokesNoChunks() {
        BatchRecordBuffer buffer = new BatchRecordBuffer();

        List<List<PolicyBatchRecord>> chunks = new ArrayList<>();
        buffer.drainInChunksOf(10, chunks::add);

        assertThat(chunks).isEmpty();
    }

    @Test
    void drainInChunksOfRejectsANonPositiveChunkSize() {
        BatchRecordBuffer buffer = new BatchRecordBuffer();

        assertThatThrownBy(() -> buffer.drainInChunksOf(0, chunk -> { }))
                .isInstanceOf(IllegalArgumentException.class);
    }

    private static PolicyBatchRecord record(String policyId) {
        return new PolicyBatchRecord(policyId, BigDecimal.valueOf(199.90), Instant.now());
    }
}

Ver relatório completo de cobertura JaCoCo →