Algorithms and Data Structures · Middle · Question 70 of 75
Why are arrays usually faster to iterate than linked lists even though both are O(n)?
- ✓Correct answer: Array items sit together in memory, which suits the CPU cache
- 2Engines iterate arrays in parallel on several cores
- 3Linked lists have to check bounds on every single step
Explanation
Big O hides constants. Contiguous memory is prefetched in cache lines; list nodes scattered around the heap cause cache misses. That's why arrays win in practice for most workloads.