What's the Difference Between an Array and a Linked List?
Question: What is the difference between an array and a linked list?
Core Answer
An array stores elements in a contiguous block of memory. Because the elements are adjacent, you can compute the address of any element using base_address + index × element_size — that is why random access is O(1).
A linked list stores each element in a separate node that contains the value plus a pointer (reference) to the next node. The nodes are scattered across the heap. To reach element i, you must follow i pointers starting from the head — so random access is O(n).
The Trade-offs
| Operation | Array | Linked List |
|---|---|---|
| Random access (index i) | O(1) | O(n) |
| Insert at head | O(n) — shift all | O(1) — just change 2 pointers |
| Insert at tail | O(1) amortized | O(n) — must traverse to tail |
| Memory overhead | None, but may waste space (capacity > length) | Extra 8 bytes per node (64-bit pointer) |
| Cache locality | Excellent (contiguous) | Poor (scattered nodes) |
The Cache Angle
This is where interviewers often dig deeper. Even though both structures are "O(n)" to traverse from a Big-O perspective, an array will almost always be faster in practice. Here is why:
The CPU does not read memory byte by byte. It reads in cache lines — typically 64 bytes at a time. When you access array[0], the CPU loads array[0] through array[15] (for 4-byte integers) into L1 cache. The next 15 accesses hit cache with essentially zero latency.
A linked list node is allocated independently. Node 1 might be at address 0x1000, node 2 at 0x3F80, node 3 at 0x7A10. Each pointer dereference jumps to a different memory region, and each is likely a cache miss — a stall of hundreds of cycles waiting for main memory.