heyrian.dev
← Data structures & algorithms
Sequences Indexed, ordered, resizable

Dynamic array

Make room for the next finisher.

Three runners cross the line; more are coming, and the results must stay in order. You have stored that list in an array already. The interesting part is how one more result fits when the reserved slots run out.

TypeScriptGoRust The same growing array in each language.

Definition

A dynamic array stores a sequence in one contiguous block of slots, keeps a count of the slots in use, and, when the block is full, moves the entries into a larger block, usually twice the size.

After Cormen et al., Introduction to Algorithms, §17.4

01Keep the order, leave the end open

Results arrive one by one. How many is unknown.

Bibs 12, 7 and 31 cross the line in that order. The results panel must show them in that order and let you jump straight to the second result. You do not know how many more runners are coming.

A dynamic array keeps a sequence in one block of numbered slots, and makes the block larger when it runs out. Reading position 2 is one step, whatever the length. Growing is the part with a cost, and this lesson makes it visible.

With 12, 7 and 31 in four slots, the length is 3 and the capacity is 4. Slots 0, 1 and 2 hold results; slot 3 is room for the next. The rule that never breaks: exactly the slots from 0 to length − 1 hold values, in recorded order, and the length never exceeds the capacity.

02Read the model

A buffer, a length, and a copy when it fills.

TypeScript arrays, Go slices and Rust Vecs already do this. To see the growth, this lesson spells out a small model: a buffer of slots, a length, and a count of moves, every entry copied, shifted or written. In real code, use your language’s own.

Start with four empty slots. Appending 12, 7, 31 and 4 writes each into the next free slot, one move each, and the length climbs 1, 2, 3, 4. Now the length equals the capacity. Here is append, from the program below:

finishers.ts
append(value: number): void {
  if (this.length === this.capacity) {
    // Full: copy every entry into a buffer twice the size, then use it.
    const oldSlots = this.slots;
    const newSlots: (number | undefined)[] = new Array(oldSlots.length * 2).fill(undefined);
    for (let i = 0; i < this.length; i++) {
      newSlots[i] = oldSlots[i];
      this.moves++;
    }
    this.slots = newSlots;
  }
  this.slots[this.length] = value;
  this.length++;
  this.moves++;
}

append writes into the next free slot. When there is none, it copies every result into a buffer twice the size, switches to it, and then writes. remove keeps the order by moving every later result one place earlier, then clears the last slot.

The whole program the lab runsThe model, then five finishers and one correction
finishers.ts
// A teaching model of a growing array. In real code, use your language's own:
// a TypeScript array, a Go slice, a Rust Vec.
class GrowingArray {
  slots: (number | undefined)[] = new Array(4).fill(undefined);
  length = 0;
  /** Entries copied, shifted or written: the work this lesson counts. */
  moves = 0;

  get capacity(): number {
    return this.slots.length;
  }

  append(value: number): void {
    if (this.length === this.capacity) {
      // Full: copy every entry into a buffer twice the size, then use it.
      const oldSlots = this.slots;
      const newSlots: (number | undefined)[] = new Array(oldSlots.length * 2).fill(undefined);
      for (let i = 0; i < this.length; i++) {
        newSlots[i] = oldSlots[i];
        this.moves++;
      }
      this.slots = newSlots;
    }
    this.slots[this.length] = value;
    this.length++;
    this.moves++;
  }

  get(index: number): number | undefined {
    return index >= 0 && index < this.length ? this.slots[index] : undefined;
  }

  remove(index: number): number | undefined {
    if (index < 0 || index >= this.length) return undefined;
    const removed = this.slots[index];
    // Keep the order: move every later entry one place earlier.
    for (let i = index + 1; i < this.length; i++) {
      this.slots[i - 1] = this.slots[i];
      this.moves++;
    }
    this.length--;
    this.slots[this.length] = undefined;
    return removed;
  }

  values(): number[] {
    return this.slots.slice(0, this.length) as number[];
  }
}

const results = new GrowingArray();
for (const bib of [12, 7, 31, 4]) results.append(bib);

const beforeFifth = results.moves;
results.append(19);
const fifthAppend = results.moves - beforeFifth;
console.log(`five: ${results.values().join(", ")} | capacity ${results.capacity} | fifth append ${fifthAppend} moves`);

const beforeRemove = results.moves;
const removed = results.remove(1);
const removal = results.moves - beforeRemove;
console.log(`removed ${removed}: ${results.values().join(", ")} | capacity ${results.capacity} | ${removal} moves`);
console.log(`index 1 now: ${results.get(1)}`);
Reading the TypeScriptClasses, getters and fill

new Array(4).fill(undefined) makes four real slots; without fill they would be holes, which length counts and map and forEach skip. get capacity() is a getter: it reads like a field and is computed from the buffer. The model’s slot count is teaching state; a JavaScript engine decides its own capacity and does not show it.

What a production results log addsAny value type, absence, and admission rules

The same growing array, generic over its values, with reads that tell a missing index apart from a stored empty value, and an optional trace of every step. The results log on top owns what the array should not: bibs are whole numbers from 1 to 999, and a bib already recorded is refused. That rule lives in a set beside the array; it is not something arrays do.

finishers.ts
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 }));
	}
}

export type Admission = 'recorded' | 'invalid-bib' | 'duplicate-bib';
export class RaceLog {
	#rows: GrowingArray<number>;
	#bibs = new Set<number>();
	#steps: Step[] = [];
	constructor(captureTrace = false) {
		this.#rows = new GrowingArray(captureTrace);
	}
	get length(): number {
		return this.#rows.length;
	}
	get capacity(): number {
		return this.#rows.capacity;
	}
	record(bib: number): Admission {
		this.#steps = [];
		if (!Number.isInteger(bib) || bib < 1 || bib > 999) return 'invalid-bib';
		if (this.#bibs.has(bib)) return 'duplicate-bib';
		this.#rows.append(bib);
		this.#bibs.add(bib);
		this.#steps = this.#rows.trace();
		return 'recorded';
	}
	read(index: number): number | null {
		const result = this.#rows.get(index);
		this.#steps = this.#rows.trace();
		return result.found ? result.value : null;
	}
	remove(index: number): number | null {
		const result = this.#rows.remove(index);
		this.#steps = this.#rows.trace();
		if (!result.found) return null;
		this.#bibs.delete(result.value);
		return result.value;
	}
	values(): number[] {
		return this.#rows.values();
	}
	trace(): Step[] {
		return this.#steps.map((step) => ({ ...step }));
	}
}

03Predict the fifth result

The fourth result fits. What does the fifth cost?

Experiment

Five finishers, one removal

Four results fill the four slots. The fifth, bib 19, arrives. How many moves does that one append cost?
Step through it in the lab

04Meet it in your language

Your language’s array grows the same way, and it shows.

A JavaScript array grows like this lesson’s model, but hides the buffer: you never see its capacity, and push stays cheap the way the model’s append does. The trap is the code that copies the whole array to add one entry, which immutable updates do on purpose.

A reducer adds each finisher with results = [...results, bib]. Building 10,000 results this way copies about how many entries in total?
spread.ts
// The bug: a spread per append builds a new array and copies every result so
// far into it, so building n results copies about n²/2 entries.
let results: number[] = [];
let copied = 0;
for (let bib = 1; bib <= 10_000; bib++) {
  copied += results.length; // the spread below copies this many
  results = [...results, bib];
}
console.log(results.length, copied); // 10000 49995000

// The fix: push into a local array, which grows by a factor like the model,
// then copy once if the caller needs a new array (one setState, one spread).
const built: number[] = [];
for (let bib = 1; bib <= 10_000; bib++) built.push(bib);
const next = [...built]; // one copy of 10,000 entries
console.log(next.length); // 10000

Build with push into a local array and copy once at the end (one setState, one spread): one spread per update is O(n), one per item is O(n²). Draining with shift() or splice(0, 1) in a loop has the same shape, because each call moves every remaining entry one place; keep an index instead. And build a sized array with Array.from({ length: n }, …), not new Array(n), which is all holes: writing past the end leaves holes too, and length counts them.

05Count the cost

One expensive append can belong to a cheap sequence.

Here n is the number of results. These are worst-case bounds for one operation on this model, except append’s amortized bound, which describes a sequence of appends.

The growing array’s costs
OperationTimeExtra spaceWhy
Read index iO(1)O(1)One slot at a known offset from the start of the buffer.
AppendO(1) amortized; O(n) worstO(1); O(n) during growthA full buffer copies n entries into one twice the size; both buffers exist while it copies.
Remove index i, keeping orderO(n − i)O(1)Every entry after i moves one place earlier. Removing the last entry moves nothing.
Insert at index iO(n − i), plus O(n) if it growsO(1); O(n) during growthEvery entry from i moves one place later; the lab builds it.
Find a valueO(n)O(1)Positions are indexed; values are not. A set or map indexes values.
Memory held—O(peak n)This model never shrinks; halving at a quarter full gives memory back (below).

An append that finds the buffer full copies n results and writes one: O(n) for that append. But doubling makes those appends rare. Copies happen at lengths 4, 8, 16 and so on, and each copy is as big as all the ones before it put together, plus four: 4 + 8 + 16 + … stays under 2n. With the n writes, any n appends cost fewer than 3n moves in all. That bound holds for every sequence of appends, not on average over lucky ones: each append is O(1) amortized, not O(1) every time.

The first nine appends, doubling from four slots
AppendsCopiesWrites
1–404
541
6–803
981
Total after 9129
The doubling is what makes it work. Change the model to grow by four more slots each time instead. After 1,000 appends from four slots, about how many entries has it copied?

During growth both buffers exist, so that one append needs O(n) extra memory, and this model never shrinks: it holds memory for its largest size. Removing keeps order by shifting, so its cost depends on how many results come after the one removed, not on the result.

Giving memory back is the mirror of growth, with one trap. Shrink to fit as soon as half the slots are empty, and a list that hovers at that size thrashes: the next append finds the buffer full and copies everything up again, the next removal copies everything down. The safe rule halves the buffer only when it is a quarter full. After a halving it is half full, with room on both sides: with n results left, n more appends or n/2 more removals must come before the next copy, enough to pay for it, so both stay O(1) amortized. A JavaScript engine decides for itself whether an array gives memory back.

06Choose another structure

Use it when order and positions earn their keep.

A dynamic array is usually the simplest answer when you append, scan and read by position. A fixed-size array is simpler still when the size is known and cannot change. Choose something else when the work is not at the end:

  • Stack: work at one end only. A dynamic array is a fine stack.
  • Order does not matter: remove index i by moving the last entry into its slot (a swap-remove), O(1) with no shift.
  • Queue or deque, or a ring buffer: items leave from the front. An array shifts everything on every removal from the front; these keep a moving start instead.
  • Linked list: callers hold a particular item and insert or move around it, so nothing should shift. You give up reading by position.
  • Hash map or hash set: you look items up by value, not position. The results log uses a set beside its array for exactly that.

Two things the cost table hides. Scanning an array is fast beyond its O(n): the slots sit next to each other, so the processor’s cache loads them in runs, while a linked structure follows a pointer to a new place in memory for every item. And amortized O(1) still includes one O(n) append now and then: if a single slow step matters (a frame budget, a latency target), reserve the size up front, or use a structure that grows in pieces.

07Make the call

Is this array doing the right work?

A dashboard keeps the latest 1,000 temperature readings. Each new reading is appended and the oldest is removed with remove(0). What do you say in review?
An import reads 50,000 rows from a file whose row count is in its header, and appends each row to your language’s array. What is its cost?

Before you open the answer below, say it in your own words: what do length and capacity each mean, why is append O(1) amortized but sometimes O(n), and when is an array the wrong structure?

One way to say itTwo numbers, one occasional copy, and where it fails

A dynamic array keeps its values in one block of slots: the length counts the slots in use, from the start, in order; the capacity counts the slots it has. Reading a position is one step. Appending writes into the next free slot, and when there is none it copies everything into a block twice the size. That copy is O(n), but doubling makes it rare enough that appends cost O(1) amortized: under 3n moves for n appends. Removing or inserting keeps order by shifting everything after the position, so work at the front is expensive. When items leave from the front, use a queue or ring buffer; when callers hold an item and move things around it, a linked list; when you look items up by value, a hash map or set.

Practice in the lab

Subtitlers work on a caption track: the lesson’s growing array, holding a film’s caption cues in order. Its buffer, from the checker’s plumbing, counts every cue written into a slot (a copy, a shift or a new cue), so the checker can tell a correct operation that is too slow from one that scales, however the code is written. Each level starts from the previous level’s finished code, so you can begin at any of them.