[Retric]

Cache means inserts into arrays are often faster than linked lists. Remember RAM is really really big and slow.

[PeterisP]

Not if the list is allocated within a slab, as described in the article. Imagine list elements allocated continuously (as in an array) but the ordering is decided by the pointers within each node, instead of assuming a fixed order. All the elements still are in the same cache line.

[Retric]

Linked lists take more memory than arrays, so even in your example it's not as obvious as your making it out to be. Further, your ordering assumes no deletes.

[signa11]

>... inserts into arrays are often faster than linked lists.

don't forget, deletes, as well.

[Retric]

Yea, it's really seeks being horribly slow on out of cache linked lists being horribly slow, and then inserts and deletes being fast once you find the right node.