Skip Lists: Simplicity Meets Efficiency

Introduction

Most data structures require trade-offs. Arrays offer fast access but slow insertions. Linked lists make insertions easy but searching is slow. Binary search trees provide balanced performance, but implementing them correctly is notoriously tricky.

Enter skip lists—a data structure that achieves the best of multiple worlds. With expected O(log n) time complexity for search, insert, and delete operations, skip lists rival balanced trees while being significantly simpler to implement. Their elegance and efficiency have made them favorites in practice, with Redis using them for ordered sets.

This article explores skip lists, explaining how they work, why they’re efficient, and when you might choose them over alternatives.

The Problem with Linked Lists

Imagine you’re searching for an item in a sorted linked list. Even though the data is sorted, you have no choice but to scan from the beginning, checking each node until you find your target. This gives O(n) search time—slow for large lists.

What if you could create “express lanes” that let you skip over large portions of the list? That’s exactly what skip lists do.

How Skip Lists Work

A skip list is a layered linked list where:

• The bottom layer contains all elements in sorted order
• Each higher layer acts as an “express lane,” containing a subset of elements from below
• Elements in higher layers are chosen randomly (typically with 50% probability)
• Searching starts from the highest layer and descends progressively

Think of it like a highway system. To travel from city A to city Z, you could take the local road through every town, or you could take highways that bypass many towns. Skip lists create multiple “highways” through the data.

Searching in a Skip List

Searching for a target value follows these steps:

1. Start at the highest level of the list
2. Move forward as long as the next node’s value is less than the target
3. When you can’t move forward, descend one level
4. Repeat until you reach the bottom level
5. Check if the current node matches the target

This process lets you skip vast portions of the data. At each level, you’re essentially making a binary search among the elements at that level. With roughly log₂(n) levels and O(1) movement per level, search takes O(log n) expected time.

Insertion: Building the Express Lanes

Insertion is where the magic happens. When you insert a new element:

1. Find where it should go in the bottom layer (standard linked list insertion)
2. Randomly determine how many “express lanes” it should appear in
3. Insert it into those corresponding higher layers

The random selection uses a geometric distribution—each level has a 50% chance of including the new element, assuming a 1/2 probability. This ensures that roughly half the elements appear in level 1, a quarter in level 2, an eighth in level 3, and so on.

This probabilistic approach means:

• Higher levels have fewer elements, creating longer “jumps”
• The overall structure maintains O(log n) expected height
• No complex rebalancing operations are needed

Deletion in Skip Lists

Deletion is straightforward:

1. Find the element in all layers where it appears
2. Remove it from each layer’s linked list

If the element doesn’t exist in a particular layer, you simply skip it. No complex rebalancing is needed because you’re just removing nodes—you never have to “fill in” gaps like with B-Trees.

Implementing Skip Lists

The simplicity of skip lists is one of their greatest strengths. Here’s what you need:

Node structure: Each node contains a value and an array of forward pointers (one for each level where the node appears).

Level management: You need a way to generate random levels. A simple approach uses repeated coin flips until you get tails (or reach a maximum level).

Search algorithm: The core search logic is just a few lines—compare, move forward, or descend.

Compare this to red-black trees, which require multiple rotation cases and careful color management. Skip lists achieve similar performance with a fraction of the code.

Time Complexity Analysis

Skip lists provide expected O(log n) time complexity for all major operations:

• Search: O(log n) expected
• Insert: O(log n) expected
• Delete: O(log n) expected
• Range query: O(log n + k) where k is the number of elements in the range

The key word is “expected.” While worst-case performance can be O(n), the probability of such worst cases is astronomically small with proper implementation. The mathematical analysis shows that a skip list with n elements has expected height of O(log n).

Space Complexity

A skip list uses more space than a single linked list because elements appear in multiple layers. On average, each element appears in 2 layers (since the sum of 1/2 + 1/4 + 1/8 + … = 1).

This gives O(n) space complexity, with the constant factor being roughly 2x a regular linked list. This trade-off is usually acceptable given the performance benefits.

Skip Lists in Practice

Skip lists are used in several real-world systems:

Redis uses skip lists for ordered sets, providing fast sorted operations while maintaining O(log n) insertion and retrieval.

Lucene (the search library behind Elasticsearch) uses skip lists in its inverted index for fast intersection of posting lists.

LevelDB, RocksDB and other key-value stores use skip lists as their underlying memtable structure.

The simplicity of skip lists also makes them excellent for teaching balanced tree concepts. Students can understand skip lists more easily than red-black trees while learning similar algorithmic concepts.

When to Use Skip Lists

Skip lists are excellent when:

• You need O(log n) operations with simpler implementation than balanced trees
• Memory is available for the extra levels (roughly 2x a linked list)
• You need ordered data with fast insertions and deletions
• Range queries are important (skip lists handle these well)

They might not be the best choice when:

• Worst-case guarantees must be strictly enforced (use arrays or balanced trees)
• Memory is extremely constrained
• You need persistent/immutable data structures

External Resources

• Skip Lists: A Probabilistic Alternative to Balanced Trees - Original paper by William Pugh
• GeeksforGeeks - Skip List
• Redis Documentation - Sorted Sets
• OpenDSA - Skip Lists

Conclusion

Skip lists demonstrate that sometimes simpler approaches can match or exceed more complex ones. By embracing randomization, they achieve the same performance as carefully balanced trees with a fraction of the implementation complexity.

The next time you need an ordered data structure with fast operations, consider skip lists. Their elegance, efficiency, and simplicity make them an excellent choice for many applications.