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.
Linked lists apologia
Academic use when teaching students principles of dynamic data structures
and pointers.
Conservative memory footprint. This applies to the case when we are storing
large structures where size of pointers is negligible to the size of the
structures.
Large structures where copying whole structure would be bothersome (as
that’s what dynamic arrays had to do from time to time).
Structures that are accessed directly via pointer (e.g. structures of OS
kernel), list operations are then desired $O(1)$.
Concurrent structures. Not sure about this but linked lists are more
suitable for RCU.