Data Structures · Cluster
Linked Structures
Lists, intrusive chains, and pointer-based layouts.
- 01 Singly Linked Lists: One Pointer per Node and the Cost of Unidirectional Traversal How a head pointer and a next field support O(1) splicing, why deletion needs the predecessor, and what pointer chasing costs on a modern cache hierarchy.
- 02 Doubly Linked Lists and the Sentinel Header That Removes the Null Checks Why two pointers buy constant-time removal from a node alone, how a circular sentinel collapses the special cases, and what the extra word per node costs.
- 03 Intrusive Linked Lists: Embedding the Link in the Payload How intrusive chains eliminate per-element allocation and let one object sit on several lists at once, at the cost of type knowledge and ownership rules.
- 04 Unrolled Linked Lists and the Cost of a Cache Miss per Node Packing several elements per node cuts pointer chases by the node capacity, and the block size that minimises total cost follows from a cache line and a word.
- 05 Index-Based Linked Lists for Relocatable and Persistent Storage Replacing pointers with offsets makes a linked structure relocatable, mmap-safe, and serialisable, and forces explicit handling of free slots and stale indices.
- 06 XOR Linked Lists: One Link Field for Both Directions Storing the difference of the two neighbour addresses halves link storage and forces traversal to carry two cursors, which breaks under debugging tools and section boundaries.
- 07 Free Lists: Threading Reuse Through the Blocks an Allocator Has Released How an allocator stores its free list inside the freed memory itself, why coalescing needs boundary tags, and what size-class segregation does to fragmentation.
- 08 Lock-Free Linked Lists and the Reclamation Problem Compare-and-swap can insert and delete on a singly linked list without locks, but freeing a removed node requires hazard pointers or epoch tracking to stop reuse.
- 09 Move-to-Front Lists and the Working-Set Bound on Sequential Search Reordering a list on every access costs one splice and buys a factor-two competitive bound against any static ordering, with a cost that depends on the access distribution.
- 10 Skip Lists: Express Lanes over a Sorted Chain Layered forward pointers turn a linear scan into an expected O(log n) search, and the geometric level distribution is what makes the expected bound hold without rebalancing.