Skip Lists

If you've ever taken a Computer Science class, you know that finding a specific number in a sorted array is incredibly fast (using Binary Search). But if you want to insert a new number in the middle of that array, it's a nightmare. You have to shift every single element down to make room.

Linked Lists solve the insertion problem: you just swap a couple of pointers. But searching a Linked List is terribly slow. You have to walk through it one by one, from the beginning, every single time.

System designers wanted the best of both worlds: the lightning-fast search of an Array, with the effortless insertions of a Linked List.

They invented the Skip List.

The Express Train

Imagine you live in New York and you want to take the subway from 1st Street to 96th Street. If you take the Local Train, it stops at every single street: 2nd, 3rd, 4th... It takes forever. This is exactly how a normal Linked List works.

Now, imagine the MTA adds an Express Train. The Express Train only stops at 10th, 20th, 30th, etc. To get to 96th Street, you take the Express Train to 90th Street, get off, and then take the Local Train for the final 6 stops. You skipped 90% of the stops!

This is the core concept of a Skip List.

How it works

A Skip List starts as a normal, sorted Linked List (the Local Train).

But above that list, we add a second "layer" of pointers. This layer only connects every second or third node, skipping the ones in between (the Express Train).

Then, we add a third layer above that, skipping even more nodes (the Super Express Train).

When you want to find the number 84:

1. You start at the very top layer (the fastest Express Train).
2. You jump massive chunks at a time: 10 -> 40 -> 70 -> 100.
3. Oops, 100 is too big! So you drop down to the previous stop (70).
4. You move down to the next layer (a slightly slower train) and jump from 70 -> 80 -> 90.
5. 90 is too big. You drop down at 80 to the bottom layer (the Local Train).
6. You walk 80 -> 81 -> 82 -> 83 -> 84. Found it!

The Magic of Coin Flipping

You might be wondering: How do we decide which numbers get an Express station? If we strictly make every 10th node an Express station, inserting a new number will ruin the perfect spacing.

Skip Lists solve this brilliantly using probability (a literal coin flip).

When you insert a new number into the bottom layer, you flip a coin.

• Heads? You promote it to the next layer up. Then you flip again.
• Heads again? You promote it to the third layer.
• Tails? You stop.

On average, half the nodes make it to layer 2, a quarter make it to layer 3, and so on. It organically creates perfectly balanced Express routes without any complex re-balancing algorithms!

Real-World Examples

If they are so great, why aren't they used everywhere? They are often overshadowed by B-Trees, but they shine in specific modern, high-performance systems.

• Redis: Uses Skip Lists under the hood for its famous Sorted Set (ZSET) data structure. It allows Redis to maintain live leaderboards where players' scores update dynamically while keeping searches blazing fast.
• LevelDB / RocksDB: These massive database engines use Skip Lists in memory (called MemTables) to handle rapid, high-volume write operations before flushing the data to disk.

Summary

A Skip List is a layered data structure that makes searching a linked list almost as fast as searching an array. By maintaining multiple layers of pointers that "skip" over sections of the list, it acts like an Express Train, allowing you to bypass large chunks of data during a search. Because it uses random coin flips to build its layers, it is incredibly easy to implement and handles rapid data insertions far better than traditional rigid trees.