Arrays

The 10-second versionCopy Anchor Link

An array is the simplest data structure there is: a contiguous block of equal-sized slots, numbered from zero. Because the slots are the same size and sit right next to each other, the computer can compute the address of slot i with one multiplication and one addition — so reading or writing any index costs O(1), no matter how big the array is. That single property is why arrays are the substrate almost everything else is built on.

Why this existedCopy Anchor Link

In the earliest computers, there were no "variables" you could name and index. You had registers, a pile of memory, and go-to. If you wanted to store 1000 sensor readings, you had two bad options:

1. One variable per reading. reading1, reading2, … reading1000. Unmaintainable, and impossible when you don't know the count ahead of time.
2. Hand-rolled address math. Compute base + i × size yourself, everywhere. Correct, but error-prone and repeated in every program.

What people wanted was a name that meant "the i-th thing" — a single noun that the computer could resolve to a real memory address on demand.

• 1957 — FORTRAN, from a team at IBM led by John Backus, ships the first widely used language where you can write A(I) and have the compiler do the address arithmetic for you. That's the moment "array" became a language feature instead of a discipline you had to practice by hand.
• The idea it codified — elements of the same type, laid out back-to-back, addressed by position — is so fundamental that essentially every language since has copied it: C, Pascal, Java, JavaScript's typed arrays, Python's list (as an implementation detail), Rust's Vec and slices, Go slices, and on and on.

Why it mattered: it turned "access the i-th item" from a technique into a guarantee. And a guarantee is what lets you build higher things — stacks, heaps, hash tables, free matrices — on top.

Inside the inventor's headCopy Anchor Link

The clever bit isn't storing values. It's the realization that if all the slots are the same size and adjacent, then index i is pure arithmetic. Nobody has to search. Nobody has to walk a chain of pointers. You just compute the address.

Walk through the reasoning her (the anonymous every-engineer) thought process:

Then the naive first attempt throws a wrench in the works. What if the slots aren't all the same size — say, mixed strings and numbers? Now the arithmetic dies, because slot i doesn't start at a predictable offset. You'd have to scan. That observation is exactly why arrays demand homogeneous elements, and why hash tables and linked lists had to be invented later for the heterogeneous, elastic cases.

Another failed intuition: "I'll grow the array by 1 whenever I need to." This works, but watch what it costs — every append copies everything. We'll fix that properly in Dynamic Arrays; for now, the punchline is that a fixed array is what makes the O(1) access possible in the first place.

The final approachCopy Anchor Link

The memory pictureCopy Anchor Link

An array of four 32-bit ints, holding 7, 3, 9, 1, starting at address 1000:

The address formula is the whole trick, and it generalizes:

address(i) = base_address + i × sizeof(element)

Cost tableCopy Anchor Link

The asymmetry is the lesson: arrays are unbeatable at random access and bad at growth in the middle. Everything else in this track exists to patch that weakness.

It in codeCopy Anchor Link

const a = [7, 3, 9, 1];          // a plain, growable arrayconsole.log(a[0]);               // 7  — O(1)console.log(a[3]);               // 1  — O(1), same costfor (const x of a) console.log(x); // O(n)

Note the honest difference: in C an array is a raw contiguous block you must size yourself; in JavaScript [] is really a dynamic array under the hood (next page); in Rust [T; N] is fixed-size while Vec<T> is the growable cousin. Same mental model, different guarantees.

A worked trace: why insertion costs O(n)Copy Anchor Link

Insert 5 at index 1 of [7, 3, 9, 1]:

In the worst case you shift every element — that's the O(n). Nothing about the address math can save you here, because contiguity must be preserved.

Where you meet it todayCopy Anchor Link

• Images. A bitmap is a 2D-ish array of pixels. image[y][x] = color is why photo editors can touch any pixel instantly.
• Lookup tables. A precomputed sin[]/cos[] table trades memory for speed — classic in C and in game engines.
• Strings are arrays. In C, a string is literally a char array ending in \0; that's why indexing a string is O(1) but concatenating isn't.
• Columnar databases. ClickHouse, Parquet, and friends store each column as one big array so scans are cache-friendly — arrays again, just chosen deliberately.

const SQUARES = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81];const squareOf = (n) => SQUARES[n];          // O(1), no multiply

RecapCopy Anchor Link

• An array is contiguous, fixed-size slots, addressed by base + i × sizeof(element).
• That formula is why random access is O(1) and why the elements must be homogeneous.
• Access is free; growth in the middle is expensive (O(n) of shifting).
• Arrays are the foundation of images, strings, tables, and — next — dynamic arrays.

Next up: Dynamic Arrays & Amortized Growth — how we keep that O(1) access while letting the thing grow.