That's true. And there is seriously optimized software out there using linked lists (e.g. in the Linux kernel). However, with bigger data in my experience a ve

That's true. And there is seriously optimized software out there using linked lists (e.g. in the Linux kernel). However, with bigger data in my experience a very good solution is often to have a vector of pointers to the actual data. This loses some locality of course, but during traversal the fact that you don't have dependencies between iterations can still be a win.