Comment by pushrax
5 years ago
Expanding on this: usually linked lists allocate each element with a separate malloc() on the heap, so they end up all over the place in memory.
You could, in principle, allocate your linked list out of contiguous memory in such a way that sequentially reading the list doesn't cause so many page accesses. That would itself be a complicated data structure to maintain, so simply using a linear array is often the right tradeoff.
That's just a slab allocator. They're not what I'd call trivial, but still simple enough to be common in small projects and CS homework. I agree that an array is still generally simpler though.
Once you are implementing your own allocator you need to worry about fragmentation under many operations, which would be the majority of the complexity.