Some 20 years ago, when I was a kernel developer with high performance requirements, my favorite data structure was a linked list of smallish arrays. Each array was small enough to be cheap to completely rewrite on insert/delete, if you needed to e.g. preserve insertion order; most of the time, it was enough to preserve order only across the linked list, treat each array like a hash table slot, or sort at consumption time.

You can also force-align (with padding if necessary) your structures to be along whatever boundaries make sense for your processor's cache lines.

Ensuring an oft-loaded structure always fits inside a single cache line (instead of splaying across ~1.9 cache lines on average) is good not only for fitting lots of those structures into your L1 but for not blowing out cache bandwidth (read _and_ write, if you're modifying them).

Expanding on this: usually linked lists allocate each element with a separate malloc() on the heap, so they end up all over the place in memory.

You could, in principle, allocate your linked list out of contiguous memory in such a way that sequentially reading the list doesn't cause so many page accesses. That would itself be a complicated data structure to maintain, so simply using a linear array is often the right tradeoff.

Forgive me but are linked lists common in other languages?