Deep Dive: Array Internals & Memory Layout

Array Internals & Memory Layout

WHAT YOU'LL LEARN

• Arrays store elements in contiguous memory blocks — each element sits right next to the previous one

• Random access is O(1) because the address of arr[i] is just baseAddress + i * elementSize — a single arithmetic operation

• Insertion/deletion at arbitrary positions is O(n) because elements must be shifted to maintain contiguity

• JavaScript arrays are actually hash maps under the hood for sparse arrays, but V8 optimizes dense arrays to use contiguous backing stores*

Why it matters: Understanding the memory model explains WHY array operations have the complexities they do, rather than memorizing a table. It also informs when to choose arrays vs. linked lists or hash maps.

Contiguous Memory & O(1) Access

In a true array, elements are packed sequentially in memory. To read arr[i], the CPU computes baseAddress + i * sizeof(element) and jumps directly there — no traversal needed. This is why arrays have O(1) random access while linked lists have O(n). In JavaScript, V8 uses 'SMI' (Small Integer) arrays and 'PACKED_DOUBLE' arrays that behave like true contiguous arrays for performance.*

// O(1) — direct index access const arr = [10, 20, 30, 40, 50]; console.log(arr[3]); // 40 — computed in constant time

// O(1) — direct index access const arr = [10, 20, 30, 40, 50]; console.log(arr[3]); // 40 — computed in constant time

// O(n) — insertion shifts all elements after index arr.splice(1, 0, 15); // Insert 15 at index 1 // [10, 15, 20, 30, 40, 50] // Elements 20, 30, 40, 50 all shifted right

// O(1) — push to end (amortized) arr.push(60); // No shifting, just append

// O(n) — unshift to front arr.unshift(5); // All elements shift right`

Enter fullscreen mode

Exit fullscreen mode

Cache Locality & Performance

Contiguous memory means arrays are cache-friendly. When the CPU loads arr[0], the cache line typically pulls in arr[1] through arr[7] as well. Sequential iteration exploits this prefetching, making arrays dramatically faster than linked lists for traversal even though both are O(n). This is why algorithms that iterate arrays sequentially (like prefix sum) perform better in practice than their Big-O alone suggests.

// Cache-friendly: sequential access pattern function sum(arr) {  let total = 0;  for (let i = 0; i < arr.length; i++) {  total += arr[i]; // Next element is already in CPU cache  }  return total; }

// Cache-friendly: sequential access pattern function sum(arr) {  let total = 0;  for (let i = 0; i < arr.length; i++) {  total += arr[i]; // Next element is already in CPU cache  }  return total; }

// Cache-unfriendly: random access pattern function randomSum(arr, indices) { let total = 0; for (const i of indices) { total += arr[i]; // Likely cache miss each time } return total; }`

Enter fullscreen mode

Exit fullscreen mode

Dynamic Array Resizing (Amortized O(1) Push)

JavaScript arrays (and C++ vectors, Java ArrayLists) use dynamic resizing. When the backing store is full, a new array of 2x size is allocated and elements are copied over. The copy is O(n), but it happens exponentially less often. Amortized over n pushes, each push costs O(1). This is why push() is O(1) amortized but splice(0, 0, x) is always O(n).

// Simulating dynamic array resizing class DynamicArray {  constructor() {  this.data = new Array(4); // initial capacity  this.size = 0;  this.capacity = 4;  }

// Simulating dynamic array resizing class DynamicArray {  constructor() {  this.data = new Array(4); // initial capacity  this.size = 0;  this.capacity = 4;  }

push(val) { if (this.size === this.capacity) { this.capacity = 2; // double capacity const newData = new Array(this.capacity); for (let i = 0; i < this.size; i++) { newData[i] = this.data[i]; // O(n) copy — rare } this.data = newData; } this.data[this.size] = val; // O(1) this.size++; }

get(i) { return this.data[i]; // O(1) random access } }`

Enter fullscreen mode

Exit fullscreen mode

Choosing the right data structure based on access pattern

Tricky Parts

JavaScript arrays aren't always contiguous

If you create a sparse array like const a = []; a[1000] = 1;, V8 switches to dictionary mode (hash map). Dense arrays with sequential indices get the fast contiguous path. Avoid holes to keep arrays optimized.

splice() vs pop() — big performance difference

arr.splice(0, 1) is O(n) because every element shifts. arr.pop() is O(1). For queue behavior (FIFO), don't use shift() on large arrays — use a proper queue or circular buffer.

Amortized O(1) doesn't mean every push is O(1)

When the backing store doubles, that single push is O(n). In real-time systems, this spike matters. For most application code, amortized O(1) is fine.

Tips & Best Practices

• Pre-allocate with new Array(n).fill(0) when you know the size upfront. Avoids repeated resizing during initialization. [Performance]

• Use TypedArrays (Float64Array, Int32Array) when you need true contiguous memory in JavaScript — they map directly to memory buffers. [Advanced]

• When in doubt about array vs. linked list: arrays win for iteration and random access, linked lists win for frequent mid-list insertions with known references. [Trade-offs]

Test Your Knowledge

Q1: Why is accessing arr[500] the same speed as arr[0]?

• The CPU computes baseAddress + 500 * elementSize — one arithmetic operation

• JavaScript caches all indices at creation time

• The array is sorted so binary search finds it in O(log n)

• The garbage collector optimizes frequent accesses*

Q2: What is the time complexity of arr.splice(0, 0, 'x') on an array of n elements?

• O(1)

• O(log n)

• O(n)

• O(n²)

Q3: What does this log?

const a = [1, 2, 3]; a.push(4); // A a.unshift(0); // B console.log(a.length, a[0], a[4]);

const a = [1, 2, 3]; a.push(4); // A a.unshift(0); // B console.log(a.length, a[0], a[4]);

Enter fullscreen mode

Exit fullscreen mode

Q4: Why are arrays faster than linked lists for sequential iteration, even though both are O(n)?

• Cache locality — contiguous memory means CPU prefetching loads subsequent elements automatically

• Arrays have shorter pointers

• Linked lists require sorting before iteration

• Arrays use less memory per element

Q5: Why is push() O(1) amortized but not O(1) worst-case?

• Occasionally the backing store must double in size, copying all elements — O(n) for that single push

• push() sorts the array after insertion

• The garbage collector pauses on every push

• V8 recalculates hash codes for the array

Answers

💡 Reveal Answer for Q1

Answer: The CPU computes baseAddress + 500 * elementSize — one arithmetic operation*

Contiguous memory layout means any index is reachable via a single address calculation: base + offset. No traversal needed.

💡 Reveal Answer for Q2

Answer: O(n)

Inserting at index 0 requires shifting all n elements one position to the right — O(n).

💡 Reveal Answer for Q3

Answer: 5 0 4

After push(4): [1,2,3,4]. After unshift(0): [0,1,2,3,4]. Length is 5, a[0] is 0, a[4] is 4.

💡 Reveal Answer for Q4

Answer: Cache locality — contiguous memory means CPU prefetching loads subsequent elements automatically

Contiguous storage means iterating arr[0], arr[1], arr[2]... hits the CPU cache. Linked list nodes are scattered in memory, causing cache misses.

💡 Reveal Answer for Q5

Answer: Occasionally the backing store must double in size, copying all elements — O(n) for that single push

Dynamic arrays resize (usually 2x) when full. The resize copies n elements, but this happens after n pushes, so amortized cost per push is O(1).

Conclusion

Mental Model: An array is a numbered row of lockers. Walking to any locker number is instant (O(1) access), but inserting a new locker in the middle means physically moving every subsequent locker down by one (O(n) insert).