# Skip Lists: The O(log n) Alternative to Balanced Trees

**TL;DR: A skip list is a probabilistic data structure that upgrades a standard linked list's O(n) search time to O(log n). By layering multiple sorted "express lane" linked lists on top of each other, it allows search queries to skip large sections of data, achieving logarithmic search times comparable to balanced binary trees.**

---

Think of standard linked lists like local subway trains. If you need to reach the last stop, you have to sit through every single station along the line. 

Skip lists solve this O(n) traversal bottleneck by adding express lines on top of the local track. By jumping across widely spaced express stops first, you can skip most of the list before dropping down to the local track to find your exact target.

## What is a skip list and how does it work?

**A skip list is a layered, sorted data structure that uses a probabilistic hierarchy to enable O(log n) search, insertion, and deletion times. The bottom layer is a standard sorted linked list, while each higher layer acts as an "express lane" containing fewer, widely spaced elements. This design allows you to skip huge segments of the dataset during search operations.**

Instead of scanning a standard linked list element-by-element, a skip list lets you bypass chunks of elements at a time. 

We can visualize this system in layers:
* **Layer 0 (The Local Track):** Every single element is present and sorted sequentially. E.g., `1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8`
* **Layer 1 (The Semi-Express Track):** Contains roughly half the elements. E.g., `1 -> 3 -> 5 -> 7`
* **Layer 2 (The Express Track):** Contains roughly a quarter of the elements. E.g., `1 -> 5`

Because the elements are sorted, you can traverse the topmost layer first. Once you overshoot your target value, you drop down a layer and continue traversing. If you have a billion elements, this layering system lets you locate any item in tens of checks rather than a billion checks.

## How does a skip list compare to other data structures?

**Skip lists provide O(log n) average time complexity for search, insertion, and deletion, matching the performance of balanced binary trees like AVL or Red-Black trees. However, they are significantly easier to implement and highly concurrency-friendly because they don't require complex tree-rebalancing algorithms. This makes them ideal for high-throughput, multi-threaded database engines.**

Here is how skip lists compare to alternative data structures:

| Data Structure | Search Complexity (Average) | Insertion Complexity (Average) | Implementation Complexity |
| :--- | :--- | :--- | :--- |
| Standard Linked List | O(n) | O(1) (if position known) | Very Easy |
| **Skip List** | **O(log n)** | **O(log n)** | **Medium** |
| Red-Black Tree | O(log n) | O(log n) | High |

## How do you search an element in a skip list?

**Searching a skip list begins at the topmost layer's header node and moves horizontally as long as the next node's value is less than or equal to the target. When the next node's value exceeds the target, the search drops down vertically to the next lower layer. This horizontal-then-vertical pattern repeats until you find the element or reach the end of the bottom layer.**

To represent a multi-level node in code, we use an array of forward pointers. In this setup, each index `i` of the `next` slice maps directly to the forward pointer at level `i`, with level `0` representing the base linked list:

```go
type SkipNode struct {
    value int
    next  []*SkipNode // next[i] points to the next node at level i
}
```

When searching for `7` in our previous three-layer example, you start at Layer 2:
1. At Layer 2, you see `1` and look ahead to `5`. Since `5` is less than `7`, you jump to `5`.
2. From `5`, the next node on Layer 2 is the end of the list, so you drop down to Layer 1.
3. At Layer 1, you look ahead from `5` and see `7`. You jump to `7` and complete the search.

## FAQ

### What is the worst-case time complexity of a skip list?
In the absolute worst-case scenario (for example, if coin flips result in no express levels being built, or conversely, every element being promoted to every level), a skip list degrades to O(n) search time. However, the mathematical probability of this occurring is astronomically low in practice.

### How do skip lists handle insertions?
When inserting a new element, it is always added to the bottom layer. The algorithm then flips a fair coin to decide whether to promote the element to the next layer up, continuing to flip and promote until a coin flip lands on tails.

### Where are skip lists used in production systems?
Skip lists are highly favored in concurrent databases because they do not require global locks for rebalancing. They are used in Redis for sorted sets (ZSET), as well as in the MemTables of popular storage engines like RocksDB and LevelDB.