[gizmo686]

Even in performance sensitive code, linked lists might be the right way to go. If you need to store an unknown amount of data, a resizable array probably does amoratize to a better performance than linked lists. But, all of the 'slowness' happens at the same time, so it might be worth slowing down the average case to avoid the worst case. The most notable examples I can think of are video games where FPS is king, and kernels, where you always want to exit quickly.

Linked lists can also work better in limited memory environments because, with the overhead of 1 pointer per element, you can make use of fragmented memory.

[olivier1664]

Or something between the two: "Unrolled linked list": In computer programming, an unrolled linked list is a variation on the linked list which stores multiple elements in each node. https://en.wikipedia.org/wiki/Unrolled_linked_list