How arrays work in memory

Contiguous slots, O(1) indexing, and why inserting in the middle costs a shift.

Lesson 11 of 75 · Beginner 2 min read

An array is a contiguous block of memory holding equally sized slots. That one fact explains every cost it has.

Because the slots are equal and adjacent, the address of element i is base + i × size. No searching, no pointer chasing — one multiplication and one add. That is why indexing is O(1) and why it stays O(1) whether the array holds ten items or ten million.

The costs that follow

Operation	Cost	Why
Read or write `arr[i]`	O(1)	Address arithmetic
Append (amortised)	O(1)	Write past the end, resize occasionally
Insert or delete at the front	O(n)	Every later element shifts one slot
Insert or delete in the middle	O(n)	Same shift, on average half the array
Search unsorted	O(n)	No structure to exploit

const items = ['b', 'c', 'd'];
items.unshift('a');   // O(n): every element moves right
items.shift();        // O(n): every element moves left
items.push('e');      // O(1) amortised
items.pop();          // O(1)

If you find yourself calling shift() in a loop to drain a queue, you have written an O(n²) loop. That is what a real queue structure exists to fix.

Cache locality: the invisible advantage

Contiguous memory means a walk through an array reads whole cache lines, and the CPU prefetches the next one. A linked list of the same length scatters its nodes and misses the cache constantly. On paper both traversals are O(n); in practice the array can be several times faster.

This is why "an array is fine" is usually the right default, and why balanced trees and linked lists need a specific reason.

JavaScript's arrays are not quite arrays

Array in JavaScript is an object with integer-like keys. Engines optimise it into a real contiguous array while it stays "packed" — dense, single-type, no holes. Break that and the engine falls back to a dictionary:

const dense = [1, 2, 3];
dense[100] = 4;       // sparse now: the fast path is gone

Keep arrays dense and typed consistently. Array.from({ length: n }, () => 0) beats new Array(n) followed by scattered writes.