The article( and its referenced article) recommends against using linked lists because they are inefficient on modern processors (due to cache misses).
However, there is a better solution than throwing away a powerful and expressive data structure. Rather than linking individual data elements, instead link blocks of consecutive elements.
This hybrid approach takes full advantage of cache locality and it minimizes the memory overhead of storing both the links and the data.
However, there is a better solution than throwing away a powerful and expressive data structure. Rather than linking individual data elements, instead link blocks of consecutive elements.
This hybrid approach takes full advantage of cache locality and it minimizes the memory overhead of storing both the links and the data.
This is the approach used in Python's implementation of deques: http://hg.python.org/cpython/file/85c04fdaa404/Modules/_coll...