3 ms·

> 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 seq

> 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 11y ago
It can be avoided by choosing a good allocation strategy for the linked list, allocating nodes in an arena can eliminate cache misses.
- yoklov 11y ago
  You'll still have more than if you had used an array, due to the low information density (2 extra pointers / node).