Arrays vs linked lists (and why arrays usually win)

Array or linked list — and why does the textbook answer usually lose?

The textbook says a linked list wins on insertion because it is O(1) once you hold the node, while an array is O(n). Real hardware disagrees, because the array is contiguous: the CPU fetches a whole cache line at a time and prefetches the next one, so scanning it is nearly free, while every node in a linked list is a separate pointer chase into unpredictable memory. Shifting a few thousand contiguous bytes routinely beats following a few hundred pointers.

The honest exception: a linked list wins when you are splicing large elements around, or already hold a pointer to the node, and never traverse to find it.

When do you actually need a linked list?

When you need stable references to elements while the container changes around them, or O(1) splicing of whole ranges. An LRU cache is the classic case — a hash map holds pointers straight to nodes in a doubly-linked list, so touching a key moves it to the front without touching anything else. That is a structural need, not a performance one.