A tower of linked lists
A skip list keeps elements sorted across several linked levels. The bottom level holds every node, and each higher level holds a random subset that acts as an express lane. A search starts at the top, moves right until it would overshoot, then drops a level, giving logarithmic expected cost.
Why it suits concurrency
Skip lists are friendlier to parallelism than balanced trees:
- A rebalanced tree may rotate large subtrees, touching many nodes at once
- A skip list changes only a local handful of pointers per insert
- Searches can traverse without locks because they only follow pointers, never mutate
Lock free linking
An insert first finds its position, then links the new node into each level from the bottom up using compare and swap. Higher level links are published only after the bottom link succeeds, so a concurrent searcher always finds a consistent path even mid insertion. The randomized height avoids the global restructuring that makes trees hard to parallelize.
Key idea
A concurrent skip list replaces tree rotations with localized randomized links, enabling lock free search and scalable ordered inserts.