112. What is an unrolled linked list and what trade-offs does it make?
HardLinked lists
Technical
Show model answer
Each node of an unrolled list stores a small array of up to B elements rather than one element. Traversal touches far fewer nodes and uses contiguous memory inside each block, so it is much more cache-friendly and has lower pointer overhead per element.
Inserting into a full block splits it into two half-full blocks; deleting may merge a block with a neighbour if it drops below half. With block size around sqrt(n), finding the kth element takes O(sqrt n) by skipping whole blocks, and insertion and deletion within a block are O(B). The trade-off is more complex code and some wasted space in partially filled blocks.