Dynamic Array — The Data Structures Atlas

Category: Linear

The problem

A plain Java array is fixed-size at creation. Most real use cases don't know the final size up front — records arrive one at a time from a file, a queue, a request. Allocating "enough" capacity means either guessing too high (wasted memory) or too low (an overflow you have to handle by hand: allocate a bigger array, copy every element across, keep going).

The solution

Wrap a raw array and grow it automatically: when an add would overflow the backing array, allocate a new array at double the capacity, copy everything across, and keep appending. A single resize is O(n), but it happens exponentially less often as the array grows, so the average cost per add across many appends — the amortized cost — stays O(1). Shrinking mirrors this: once occupancy drops to a quarter of capacity, halve it, so a fill-then-drain workload doesn't thrash by resizing at every single removal near one boundary.

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"]

Operation	Cost	Why
`get(index)` / `set(index, v)`	O(1)	direct array offset
`add(v)` (append)	O(1) amortized	doubling keeps resize frequency exponentially small
`remove(index)`	O(n)	shifts every element after `index` left by one
iteration	O(n)	contiguous, cache-friendly scan

Classic example

classic/DynamicArray is built on a raw Object[], not java.util.ArrayList — add, get, set, remove, and Iterable<T> are all hand-rolled, including the doubling growth and quartering shrink policy. DynamicArrayTest covers growth past the initial capacity, shrink-after-drain, out-of-bounds access, and iterator exhaustion.

Applied example: batch record buffer

applied/BatchRecordBuffer stages PolicyBatchRecord rows as they arrive from an insurance-premium batch extraction, then hands them out to parallel workers in fixed-size chunks via drainInChunksOf. This is exactly the shape a large batch pipeline (3M+ rows/day at a large insurer) runs into: ingestion is pure append, and draining is a single bulk scan — a dynamic array's contiguous layout serves both better than a linked list would. BatchRecordBufferTest covers even/uneven chunk boundaries and the empty-buffer case.

Benchmark

./gradlew :linear:dynamic-array:jmh

Real run on this machine (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork):

Benchmark	size=100	size=10,000	size=1,000,000
`append` (total for N appends)	611 ns	75,047 ns	75.6 ms
`get` (single indexed read)	2.50 ns	2.44 ns	2.46 ns

get stays flat at ~2.4–2.5 ns regardless of size — the O(1) claim, falsifiable and confirmed. append's total cost scales roughly linearly with size (≈6–7.5 ns/element at 100 and 10,000), which is what "amortized O(1) per element" looks like in aggregate; the 1,000,000 row had one iteration land on a large resize and skews the average up, which is the honest, unsmoothed result of a doubling-array resize actually happening mid-benchmark, not a measurement error.

When not to use it

Frequent insertion/removal at the front or middle: every such operation is O(n) here. A doubly linked list (or an ArrayDeque-style circular buffer for the front-only case) is the better fit.
If the maximum size is known exactly up front and never changes, a plain fixed array skips the resize machinery entirely.
Need range queries or ordered floor/ceiling lookups by key? See this repo's Binary Search Tree module instead.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :linear:dynamic-array:jacocoTestReport

Report at linear/dynamic-array/build/reports/jacoco/test/html/index.html.

Unit tests

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());
    }
}

View full JaCoCo coverage report →