Why a Skip List? From Sorted Arrays to Layered Lists

A horse race needs a live leaderboard, at every instant, which horse is in 1st place, which is in 2nd, and so on, while every horse's distance is changing dozens of times per second. That's really just one operation, repeated constantly: keep a collection sorted by a changing value, and read the sorted order back out cheaply. The data structure you pick for that decides whether your leaderboard is instant or a bottleneck.

Why the obvious choices fall short

• A sorted array: reading the current standings is trivial, it's already in order. But every time a horse's distance changes, you need to remove it and reinsert it at the right spot, which means shifting every element after it, an O(n) operation, once per horse, every single frame.
• A plain linked list: inserting or removing a node is O(1) once you know where, no shifting required. But finding where a given distance belongs means walking from the front one node at a time, O(n) again, you've just moved the cost from "shifting" to "searching."
• A balanced binary search tree (AVL, red-black): genuinely fixes both problems, O(log n) search and O(log n) insert/delete. The catch is implementing one correctly, rotations, rebalancing rules, and edge cases make a from-scratch balanced tree one of the fussier data structures to get right.

The skip list's trick: add shortcut lanes

A skip list gets the same O(log n) search, insert, and delete as a balanced tree, but without any rebalancing logic at all. The idea: start with an ordinary sorted linked list (this is "level 0"), then build extra linked lists on top of it that skip over multiple nodes at once, like express lanes above a local road.

Level 2:  HEAD ────────────────────────► 40 ─────────────► NULL
Level 1:  HEAD ─────────► 20 ──────────► 40 ─────────────► NULL
Level 0:  HEAD ──► 10 ──► 20 ──► 30 ──► 40 ──► 50 ──► 60 ──► NULL

Searching for 50 starts at the top level and moves forward as long as the next value is still less than what you're looking for, only dropping down a level when the next hop would overshoot. Instead of visiting every node one at a time, the search skips whole stretches of the list at once, and the fewer nodes you visit, the fewer comparisons the whole operation costs.

Where the levels come from

Here's the part that replaces a balanced tree's rebalancing rules entirely: randomness. Every time a node is inserted, it gets promoted to a higher level with a coin flip, heads, promote and flip again, tails, stop. That means roughly half of all nodes only exist at level 0, a quarter reach level 1, an eighth reach level 2, and so on. No node is ever explicitly "rebalanced," the express lanes just naturally thin out the higher you go, and that thinning is exactly what makes search, insert, and delete all expected O(log n), with dramatically simpler code than a balanced tree.