Hacker News Reader

Comment by cjaybo | Hacker News Reader

> PS: If the linked list is stored in contiguous memory (if you're using a slab allocator, for example), you can actually be even more clever (I'll leave that as an exercise to the reader).

This might be a dumb question, but if list elements are stored contiguously, is there any advantage to using a linked list instead of a data structure that is designed for contiguous storage (something like C++'s std::vector)?

View on HN

  > if list elements are stored contiguously, is there any advantage to using a linked list

Storing them contiguously probably implies that you consider "freed" space in the middle to also be part of the contiguous area. Otherwise you can't remove in O(1) time.

It is straightforward to maintain a list of freed nodes which you can add back later.

If you don't mind not being able to remove in O(1) time, you still have the advantage of passing the handi-capped (contiguous) linked list to interfaces that expect a linked list, but still get the cache locality of a plain vector.

Reply on news.ycombinator.com