Arrays and Dynamic Arrays from Scratch

Time to build one. The growable array is the structure you use more than any other: a list in Python, an Array in JavaScript, a slice in Go, a vector in C++, an ArrayList in Java. They have different names and identical guts, and by the end of this lesson you will have built those guts yourself, in three languages. The first two lessons priced the contiguous block of memory; this one wraps a machine around it.

The fixed array: one multiply, one add

The raw material is the fixed-size array: one contiguous block of memory, carved into equal-sized slots. Equal and side by side, and that single design choice buys the array its superpower.

Say each slot holds a 4-byte integer and the block starts at address 0x1000. Item 0 lives at 0x1000. Item 1 lives at 0x1004. Item 7 lives seven slots in, 28 bytes from the start, at 0x101C. In general:

address_of(items[i]) = base_address + i * slot_size

One multiply, one add, one load. There is no walking and no searching: the formula tells you exactly where item i is, whether i is 3 or 3 million, for the same three operations. That is why indexing an array is O(1). It's not an optimization or an implementation detail; it's arithmetic, and it only works because every slot is the same size and the block has no gaps.

This is also lesson 2 paying off. The block is contiguous, so a scan through it is sequential, so every 64-byte cache line is fully used and the prefetcher streams the data before the loop arrives. The fixed array is simultaneously the cheapest structure to index and the cheapest to scan. Everything else in this course gets compared to it.

The price of order: shifting

Indexing is free because every element sits exactly where the formula says it must. The same rigidity sends a bill the moment you disturb the order.

Insert a new element at the front of a million-element array. Slot 0 is occupied, and there is no slot -1. The only way to make room is to shift: element 999,999 moves right one slot, then 999,998, all the way down, a million moves before the actual write. Insert at position i and you shift the n − i elements after it; delete from position i and you shift them back to close the gap. Worst case, O(n) per insert or delete, and the worst case is the front.

This is not a textbook hypothetical. In Python, list.pop() removes the last element in O(1), while list.pop(0) removes the first and quietly shifts the entire list: same method, one argument, a factor of a million in work on a million-element list. JavaScript's Array.prototype.shift() versus pop() is the identical trap. (Structures built for cheap removal at the front exist, and they get their own treatment later in the course; the point here is that the array's contract is cheap at the end, expensive everywhere else.)

The wall: capacity is a promise

There is a harder problem than shifting. The block has a fixed size, and that size was a promise to the allocator. You asked for 8 slots; the memory manager reserved exactly 32 bytes and was free to hand the bytes immediately after your block to someone else. By the time element 9 shows up, the address where slot 9 would go may be the middle of another object.

So you cannot grow in place, not reliably (some allocators can occasionally extend a block when the neighboring space happens to be free, but no structure can be designed around "occasionally"). When the block is full, there is exactly one move available:

1. Allocate a bigger block somewhere else.
2. Copy every existing element across.
3. Free the old block.
4. Append into the new spare room.

Step 2 is O(n), every element, every time you outgrow the block. The whole design problem of the dynamic array is choosing the new size so that this O(n) copy happens rarely enough not to matter.

The machine: length versus capacity

Here is the dynamic array in its entirety. Three fields:

struct dynarray:
    data: pointer to a block      # where the elements live
    len:  integer                 # slots currently filled
    cap:  integer                 # slots currently allocated

The invariant is len <= cap, and the gap between them is the entire trick: deliberately allocate more than you currently need, so most appends land in spare room.

function append(arr, x):
    if arr.len == arr.cap:        # no spare room
        grow(arr)                 # the slow path (next section)
    arr.data[arr.len] = x         # write into the next free slot
    arr.len = arr.len + 1         # bump the length

The fast path is two steps: write, bump. O(1), unconditionally. And notice where the write lands: immediately after the previous element, in a block you touched moments ago. By lesson 2's rules that cache line is warm, so the fast path is cheap on paper and cheap on the machine. Indexing checks i < len and then uses the same base-plus-offset formula as the fixed array, so reads stay O(1) too.

The slow path: grow

When len == cap, the append takes the slow path:

function grow(arr):
    new_cap = arr.cap * 2         # the growth factor (see below)
    new_block = allocate(new_cap)
    copy arr.data[0 .. arr.len] into new_block
    free(arr.data)
    arr.data = new_block
    arr.cap = new_cap

Walk the trace. Start from capacity 1 and append nine elements:

Most appends are the two-step fast path. But appends 2, 3, 5, and 9 each triggered a full copy of everything so far, and append 9 alone cost eight copies plus the write. That is the exact moment an innocent-looking append quietly costs O(n): same function call from the outside, wildly different bill.

Total copies for nine appends: 1 + 2 + 4 + 8 = 15, just under 2n. That's not a coincidence of this trace; it's the amortized argument from lesson 1, collected rather than re-derived. The doublings are spaced exponentially apart, so all copies ever performed sum to less than 2n, which spread over n appends is about 3 steps each: O(1) amortized. The token bank from lesson 1 never overdrafts.

Hold on to the fine print, though, because it matters more here than anywhere: amortized means the average over a run is constant. It does not mean every append is fast. On a list of a hundred million elements, some single append will stall while a hundred million elements move. The sum is guaranteed; the spike is real; both facts are true at once.

Growth factors in the wild

Why double, specifically? First, why the growth must be a multiplier at all: grow by a fixed step of 10 slots and a million appends trigger a copy every 10 appends, each copy proportional to the current size. That sums to O(n²), quadratic in disguise, the GTA bug wearing a new costume. Any constant factor greater than 1 restores the geometric spacing that makes the amortized math work.

But the factor doesn't have to be 2, and real implementations disagree:

These are implementation internals, not contracts; any of them can change in a release. But the spread is the lesson. A bigger factor means fewer copies but more waste: right after a 2x growth, the block is half empty, and a 2 GB array may be squatting on 4 GB. A smaller factor wastes less but copies more often. There's also a subtler allocator argument, written up famously in Facebook's folly fbvector documentation: with a factor below the golden ratio (~1.618), the freed blocks from earlier growths can eventually be coalesced and reused for a later one, while doubling always needs fresh memory; whether that pays off in practice depends on the allocator. Every one of those teams did the same arithmetic and picked a different point on the same curve. There is no free answer, only the trade.

The marquee footgun: Go slices share until they don't

The three-word machine has a sharp edge, and Go exposes it more honestly than any other mainstream language, which means Go engineers cut themselves on it weekly. A Go slice is the struct above: pointer, length, capacity. The crucial fact: slicing does not copy.

a := []int{10, 20, 30, 40}
b := a[:2]              // no copy: b points at a's block, len(b)=2, cap(b)=4
 
b = append(b, 99)       // spare capacity exists, so append writes IN PLACE
fmt.Println(a)          // [10 20 99 40]   appending to b mutated a
 
b = append(b, 1, 2, 3)  // exceeds cap: append allocates a new block and copies
b[0] = 0
fmt.Println(a)          // [10 20 99 40]   a is no longer affected

Walk it. a[:2] builds a new header over the same backing array: length 2, but capacity 4, because the block extends past b's end. The first append checks for spare capacity, finds it, and writes 99 into the next slot of the shared block, which is a's slot 2. You appended to b and mutated a. The second append needs more room than the block has, so it allocates a fresh block and copies; from that moment b is divorced from a and writes no longer travel between them.

Same function, append. Sometimes it aliases, sometimes it divorces, and which one you get depends on a capacity you probably never checked. This bites hardest in functions that receive a slice parameter and append to it, silently clobbering data the caller still holds. The defensive idioms: the full slice expression b := a[:2:2], which caps the capacity at 2 so any append must reallocate immediately, or an explicit copy into a fresh slice when you intend to own the data.

The other footguns

The Go story generalizes. Three more edges, in every language that exposes the machinery:

• Invalidation. When the array grows, every element moves to a new address and the old block is freed. In C++, any pointer, reference, or iterator you saved into a vector before a push_back that reallocates now points into freed memory; using it is undefined behavior. In Go, a stale slice header keeps you staring at the abandoned block while new appends land in the new one. The rule: don't hold interior pointers across an append unless you've guaranteed capacity.
• The spike. O(1) amortized still means some single append stalls for a full O(n) copy. Inside a 16 ms game frame, or on the hot path of a trading system, that one spike is the whole incident. Latency-sensitive code pre-allocates (next section) or uses structures with worst-case bounds, exactly the distinction lesson 1 flagged.
• The silent squat. Popping elements does not give memory back. A C++ vector that held ten million elements and now holds ten still owns the ten-million-slot block until you ask (shrink_to_fit, and even that is a non-binding request). Go never shrinks a slice's backing array while it's referenced. CPython's list does release memory when it drops below roughly half full, but that's CPython's current policy, not a property of the structure. Growth is automatic; shrinkage almost never is.

The antidote: pre-size

All three footguns share one antidote: if you know how many elements are coming, say so.

std::vector<int> v;
v.reserve(n);            // one allocation, capacity n, length still 0

s := make([]int, 0, n)   // length 0, capacity n

var list = new ArrayList<Integer>(n);

One allocation up front, and every append for the rest of the loop is the two-step fast path: no copies, no spikes, no invalidation mid-loop, no half-empty block. Look back at lesson 1's duplicate checker: the Go version passed a size hint to make, and the C++ version called reserve before the loop. That wasn't decoration; it was this lesson, applied early. The dynamic array's growth machinery is a brilliant default for when you can't predict n. The moment you can predict it, pre-size, and the grow-and-copy drama never happens.

A minimal dynamic array, in real code

The videos stay in pseudocode; here is the machine itself, append plus index plus grow, in the three languages this course carries. Each is deliberately minimal: integers only, no insert-at-i, no shrink, because the point is to see the skeleton.

The TypeScript version uses Int32Array as the raw fixed block so the capacity is honest (a plain JS array would secretly be a dynamic array already, which defeats the exercise). The Go version builds the machine manually from a fixed-length backing slice that we only ever index (no built-in append, that would be cheating). In C++ nothing is reclaimed for you, so the machine's full shape is visible, including the free.

class DynArray {
  private buf = new Int32Array(4) // the fixed block: capacity 4 to start
  private len = 0                 // slots filled
 
  get length(): number {
    return this.len
  }
 
  at(i: number): number {
    if (i < 0 || i >= this.len) throw new RangeError(`index ${i} out of bounds`)
    return this.buf[i] // base + i * 4 bytes, done by the typed array
  }
 
  push(x: number): void {
    if (this.len === this.buf.length) this.grow() // full: slow path
    this.buf[this.len] = x // write
    this.len++ // bump
  }
 
  private grow(): void {
    const bigger = new Int32Array(this.buf.length * 2) // allocate double
    bigger.set(this.buf) // copy everything
    this.buf = bigger // old block becomes garbage
  }
}

type DynArray struct {
	buf []int // backing block; allocated once per growth, only indexed
	n   int   // slots filled
}
 
func NewDynArray() *DynArray {
	return &DynArray{buf: make([]int, 4)}
}
 
func (d *DynArray) Len() int { return d.n }
 
func (d *DynArray) At(i int) int {
	if i < 0 || i >= d.n {
		panic("index out of bounds")
	}
	return d.buf[i]
}
 
func (d *DynArray) Push(x int) {
	if d.n == len(d.buf) { // full: slow path
		bigger := make([]int, len(d.buf)*2) // allocate double
		copy(bigger, d.buf)                 // copy everything
		d.buf = bigger                      // old block becomes garbage
	}
	d.buf[d.n] = x // write
	d.n++          // bump
}

class DynArray {
    int* buf_;          // the block
    size_t len_ = 0;    // slots filled
    size_t cap_ = 4;    // slots allocated
 
public:
    DynArray() : buf_(new int[cap_]) {}
    ~DynArray() { delete[] buf_; }
 
    // growth moves elements, so forbid shallow copies of the machine itself
    DynArray(const DynArray&) = delete;
    DynArray& operator=(const DynArray&) = delete;
 
    size_t size() const { return len_; }
 
    int at(size_t i) const {
        if (i >= len_) throw std::out_of_range("index out of bounds");
        return buf_[i];
    }
 
    void push(int x) {
        if (len_ == cap_) grow();  // full: slow path
        buf_[len_] = x;            // write
        ++len_;                    // bump
    }
 
private:
    void grow() {
        size_t new_cap = cap_ * 2;
        int* bigger = new int[new_cap];          // allocate double
        std::copy(buf_, buf_ + len_, bigger);    // copy everything
        delete[] buf_;                           // free the old block
        buf_ = bigger;
        cap_ = new_cap;
    }
};

In the TypeScript version, push is the pseudocode verbatim: check, maybe grow, write, bump. grow allocates double, copies with set (a single O(n) bulk copy), and drops the old buffer for the garbage collector to free. at bounds-checks against len, not capacity, so the spare slots are invisible to callers.

The Go version is the identical skeleton. make allocates the new block, copy is the O(n) move, and the garbage collector reclaims the old block once nothing references it. Real Go slices implement exactly this dance inside the runtime's growslice, just with the tapering growth factor from the table.

In the C++ version all three steps of the slow path are explicit: new allocates, std::copy moves the elements, delete[] frees the old block, and buf_ is repointed. This is the moment every saved pointer into the old block becomes a dangling pointer, which is why the class deletes its copy operations rather than pretend a shallow copy would be safe (a production vector implements proper copy and move semantics; that's deliberately out of scope for the skeleton).

All three classes are the same fifteen lines wearing different syntax, and every one of them is a working, honest miniature of the structure that ships in your language's standard library.

Where this shows up in production

Everywhere is barely an exaggeration. The default sequence type of every mainstream language is this machine, which means nearly every loop that builds up a collection is exercising the fast path and occasionally paying the slow one. The places it surfaces as a real engineering concern: Go code review (the aliasing gotcha above is a perennial source of subtle bugs in functions that append to slice arguments), latency-sensitive systems (game engines and trading systems pre-allocate precisely to delete the growth spike), and memory-constrained services (a long-lived process that built a huge list and then shrank it may still be squatting on the peak allocation). And one teaser: the grow-and-copy move you just built returns in lesson 12, when hash tables resize themselves with the same trick, copy spike and all. The linked list, the structure that never copies on growth, gets its honest hearing in lesson 5, toll booth and all.

Next lesson takes what looks like a special case and turns out to be its own world: the string. It's an array of characters underneath, but in Python, Java, JavaScript, and Go you cannot change one, not a single character, ever. Why every language made that choice, what it buys, and the hidden O(n) that turns an innocent loop of concatenations into a quadratic accident: that's lesson 4.