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(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
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-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;
}
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;
}
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
}
}
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]);
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).

Top comments (0)