Skip Lists: A probablistic Alternative to Balanced Trees

Created: 2022-01-25T12:03:11-06:00

Skip lists have similar performance to balanced trees. They cost additional pointers for each level of indexing and have rare chances to perform poorly ("anxiety.") But for all realistic inputs they work like self-balancing trees with less code and much easier to implement lock-free.

What is it

• Start with a linked list.
• Now add additional forward pointers for additional "skip over" levels.
• Also associate a key field with each node and the total list is sorted by this key.

How does it work

• Each additional level skips over the next power of two elements.
• Each level has a probability that a node belongs to it; ex. level 2 is 50%, level 3 is 25%, etc.
• When inserting a node roll dice to determine which level it will belong to.