I have found this talk by Bjarne Stroustrup about inefficiency of linked lists. The arguments he presents are:

• Linked lists has asymptotic insertion time of $O(1)$, however dynamic arrays $O(n)$. He assumes that you rarely insert into a priori known location and thus you first need to perform $O(n)$ search in the linked list. Asymptotically linked lists are thus equivalent to dynamic arrays and in reality they are inferior because of higher memory indirection.
• Linked lists are less memory-efficient as they have to store a pair of pointers with each item.

Is it measurable?

Yes, it is. I wrote a simple program to compare the behavior of insertion to the std::vector<int> and std::list<int>.

The results of the mentioned program are bellow.

Appending to vector and to linked list seems to be comparable as the size of the container increases.

Copying the whole structures seems to be ~6 times faster for vector.

This is the case described by Stroustrup where vectors are faster even though inserted item has to shift all following items. Vector is consistently faster.

Moral of the story

Obviously, I’m not the only one who was influenced by this video. I was trying to list some arguments when/why linked lists are preferable.

• Structures that are accessed directly via pointer (e.g. structures of OS kernel), list operations are then desired $O(1)$.