Arrays and Dynamic Arrays: Random Access and Amortized O(1) Append

You’re adding songs to a playlist. You drag in the tenth, the fiftieth, the five-hundredth — and the app never once says "sorry, this playlist is full, start a new one." Then you tap the song sitting at position 237 and it starts instantly, no scrolling, no waiting.

Two quiet miracles are hiding in that moment. One: a list that grows forever without you ever booking space for it. Two: reaching any item, however deep, in a single step. Both come from the most fundamental container in all of computing — the array — and its shape-shifting cousin, the dynamic array. By the end of this article you and I will have built the growable one from scratch, and you’ll know exactly why appending to it is "free" even though it sometimes has to copy everything you own.

Let’s start nowhere near a computer

Picture a row of seats bolted to the floor of a theatre. They’re evenly spaced and numbered from 0. Your ticket says seat 4.

You don’t walk in and count seats from the aisle — one, two, three — until you arrive. You glance at the numbers, and because every seat is the same width and the row starts at a known spot, you walk straight to it. In your head you did a tiny sum without noticing: seat 4 is four seat-widths from the start.

That sum is the entire superpower of an array. The row’s starting position is an address. Each seat is a fixed size. So the location of seat i is just:

position of seat i  =  start  +  i × seat_width

One multiply, one add, and you’re standing at the right seat — whether it’s seat 4 or seat 400. You never touched the seats in between. Hold onto that, because it’s the whole reason arrays feel instant: the index is an address, and computing an address is one step, not a walk.

Now the second half of the story — the part that isn’t so effortless. Imagine those seats are a bookshelf instead, packed end to end with exactly enough room for the books you own. A new book arrives. There’s no gap to slide it into and no empty shelf at the end — the wall is right there. Your only move is to find a bigger, empty shelf, carry every book across, and then add the new one.

That carry-everyone-across is the price of a block that has to stay contiguous. Keep both pictures in your head — the walk-straight-to-a-seat and the widen-the-shelf — because the rest of this article is just those two moments turned into code.

The same block, all over your day

Once you know the shape, you spot contiguous indexed blocks everywhere. The pixels of the photo you just took are a flat array — row after row of colour, addressed by position. A spreadsheet column, the frames of a video, the samples in a sound file, the bytes of any file on disk: all arrays. When your program calls a function, the call stack it pushes onto is an array. Your ArrayList, your ArrayDeque, the buffer inside a StringBuilder — arrays wearing jackets.

But the most illuminating one hides in plain sight. Every time you build a string in a loop — gluing together a report, a query, a line of CSV — a StringBuilder is quietly doing the widen-the-shelf dance for you. It’s a dynamic array of characters. Each append drops a character into a spare slot; when the buffer fills, it books a bigger one and copies. You’ve been riding the doubling trick we’re about to build for years without ever seeing the machinery. Let’s finally look at it.

What an array actually looks like

Here’s a block of eight values laid out in memory. The values sit shoulder to shoulder, addresses climbing by a fixed step (four bytes each, say). Under each slot is its index, and under that its actual address.

Ask for index 5 and the machine doesn’t search. It computes base + 5 × elementSize = 100 + 5 × 4 = 120, reads that address, and hands you the value. That’s O(1) random access — "random" meaning you can hit any index in the same one step, in any order, with no penalty for jumping around.

The catch is baked into that same formula. It only works if the elements are packed together with no gaps and known width — one contiguous block. That contiguity is the source of both the magic (address math) and the pain (a full array can’t just sprout a new slot; the memory right after it belongs to someone else). So a raw array has a fixed size decided the day it’s born. To grow, we need the jacket.

Let’s build a growing one, step by step

We’ll build a DynamicArray in small pieces, and at the end I’ll hand you the whole class. The plan is simple: keep a plain fixed array underneath, and be smarter than it about running out of room.

Step 1: the two numbers

A dynamic array is a fixed array plus a single extra integer, and the gap between them is the whole idea. Capacity is how many slots you’ve booked. Size is how many actually hold a value. Capacity is almost always bigger than size — that slack is the spare room that makes growing cheap.

public final class DynamicArray<E> {
 
    private Object[] elements;   // the backing block — may hold spare slots
    private int size;            // how many slots actually hold a value
 
    public DynamicArray() {
        this.elements = new Object[2];   // a little room to start
        this.size = 0;
    }
}

The backing block is Object[] so it can hold any element type; the <E> on the class keeps the outside world type-safe. Notice size starts at 0 even though we booked two slots — those slots exist, but nothing lives in them yet.

Step 2: read and write by index

Reading is where we cash in the array’s superpower. get(i) is a bounds check and a single indexed read — the address math from the diagram, O(1). set(i, v) overwrites in place, also O(1).

@SuppressWarnings("unchecked")
public E get(int index) {
    checkIndex(index);
    return (E) elements[index];
}
 
public E set(int index, E value) {
    checkIndex(index);
    @SuppressWarnings("unchecked")
    E old = (E) elements[index];
    elements[index] = value;
    return old;
}
 
private void checkIndex(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("index " + index + ", size " + size);
    }
}

The bounds check guards against size, not capacity. Index 6 might be a real allocated slot, but if size is 5 it’s spare room holding garbage — reading it would be a bug, so we refuse. The rule: you can only touch what you’ve actually stored.

Step 3: append — drop it in the spare slot

Adding to the end is the common case, and usually it’s trivial: if there’s a spare slot, drop the value at index size and bump size by one.

public void add(E value) {
    if (size == elements.length) {   // no spare slot left
        grow();
    }
    elements[size] = value;
    size++;
}

Everything interesting is in that first line. When size still hasn’t caught up to capacity, add is a single write — O(1), done. The drama only starts when size == elements.length: the block is full, and we have to grow(). So the real question of this entire article is: what should grow() do?

Step 4: growing — the tempting mistake first

Your first instinct is probably to be frugal. We need one more slot, so let’s make the array exactly one bigger:

private void grow() {
    // grow by exactly one — surely that's the frugal choice?
    elements = Arrays.copyOf(elements, elements.length + 1);
}

This is correct, and it is a disaster. Think about what happens on a burst of appends. The array is full at size 1, so append #2 copies 1 element. Full again at size 2, so #3 copies 2. Then #4 copies 3, #5 copies 4... every single append is now full, so every single append copies the entire array first.

Add up the copies to build a list of n items: 1 + 2 + 3 + … + (n−1), which is n(n−1)/2 — that’s O(n²). Concretely, building a list of just 1,000 items this way performs 499,500 element-copies. You wanted a list; you got a machine for copying memory.

The fix is to grow in bigger jumps so that growing becomes rare. And the jump that works is: double.

Step 5: growing by doubling

When the block fills, book one twice as big and copy everyone across.

private void grow() {
    int newCapacity = elements.length * 2;
    elements = Arrays.copyOf(elements, newCapacity);
}

Yes, a single grow() still copies everything — that one append is O(n). But because we just doubled the capacity, the next n appends all land in spare slots for free before we ever have to copy again. That trade — one expensive copy that buys a long run of cheap appends — is the heart of the whole structure, and it’s important enough that we’ll prove it properly in a moment.

Step 6: insert and remove in the middle — the shifting tax

Appending is cheap. Inserting in the middle is not, and the reason is the same contiguity that made reads fast. To open a gap at index i, every element from i onward has to slide one slot to the right. There’s no shortcut — the block must stay packed.

public void add(int index, E value) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("index " + index + ", size " + size);
    }
    if (size == elements.length) {
        grow();
    }
    for (int i = size; i > index; i--) {   // walk from the back
        elements[i] = elements[i - 1];     // slide each one right
    }
    elements[index] = value;
    size++;
}

Notice we walk from the back forward. If we shifted front-to-back instead, we’d overwrite the next value before we’d moved it — copying one element over all the others. Walking backward keeps a clean, empty slot always one step ahead of us.

Removing is the mirror image: pull everything after i one slot to the left to close the gap.

@SuppressWarnings("unchecked")
public E removeAt(int index) {
    checkIndex(index);
    E removed = (E) elements[index];
    for (int i = index; i < size - 1; i++) {
        elements[i] = elements[i + 1];     // slide each one left
    }
    elements[size - 1] = null;             // release the old tail for GC
    size--;
    return removed;
}

That elements[size - 1] = null line is easy to forget and quietly important. After shifting left, the last slot still holds a duplicate reference to an object that’s now logically gone. Leave it there and the garbage collector can never reclaim that object — a slow leak of "loitering" references. Nulling the tail lets it go.

Both middle operations are O(n): in the worst case (touching index 0) you move every other element. This is the array’s soft underbelly, and it’s exactly where a linked structure would beat it.

Why append is (amortized) O(1)

Here’s the part worth slowing down for — it’s the single most-tested idea about dynamic arrays, and it trips up people who can otherwise code the whole class from memory.

We just admitted that some appends are O(n): the ones that trigger a doubling copy every element. So how can anyone say add is O(1)? The honest answer is a specific, careful word: it’s amortized O(1) — meaning if you average the cost over any run of appends, each one works out to a constant, even though a rare individual append spikes.

The picture makes the claim believable. Plot the cost of each append as you build a list from empty:

Most bars are height 1 — a plain drop into a spare slot. The spikes are the doublings: copy 1, then copy 2, then 4, then 8. Two things happen at once, and they’re the whole trick: the spikes get taller, but they also get twice as far apart. A copy of 8 only happens after 8 cheap appends have banked room for it. The expense is always outrun by the free appends before it.

The geometric series that makes it work

Let’s make "outrun" exact. Suppose you append n items, doubling from a capacity of 1. The copies happen when the array is full — at sizes 1, 2, 4, 8, and so on. So the total copying you ever do is:

1 + 2 + 4 + 8 + … + n/2

A doubling series has a beautiful property: each term is bigger than everything before it combined. 8 is more than 1 + 2 + 4. So the whole sum is dominated by its last term and lands just short of 2n. For n = 16, it’s exactly 1 + 2 + 4 + 8 = 15 — fifteen copies to place sixteen items.

Add the n cheap placements to those ~n copies and building the entire list costs under 2n writes — spread over n appends, that’s under two writes each. Constant, on average. Compare the two growth strategies head to head for a list of 1,000 items and the difference is night and day:

Same list, same code shape — a single decision in grow() turns a quadratic disaster into a linear walk.

Why two, and the honesty of "amortized"

Why double, and not grow by ten times, or by half? The growth factor trades two things against each other. A bigger factor means fewer resizes (you copy less often) but more wasted memory (a nearly-empty giant block). Doubling is the sweet spot people reach for: it keeps the number of resizes to about log₂ n for n appends while never wasting more than roughly half the block.

One more piece of honesty, because interviewers probe it: amortized O(1) is not worst-case O(1). A single unlucky append — the one that triggers the resize — genuinely stalls for O(n) while it copies. For most code that’s invisible. But for a latency-sensitive path (a real-time system, a tight game loop), that occasional multi-millisecond hitch is real, and the fix is to preallocate the capacity you’ll need up front so the copy never happens mid-flight. Knowing the difference between "amortized" and "worst-case" is often the exact thing being tested.

What each operation really costs

Here’s the whole structure at a glance, measured against the obvious alternative — a doubly linked list, where each element is its own node pointing at its neighbours.

The asterisk is the trap. A linked list’s middle-insert is O(1) only if you already hold the node — but finding the node is O(n), and you gave up random access to get here. So the list’s headline win often evaporates in practice.

The complete implementation

Every piece, assembled into one class you can drop into a project or rebuild on a whiteboard:

package dev.fiveyear.arrays;
 
import java.util.Arrays;
 
/** A growable, index-addressable list backed by one contiguous array. */
public final class DynamicArray<E> {
 
    private Object[] elements;   // the backing block — may hold spare slots
    private int size;            // how many slots actually hold a value
 
    public DynamicArray() {
        this.elements = new Object[2];   // a little room to start
        this.size = 0;
    }
 
    /** Elements currently stored. O(1). */
    public int size() {
        return size;
    }
 
    /** Slots currently allocated — usually more than size. Shown here for teaching. */
    public int capacity() {
        return elements.length;
    }
 
    public boolean isEmpty() {
        return size == 0;
    }
 
    /** Append to the end. Amortized O(1). */
    public void add(E value) {
        if (size == elements.length) {   // no spare slot left
            grow();
        }
        elements[size] = value;
        size++;
    }
 
    /** Read by index. O(1). */
    @SuppressWarnings("unchecked")
    public E get(int index) {
        checkIndex(index);
        return (E) elements[index];
    }
 
    /** Overwrite by index; returns the old value. O(1). */
    public E set(int index, E value) {
        checkIndex(index);
        @SuppressWarnings("unchecked")
        E old = (E) elements[index];
        elements[index] = value;
        return old;
    }
 
    /** Insert at index, sliding the tail one slot right. O(n). */
    public void add(int index, E value) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index " + index + ", size " + size);
        }
        if (size == elements.length) {
            grow();
        }
        for (int i = size; i > index; i--) {   // walk from the back
            elements[i] = elements[i - 1];     // slide each one right
        }
        elements[index] = value;
        size++;
    }
 
    /** Remove at index, sliding the tail one slot left; returns the removed value. O(n). */
    @SuppressWarnings("unchecked")
    public E removeAt(int index) {
        checkIndex(index);
        E removed = (E) elements[index];
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];     // slide each one left
        }
        elements[size - 1] = null;             // release the old tail for GC
        size--;
        return removed;
    }
 
    // Double the backing block and copy every element into it.
    private void grow() {
        int newCapacity = elements.length * 2;
        elements = Arrays.copyOf(elements, newCapacity);
    }
 
    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index " + index + ", size " + size);
        }
    }
}

And here it is doing the things we drew:

DynamicArray<String> list = new DynamicArray<>();
list.add("a");
list.add("b");
list.add("c");
 
list.get(1);            // "b"  — one jump, no scanning
list.set(1, "B");       // returns "b"; slot now holds "B"
 
list.add(1, "x");       // insert      -> [a, x, B, c]
list.removeAt(0);       // returns "a" -> [x, B, c]
list.size();            // 3

The interview corner

Dynamic arrays are the warm-up in half of all coding rounds, and "implement ArrayList" is a genuine question. What separates a pass from a stumble is the reasoning around growth and cost.

Before you write a line, ask:

• "Does removal need to preserve order?" If order doesn’t matter, removeAt can be O(1) — swap the target with the last element and drop the last slot, no shifting. That single question can turn an O(n) operation into O(1).
• "Roughly how many elements, and is the workload append-heavy or middle-insert-heavy?" Append-heavy loves this structure; lots of front/middle inserts point at a linked list or a deque.
• "Do we know the final size up front?" If yes, preallocate the capacity and every resize disappears — no doubling, no worst-case spike.

The follow-up ladder (each one a real escalation, not a rephrase):

1. "Make removeAt O(1)." → If order is expendable, swap the removed index with the last element, then shrink size by one — you move exactly one element instead of shifting the whole tail.
2. "Support O(1) add and remove at both ends." → That’s a deque. Back it with a circular buffer: track a head and tail index that wrap around, so the front never has to shift. This is what ArrayDeque does.
3. "Keep it sorted as items arrive." → Binary-search the insertion point in O(log n), but the insert itself still shifts in O(n). Be clear that the shift, not the search, dominates — a sorted array is cheap to read, expensive to maintain.
4. "Now it’s shared across threads." → A resize is a read-modify-write on the backing reference; two appends can race and stomp the same slot or copy a stale array. Guard it with a lock or reach for a copy-on-write structure — it’s the same read-modify-write hazard covered in the thread-safe LRU cache.
5. "Cap the wasted memory when the list shrinks." → Halve the backing block when size falls below a quarter of capacity. The quarter (not half) threshold is deliberate — it leaves a gap between the grow and shrink points so you can’t thrash.

Mistakes that fail the round:

• Shrinking at exactly half. If you grow at full and shrink at half, an alternating add/remove sitting right on the boundary resizes on every single call — silently O(n) per operation. Leave a hysteresis gap: grow at full, shrink at a quarter.
• Forgetting to null the removed tail slot. The backing array keeps a live reference to the "removed" object, so it never gets collected — a leak that passes every functional test and shows up only under a memory profiler.
• Calling append "O(1)" flatly. It’s O(1) amortized; the append that triggers a resize is O(n). Saying the word "amortized" out loud is often the exact signal the interviewer is listening for.

Where to go from here

You now own the two ideas that everything else builds on: the index is an address (so reads are free), and doubling makes growth free on average (so appends are free too). Three natural next stops:

• Circular buffers and ArrayDeque — wrap a head/tail pointer around a fixed array and suddenly both ends are O(1). It’s the array behind queues, ring buffers, and bounded producer-consumer pipelines.
• When the block stops being the right tool — reach for pointer-based structures like the trie when you need shared prefixes, or a linked list when middle-insertion truly dominates and you never need random access.
• Cache-friendliness, measured — dig into why a flat array so often beats an asymptotically-equal linked structure in the real world. Spatial locality and prefetching are why HashMap buckets, B-tree nodes, and column stores all pack their data into arrays under the hood.

Next time a playlist swallows its thousandth song without blinking, you’ll know the trick: a humble block of memory that reaches any slot by arithmetic, and quietly doubles itself the moment it runs out of room.