Arrays and memory layout
easyAn array is one contiguous block, so element i lives at base + i × size. Read a cell, then insert at the front and watch every other element shift - the asymmetry that every array-versus-list argument comes down to.
O(1) indexAverage O(n) insert/deleteWorst O(n)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How arrays and memory layout works
An array is one contiguous block of memory, and everything about it follows from that. Element i lives at base + i × size, so reading a[i] is one multiply and one add - the same two instructions whether the array holds five elements or five million. That arithmetic is the entire secret behind O(1) random access.
Contiguity cuts both ways. To insert at index 0, every existing element must first move one slot right; to delete from the front, everything shifts left to close the gap. On a five-element array that is five extra writes for one insert. Appending and popping at the end touch a single slot, so the two ends of the same array cost wildly different amounts.
The block is also why arrays are fast beyond the big-O. Neighbouring elements share cache lines, so a linear scan gets most of its reads nearly free, while a linked list with identical asymptotics chases pointers all over the heap and can run an order of magnitude slower on real hardware.
Step by step
- Five integers - 17, 42, 8, 91, 23 - occupy one block starting at address 0x1000, four bytes apart, with room for eight.
- Read a[2]: the address is 0x1000 + 2 × 4 = 0x1008. One multiply and one add fetch the 8, regardless of array length.
- Append 50: it drops into the next free slot at index 5. One write, nothing shifts - the O(1) end of the array.
- Insert 7 at the front: all six elements shift one slot right, back to front so nothing is overwritten, then 7 fills index 0 - seven writes.
- Delete from the front: removing 7 leaves a hole, and the address formula depends on contiguity, so six elements shift left to close it.
- Delete from the end: the length simply drops by one and nothing moves. The two ends of the same array are not symmetric.
Complexity
| Best case time | O(1) index |
|---|---|
| Average time | O(n) insert/delete |
| Worst case time | O(n) |
| Space | O(n) |
Reference implementation
Python
# Indexing is one multiply and one add - the size of the array
# is irrelevant, which is what "O(1) random access" means.
value = a[i] # address = base + i * itemsize
# Insertion has to make room, so everything to the right moves.
def insert_at(a, i, v):
a.append(None)
for j in range(len(a) - 2, i - 1, -1):
a[j + 1] = a[j] # shift right
a[i] = v
# Deletion has to close the gap.
def delete_at(a, i):
for j in range(i, len(a) - 1):
a[j] = a[j + 1] # shift left
a.pop()JavaScript
// O(1): one multiply, one add. Array size does not matter.
const value = a[i];
// O(n): everything right of i shifts up one slot.
function insertAt(a, i, v) {
for (let j = a.length; j > i; j--) a[j] = a[j - 1];
a[i] = v;
}
// O(n): everything right of i shifts down one slot.
function deleteAt(a, i) {
for (let j = i; j < a.length - 1; j++) a[j] = a[j + 1];
a.length--;
}Worth noticing
Random access is O(1) because of arithmetic, not magic
The address of element i is base + i × size. That is one multiply and one add regardless of whether the array holds ten items or ten million - which is the single most useful property arrays have.
Insert at the front is the expensive one
Compare 'insert at 0' with 'append': one shifts every element, the other writes a single slot. Every discussion of arrays versus linked lists comes down to this asymmetry.
Contiguity is also why arrays are fast in practice
Neighbouring elements share cache lines, so a linear scan gets most of its reads for free. A linked list with the same asymptotic complexity can be an order of magnitude slower on real hardware for exactly this reason.
Common pitfalls
- Removing or inserting at the front inside a loop. Each call shifts the whole array, so a linear-looking loop quietly becomes O(n²) - the classic cause of code that chokes at scale.
- Assuming high-level languages dodge the shift. Python's list.insert(0, v) and JavaScript's unshift still move every element - the syntax is one call, the cost is still n writes.
- Shifting in the wrong direction. Making room for a front insert must copy back to front; walking front to back overwrites each element with its neighbour before it has been saved.
- Picking a linked list purely from the big-O table. The list wins the insert column on paper and loses linear scans by 10× in practice, because pointer-chasing defeats the cache.
Where it is used
- The backing store of nearly everything else: strings, stacks, heaps, hash table buckets and dynamic arrays are all this block.
- Ring buffers and deques exist specifically to dodge the front-shift cost this visualizer shows.
- Columnar databases and NumPy lay values contiguously so scans stream through the cache - the same property, at scale.
- Interview staples: in-place rotation, two-pointer partitioning and shift-based deletion all assume you know what a[i] costs.
Frequently asked questions
What is the time complexity of array operations?
Indexing is O(1) in the best case - the address is computed as base + i × size, one multiply and one add. Insert and delete are O(n) on average and O(n) in the worst case, because up to n elements shift to keep the block contiguous. Space is O(n) for the block itself.
Why is array indexing O(1)?
Because every element is the same size and they sit side by side, element i is exactly i × size bytes past the base address. Computing that takes the same two instructions for index 3 or index 3,000,000 - no search, no traversal, just arithmetic.
When should I use an array instead of a linked list?
Default to the array. It wins random access - O(1) against O(n) - and wins scans on cache behaviour. A linked list pays off only when you splice at already-known nodes far from the ends and never need indexing; an LRU cache is the textbook case.
Is appending to an array O(1)?
While spare capacity exists, yes - one write into the next free slot. This fixed block simply stops at capacity 8; growable arrays instead allocate a bigger block and copy everything across, which is the amortised story the dynamic array visualizer tells.