7 ms·
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
by pushrax 6y 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.
- AlotOfReading 6y agoThat'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.
- pushrax 6y agoOnce you are implementing your own allocator you need to worry about fragmentation under many operations, which would be the majority of the complexity.