What is the difference between an array and a linked list, and when would you choose each?
An array stores items contiguously, so indexing is O(1) but inserting in the middle is O(n). A linked list stores nodes connected by pointers, so insertion at a known node is O(1) but reaching the kth item is O(n).
Explain it simply
An array is a row of numbered lockers: to open locker 57 you walk straight to it. Adding a new locker in the middle means shifting every locker after it.
A linked list is a treasure hunt. Each clue (node) tells you where the next one is. You can slot a new clue into the chain by changing just two pointers, but to reach clue 57 you must follow the first 56.
| Operation | Array | Linked list |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert/delete at start | O(n) | O(1) |
| Insert/delete after a known node | O(n) | O(1) |
| Memory | compact, cache-friendly | extra pointer per node |
In practice arrays win most of the time because contiguous memory is fast on modern CPUs.
Example
array: [10][20][30][40] index 2 -> jump straight to 30
linked list: 10 -> 20 -> 30 -> 40 reach 30 -> follow two pointersWhat to say in the interview
"Arrays give O(1) random access but costly middle inserts; linked lists give O(1) inserts once you hold the node but O(n) lookup and extra memory for pointers. I pick an array when I read by index a lot and a linked list when I insert and delete at the ends or at known nodes often."
Common mistakes
- Saying linked list insertion is always O(1): finding the position is still O(n).
- Ignoring cache behaviour, which often makes arrays faster than their big-O suggests.