[pmelendez]

> Linked lists don't suffer from this problem, but at the cost of 1-2 pointers per item.

Another cost is the cache misses. If you are doing operations in a sequential fashion using an array would have a significant advantage if the number of elements is high. That's another tradeoff to take in consideration.

[adrusi]

It can be avoided by choosing a good allocation strategy for the linked list, allocating nodes in an arena can eliminate cache misses.

[yoklov]

You'll still have more than if you had used an array, due to the low information density (2 extra pointers / node).