3 ms·
Not only are linked lists rare, they are also mainly useful exactly in situations where you cannot guarantee a (even mostly) linear allocation order.
by account42 2y ago
Not only are linked lists rare, they are also mainly useful exactly in situations where you cannot guarantee a (even mostly) linear allocation order.
- gpderetta 2y agothe optimization could be vaguely interesting if you are implementing a lisp (or some other list heavy language) and don't want to perform too aggressive non-local optimizations to optimize the layout of lists.
- twoodfin 2y agoAs I recall, at least one of the Lisp machine Lisps used a bit in the cons pair to declare if the cdr (tail element) was immediately following. EDIT: https://en.wikipedia.org/wiki/CDR_coding https://en.wikipedia.org/wiki/CDR_coding
- kevin_thibedeau 2y agoMemory pools are commonly allocated in a contiguous block and sliced into nodes placed onto a free list. They will be sequential until the pattern of allocations mixes them up.
- kazinator 2y agoGarbage collection is good at consolidating swaths of adjacent free objects into ordered allocation.
- saagarjha 2y agoThe point here is that this isn't guaranteed, it's that it is likely. And as the other commenters mention, it's likelier than you think.
- kazinator 2y agoThe Linux kernel is full of links, and so are many (probably most) C programs in the GNU/Linux userland.