I'm not sure if those are the meassures that guide the decision: Searching in linked lists is suboptimal (was it O(n)?), as is their cache performance. Sure, with small lists, that doesn;t matter, but how small is small enough?