Building a Dynamic Array from Scratch

Data structures and algorithms is a course every computer engineering student takes at the undergraduate level — and one that most students question at some point, wondering how it will ever be useful in real life. Personally, I think it's one of the most enjoyable courses in computer science. When you genuinely wrestle with the concepts here, your ability to think abstractly and your perspective on engineering changes significantly.

I've always lived by Aristotle's saying: "To know is to know the cause." That's what drove me to look closely at the difference between a static array and a dynamic list in Java — that is, how the gap between an Array and an ArrayList is actually bridged. And then I wanted to build one myself from scratch. That curiosity is what started all of this.

Every ArrayList internally holds a static array. If no initial capacity is given, it defaults to 10. Knowing this, I started by defining the necessary fields:

private static final int DEFAULT_CAPACITY = 10;
private int[] data;
private int size;
private int capacity;

public DynamicArray() {
    this(DEFAULT_CAPACITY);
}

The Core Operations

I grouped the methods into two categories in my head: the ones the user directly interacts with, and the ones that silently keep everything working under the hood.

User-Facing Methods

public int get(int index) {
    index = resolveIndex(index);
    return data[index];
}

public void set(int index, int value) {
    index = resolveIndex(index);
    data[index] = value;
}

public void pushBack(int value) {
    ensureCapacity();
    data[size] = value;
    size++;
}

public int popBack() {
    if (isEmpty()) {
        throw new IllegalStateException("Array is empty");
    }
    int value = data[size - 1];
    size--;
    shrinkIfNeeded();
    return value;
}

public void insertAt(int index, int value) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index " + index + " out of bounds for size " + size);
    }
    ensureCapacity();
    for (int i = size; i > index; i--) {
        data[i] = data[i - 1];
    }
    data[index] = value;
    size++;
}

public int removeAt(int index) {
    index = resolveIndex(index);
    int value = data[index];
    for (int i = index; i < size - 1; i++) {
        data[i] = data[i + 1];
    }
    size--;
    shrinkIfNeeded();
    return value;
}

public int size() { return size; }
public int capacity() { return capacity; }
public boolean isEmpty() { return size == 0; }

public void print() {
    StringBuilder sb = new StringBuilder("[");
    for (int i = 0; i < size; i++) {
        if (i > 0) sb.append(", ");
        sb.append(data[i]);
    }
    sb.append("] (size=").append(size).append(", capacity=")
            .append(capacity).append(")");
    System.out.println(sb);
}

For the user-facing side, pushBack and popBack handle the two ends of the array. pushBack adds an element to the tail, while popBack removes it and hands it back. Deletion isn't just about shrinking size though — after every removal, I call shrinkIfNeeded to keep memory usage honest.

insertAt and removeAt are where things get more expensive. Inserting at an arbitrary index means shifting every element to the right of it — that's O(n) in the worst case. Same logic applies for removal, just in the opposite direction. This is the fundamental trade-off of arrays: fast access, slow middle insertions.

One detail I'm particularly fond of is resolveIndex. It handles negative indices the same way Python does — passing -1 gives you the last element, -2 the second to last, and so on. It's a small touch, but it makes the API feel more intuitive.

Helper Methods

private int resolveIndex(int index) {
    if (index < 0) {
        index += size;
    }
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index " + index + " out of bounds for size " + size);
    }
    return index;
}

private void ensureCapacity() {
    if (size == capacity) {
        resize(capacity * 2);
    }
}

private void shrinkIfNeeded() {
    if (size > 0 && size == capacity / 4 && capacity > DEFAULT_CAPACITY) {
        resize(capacity / 2);
    }
}

private void resize(int newCapacity) {
    int[] newData = new int[newCapacity];
    for (int i = 0; i < size; i++) {
        newData[i] = data[i];
    }
    data = newData;
    capacity = newCapacity;
}

The Resize Logic — Where the Magic Happens

When the array fills up, ensureCapacity doubles the current capacity by calling resize. This is the classic amortized O(1) trick: yes, a single pushBack can trigger an O(n) copy — but that only happens logarithmically often. Average it out over many insertions, and each one costs O(1). That's the amortized guarantee.

The shrink side is equally thoughtful. I only shrink when size drops to capacity / 4, not capacity / 2. Why? If I shrunk at the halfway point, a sequence of alternating insertions and deletions right at that boundary would trigger a resize on every single operation — a phenomenon called thrashing. Waiting until a quarter capacity gives the array enough breathing room.

What I Took Away

Writing this from scratch changed how I think about ArrayList. Every time I call .add() in production code now, I know there's a potential resize lurking underneath — and I think about whether I should pre-size the list with an initial capacity.

That's the point of Aristotle's quote I opened with. Knowing that ArrayList grows automatically is useful. Knowing why and how — the doubling strategy, the amortized cost, the shrink threshold — that's what actually makes you a better engineer.