Skip to interview prep
Apexed

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.

What is an unrolled linked list and what trade-offs does it make — Data structures & algorithms interview question — Apexed