Dynamic array.

01 / The idea

You know the order. You do not know the final count.

Bibs 12, 7, and 31 cross the line, in that order. You write them down as they arrive. You can point at the second result without counting, and you have no idea how many more runners are coming. That is the whole job: ordered, indexed, open-ended.

You solved this today without noticing. A number[] in TypeScript, a slice in Go, a Vec in Rust. You pushed onto it and moved on. Underneath, something reserved a block of slots, filled them, and when they ran out, made the block bigger, usually by moving everything into a new one. You never saw it because it worked.

A dynamic array is that mechanism: an indexed sequence kept in a buffer that is replaced by a larger one when it fills. Direct access by position, plus a length that grows. This lesson builds one by hand. Not because you should, but because once you have watched the copy happen you will recognize it in your own code.

02 / Name the rule

Three entries can occupy a four-slot buffer.

Length is how many entries you can read. Capacity is how many slots the buffer has. With [12, 7, 31] in a four-slot buffer, length is 3 and capacity is 4. The spare slot is room, not a result.

Indices start at zero: index 0 holds bib 12, index 1 holds bib 7. A bib names a runner. An index names where that runner’s result sits right now. Keep those two apart. It matters later.

The invariant, the thing that must be true after every operation: the entries fill exactly index 0 through length - 1, in recorded order, and 0 ≤ length ≤ capacity. Empty means no readable index, even with slots reserved.

03 / Follow one operation

The fourth finisher fits. The fifth changes the buffer.

Bib 4 takes the last spare slot. Nothing moves. Then bib 19 arrives with nowhere to go: allocate eight slots, copy the four entries across in order, switch to the new buffer, write 19. The order survives. The storage changed underneath it.

Doubling is this example’s choice, and the whole thing runs inside one synchronous call. The animation slows it down so you can see each step. Try it lets you record your own finishers, read an index, and correct a mistake.

04 / Read the shape

The buffer provides positions. The recorder provides policy.

Basic form is the buffer alone: grow, index, remove. In the wild wraps it in RaceLog, which decides what a valid bib is and refuses a runner who has already been recorded. Notice which side each rule lives on. The array will happily store 7 twice. The recorder says no.

That split is the one to carry into your own code. The collection gives you positions. Everything about what may go in them is yours.

export type Lookup<T> = { found: true; value: T } | { found: false };
export type Step = {
	kind: 'allocate' | 'copy' | 'switch' | 'append' | 'read' | 'shift' | 'clear' | 'missing';
	from: number;
	to: number;
};

// Explicit teaching storage. This capacity is NOT JavaScript engine capacity.
export class GrowingArray<T> {
	#slots: (T | undefined)[] = new Array(4).fill(undefined);
	#length = 0;
	#steps: Step[] = [];
	#capture: boolean;
	constructor(capture = false) {
		this.#capture = capture;
	}
	get length(): number {
		return this.#length;
	}
	get capacity(): number {
		return this.#slots.length;
	}
	#record(kind: Step['kind'], from: number, to: number): void {
		if (this.#capture) this.#steps.push({ kind, from, to });
	}
	append(value: T): void {
		this.#steps = [];
		if (this.#length === this.capacity) {
			const previousCapacity = this.capacity;
			const next: (T | undefined)[] = new Array(previousCapacity * 2).fill(undefined);
			this.#record('allocate', previousCapacity, next.length);
			for (let i = 0; i < this.#length; i++) {
				next[i] = this.#slots[i];
				this.#record('copy', i, i);
			}
			this.#slots = next;
			this.#record('switch', previousCapacity, this.capacity);
		}
		this.#slots[this.#length] = value;
		this.#record('append', -1, this.#length);
		this.#length++;
	}
	get(index: number): Lookup<T> {
		this.#steps = [];
		if (!Number.isInteger(index) || index < 0 || index >= this.#length) {
			this.#record('missing', index, -1);
			return { found: false };
		}
		this.#record('read', index, index);
		return { found: true, value: this.#slots[index] as T };
	}
	remove(index: number): Lookup<T> {
		this.#steps = [];
		if (!Number.isInteger(index) || index < 0 || index >= this.#length) {
			this.#record('missing', index, -1);
			return { found: false };
		}
		const value = this.#slots[index] as T;
		for (let from = index + 1; from < this.#length; from++) {
			this.#slots[from - 1] = this.#slots[from];
			this.#record('shift', from, from - 1);
		}
		this.#length--;
		this.#slots[this.#length] = undefined;
		this.#record('clear', this.#length, -1);
		return { found: true, value };
	}
	// Independent outer arrays; arbitrary T payloads are not deep-cloned.
	values(): T[] {
		return this.#slots.slice(0, this.#length) as T[];
	}
	trace(): Step[] {
		return this.#steps.map((step) => ({ ...step }));
	}
}

type Step struct {
	Kind string `json:"kind"`
	From int    `json:"from"`
	To   int    `json:"to"`
}

// Each backing slice has a fixed length. This model chooses when to replace it.
type GrowingArray[T any] struct {
	slots   []T
	length  int
	steps   []Step
	capture bool
}

func NewGrowingArray[T any](capture bool) *GrowingArray[T] {
	return &GrowingArray[T]{slots: make([]T, 4), capture: capture}
}
func (a *GrowingArray[T]) Len() int      { return a.length }
func (a *GrowingArray[T]) Capacity() int { return len(a.slots) }
func (a *GrowingArray[T]) record(kind string, from, to int) {
	if a.capture {
		a.steps = append(a.steps, Step{kind, from, to})
	}
}
func (a *GrowingArray[T]) Append(value T) {
	a.steps = nil
	if a.length == len(a.slots) {
		previousCapacity := len(a.slots)
		next := make([]T, previousCapacity*2)
		a.record("allocate", previousCapacity, len(next))
		for i := 0; i < a.length; i++ {
			next[i] = a.slots[i]
			a.record("copy", i, i)
		}
		a.slots = next
		a.record("switch", previousCapacity, len(a.slots))
	}
	a.slots[a.length] = value
	a.record("append", -1, a.length)
	a.length++
}
func (a *GrowingArray[T]) Get(index int) (T, bool) {
	a.steps = nil
	if index < 0 || index >= a.length {
		a.record("missing", index, -1)
		var zero T
		return zero, false
	}
	a.record("read", index, index)
	return a.slots[index], true
}
func (a *GrowingArray[T]) Remove(index int) (T, bool) {
	a.steps = nil
	if index < 0 || index >= a.length {
		a.record("missing", index, -1)
		var zero T
		return zero, false
	}
	value := a.slots[index]
	for from := index + 1; from < a.length; from++ {
		a.slots[from-1] = a.slots[from]
		a.record("shift", from, from-1)
	}
	a.length--
	var zero T
	a.slots[a.length] = zero // Release the unused slot's reference, if T holds one.
	a.record("clear", a.length, -1)
	return value, true
}
func (a *GrowingArray[T]) Values() []T   { return append([]T{}, a.slots[:a.length]...) }
func (a *GrowingArray[T]) Trace() []Step { return append([]Step{}, a.steps...) }

05 / Try a decision

Removing a middle entry also changes positions.

Bib 7 was a scanning error. Reading index 1 touches one slot. Removing index 1 has a promise to keep for everything after it. Decide what should happen before the lab shows you.

06 / Follow the cost

A costly append can still be part of a cheap sequence.

Here is every operation at a glance, with n entries in the array. The rest of this section is why append gets to say amortized.

An append with a spare slot writes one entry. An append into a full buffer of n entries copies all n first, then writes one. That single append really is proportional to n. So why does push feel free?

Because the next append does not copy again. Doubling buys spare slots that pay for the copy over the arrivals that follow. Count only entry copies and writes for the first nine appends:

Over n appends the growth copies form 4 + 8 + 16 + …, and that sum stays under 2n. Add n writes and the whole sequence is under 3n. That is amortized constant-time append: a promise about the sequence, not about any single push.

These are entry moves, not milliseconds. Allocation, the recorder’s duplicate check, and drawing the results are extra. And this array keeps its capacity after a removal, trading a little space for not having to grow again.

07 / Give it a real job

Let one recorder own the result list.

In a real timing app, one recorder owns the list for a race session. The scanner calls record(bib). The results panel asks for a snapshot. A correction removes a position. The array lives inside that owner, and the validation and duplicate rule wrap around it.

If registration tells you roughly how many runners to expect, reserve that many slots up front and skip most of the growth. Guess high and you hold empty slots; guess low and you grow anyway. Our demo starts at four on purpose, so you can watch the boundary.

What the recorder leaves out is a design decision too. It has no durable storage, no scanner retry, no policy for official results, and it assumes one caller at a time. And an index you saved before a correction may now point at a different runner.

import { useState } from 'react';

export function TodoList() {
	const [todos, setTodos] = useState<string[]>([]);
	const [draft, setDraft] = useState('');

	function add() {
		// A new array: copy every todo, then append one.
		setTodos([...todos, draft]);
		setDraft('');
	}

	function remove(index: number) {
		// Everything after index shifts left by one.
		setTodos(todos.filter((_, i) => i !== index));
	}

	return (
		<>
			<input value={draft} onChange={(e) => setDraft(e.target.value)} />
			<button onClick={add}>Add</button>
			<ul>
				{todos.map((todo, index) => (
					// Keyed by position: remove one, and any state a row holds,
					// like focus or an input's text, stays with the position.
					<li key={index}>
						{todo} <button onClick={() => remove(index)}>Done</button>
					</li>
				))}
			</ul>
		</>
	);
}

08 / Make the call

Ask which positions your workload keeps touching.

Reach for a growing array when you append, iterate, and read by position. That covers most lists you will ever hold, and your language’s built-in one already does it well. Keep it.

Look elsewhere when the shape of the work changes. Size known up front: a plain array. Only ever touching the ends: a queue or deque says so more clearly. Callers holding onto particular items while the order changes around them: a linked structure. Inserting into the middle every time: cheap append is not helping you. Keeping only the latest few: a ring buffer is the honest name for that.

09 / Take the idea with you

Explain the growth without saying “dynamic array.”

“The results sit in order in one block of slots. When the block fills, I get a bigger one, copy them across, and keep appending.” That describes the mechanism. The name is what you call it in a review.

Before moving on, explain three things without the name: why length 3 can coexist with capacity 4, why the fifth append copies four entries in this model, and why removing a middle result changes the positions after it. Then open the last component you wrote with a list in it and find all three.