Theory vs Practice -- Linked List and Array

When I was a student, in algorithm course about data structures, we were comparing arrays and linked lists. Arrays are faster than linked lists on random access (O(1) vs O(n)). However, listed lists are faster than arrays for random insertion/deletion operations (O(1) vs O(n)).

In reality, when we consider the L1 and L2 cache in a computer system, the above is not always true. Recently, I found a good page comparing the performance of C++ std::vector (dynamic array), std::list (linked list) and std::deque. When the size of an element is small, vectors and deques perform better than lists. It's because the spatial locality. In arrays, elements are packed next to each others in memory, but in lists, elements are located randomly and linked by pointers. Therefore, when iterating the elements in lists, it will have much higher chance of cache missed. In other words, lists can't get the benefit from cache.