Comment by kevincox

Traversing a linked list is terrible for performance. But in cases like the cache you are only poping from the front, appending to the back or removing which are all quite fast and require little pointer chashing.

Cache cost of individual allocations can be an issue but that can also be mitigated with a good allocator and even without special care can be quite performant in many applications.

I agree the linked lists shouldn't be the first structure you reach to. But there are situations where they can perform very well.