Introduction to Skip Lists
A Skip List is a probabilistic data structure that allows fast search, insertion, and deletion operations within an ordered sequence of elements. It achieves an average time complexity of O(log n) for these operations, comparable to balanced binary search trees, but with a much simpler implementation. Skip Lists were invented by William Pugh in 1989 as an alternative to balanced trees that avoids the complex rebalancing operations required by structures like AVL or Red-Black trees.
The core idea behind a Skip List is to maintain multiple layers of linked lists, where each higher layer acts as an "express lane" that skips over several elements of the lower layer. The bottom layer is a standard sorted linked list containing all elements. Each higher layer contains a subset of the elements from the layer below, allowing searches to skip large portions of the list and rapidly narrow down to the target region.
Why Skip Lists Matter
Skip Lists occupy a unique niche in the landscape of data structures. They combine the conceptual simplicity of linked lists with the logarithmic performance of balanced trees. This makes them particularly attractive in several scenarios:
- Simplicity of implementation: Unlike AVL or Red-Black trees, Skip Lists do not require complex rotation logic to maintain balance. The structure self-balances probabilistically through randomized node heights.
- Concurrent access: Skip Lists are easier to make thread-safe than balanced trees. Lock-free and fine-grained locking implementations are more straightforward because updates affect localized portions of the structure. This is why databases like Redis and LevelDB use Skip Lists internally.
- Range queries: Because the bottom layer is a sorted linked list, range queries and ordered traversal are natural and efficient operations.
- Memory efficiency: On average, each element appears in approximately two layers, giving a space complexity of O(n) with a small constant factor.
How Skip Lists Work
The Layered Structure
Imagine a sorted linked list with n elements. Searching for an element requires traversing the list one node at a time, resulting in O(n) time. A Skip List improves this by adding additional layers of pointers. The bottom layer (layer 0) contains every element. Each successive layer contains roughly half the elements of the layer below it. The topmost layer contains the fewest elements, often just one or two.
When searching, you start at the topmost layer and move forward as long as the next node's key is less than the target. When the next node's key exceeds the target, you drop down one layer and continue. This process repeats until you reach the bottom layer, where you either find the element or confirm its absence. The effect is similar to binary search, but performed on linked structures.
Randomization and Probability
The height of each node is determined randomly during insertion. A common approach is to use a coin flip: starting at layer 0, each time a fair coin comes up heads, the node is promoted to the next higher layer. This continues until tails appears. On average, each node appears in 1/(1-p) layers, where p is the promotion probability (typically 0.5). This randomization ensures the list remains balanced in expectation without any explicit rebalancing.
While the worst-case time complexity is O(n) — if every node happened to be promoted to every layer — the expected time complexity for search, insertion, and deletion is O(log n). The probability of significant imbalance diminishes exponentially with the number of elements.
Implementing a Skip List
Let us implement a Skip List in Python that supports insertion, search, and deletion of integer keys. The implementation uses a maximum level cap to prevent excessive memory usage and a promotion probability of 0.5.
Node and SkipList Classes
import random
class SkipListNode:
def __init__(self, key, level):
self.key = key
# forward[i] points to the next node at level i
self.forward = [None] * (level + 1)
class SkipList:
def __init__(self, max_level=16, p=0.5):
self.max_level = max_level
self.p = p
# header node spans all levels but holds no key
self.header = SkipListNode(None, self.max_level)
self.level = 0 # current highest level in use
def random_level(self):
lvl = 0
while random.random() < self.p and lvl < self.max_level:
lvl += 1
return lvl
def search(self, key):
current = self.header
# Start from the highest level and work downward
for i in range(self.level, -1, -1):
while current.forward[i] is not None and current.forward[i].key < key:
current = current.forward[i]
current = current.forward[0]
if current is not None and current.key == key:
return current
return None
def insert(self, key):
# update[i] will hold the node that precedes the insertion point at level i
update = [None] * (self.max_level + 1)
current = self.header
for i in range(self.level, -1, -1):
while current.forward[i] is not None and current.forward[i].key < key:
current = current.forward[i]
update[i] = current
current = current.forward[0]
# If key already exists, we can either skip or update. Here we skip.
if current is None or current.key != key:
new_level = self.random_level()
# If the new node's level exceeds current max, update header pointers
if new_level > self.level:
for i in range(self.level + 1, new_level + 1):
update[i] = self.header
self.level = new_level
new_node = SkipListNode(key, new_level)
# Splice the new node into each level
for i in range(new_level + 1):
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
def delete(self, key):
update = [None] * (self.max_level + 1)
current = self.header
for i in range(self.level, -1, -1):
while current.forward[i] is not None and current.forward[i].key < key:
current = current.forward[i]
update[i] = current
current = current.forward[0]
if current is not None and current.key == key:
# Unlink the node from every level it appears in
for i in range(self.level + 1):
if update[i].forward[i] is not current:
break
update[i].forward[i] = current.forward[i]
# Lower the overall level if the top levels are now empty
while self.level > 0 and self.header.forward[self.level] is None:
self.level -= 1
def display(self):
print("Skip List (top to bottom):")
for i in range(self.level, -1, -1):
node = self.header.forward[i]
values = []
while node is not None:
values.append(str(node.key))
node = node.forward[i]
print(f"Level {i}: {' -> '.join(values)}")
Using the Skip List
Now let us exercise the Skip List with a series of operations to demonstrate its behavior:
sl = SkipList(max_level=6, p=0.5)
# Insert several keys
for key in [3, 6, 7, 9, 12, 19, 17, 26, 21, 25]:
sl.insert(key)
sl.display()
# Search for keys
print("\nSearch 19:", sl.search(19) is not None)
print("Search 15:", sl.search(15) is not None)
# Delete a key
sl.delete(19)
print("\nAfter deleting 19:")
sl.display()
print("\nSearch 19 after deletion:", sl.search(19) is not None)
A typical run might produce output like the following, though the exact layer distribution varies due to randomization:
Skip List (top to bottom):
Level 4: 3 -> 19
Level 3: 3 -> 19
Level 2: 3 -> 7 -> 19
Level 1: 3 -> 6 -> 7 -> 9 -> 19 -> 21 -> 25
Level 0: 3 -> 6 -> 7 -> 9 -> 12 -> 17 -> 19 -> 21 -> 25 -> 26
Search 19: True
Search 15: False
After deleting 19:
Level 3: 3
Level 2: 3 -> 7
Level 1: 3 -> 6 -> 7 -> 9 -> 21 -> 25
Level 0: 3 -> 6 -> 7 -> 9 -> 12 -> 17 -> 21 -> 25 -> 26
Search 19 after deletion: False
Time Complexity Analysis
Search Complexity
Consider the search path from the top level down. At each level, the algorithm moves forward until it would overshoot the target, then drops down. Because each level contains approximately half the nodes of the level below, the expected number of nodes examined at each level is constant (at most 1/p on average). The number of levels is O(log n) in expectation, giving an expected search time of O(log n).
More formally, the expected number of comparisons is bounded by (log_{1/p} n) / p. With p = 0.5, this simplifies to approximately 2 * log2(n), which is O(log n).
Insertion Complexity
Insertion requires first searching for the insertion point, which takes O(log n) expected time. Then the new node is spliced into each level it belongs to. The expected number of levels for a new node is 1/(1-p), which is O(1). Therefore, the total expected insertion time is O(log n).
Deletion Complexity
Deletion follows the same pattern: search for the node in O(log n) expected time, then unlink it from each level it appears in. The expected number of levels to update is O(1), so the total expected deletion time is O(log n).
Space Complexity
Each node appears in an expected 1/(1-p) levels. With p = 0.5, each node appears in an average of 2 levels. The total number of pointers across all nodes is therefore O(n), giving a space complexity of O(n).
Worst-Case Behavior
In the worst case, randomization could produce a degenerate structure where every node is promoted to the maximum level, collapsing the Skip List into a set of parallel linked lists with no skipping benefit. In this scenario, all operations degrade to O(n). However, the probability of such degeneracy is astronomically small for reasonable list sizes. For practical purposes, Skip Lists deliver O(log n) performance reliably.
Best Practices
- Choose an appropriate promotion probability: A value of p = 0.5 works well for most use cases, balancing search speed against memory overhead. Lower values like 0.25 reduce memory usage at the cost of slightly slower searches, while higher values speed up searches but consume more memory.
- Cap the maximum level: Set max_level based on the expected number of elements. A good rule of thumb is max_level = ceil(log_{1/p}(n_max)), where n_max is the maximum anticipated size. For p = 0.5 and up to a billion elements, a max_level of 32 is sufficient.
- Use a high-quality random source: The balance of the Skip List depends on the quality of randomization. In production systems, use a cryptographically acceptable or well-tested pseudo-random number generator rather than a weak default.
- Consider deterministic variants for testing: For reproducible test cases, seed your random number generator or use a deterministic Skip List variant that assigns levels based on a hash of the key.
- Exploit concurrency advantages: If your application requires concurrent access, Skip Lists are an excellent choice. Implement fine-grained locking per node or use lock-free techniques with compare-and-swap operations, which are simpler to reason about than tree rotations under concurrency.
- Handle duplicates deliberately: Decide upfront whether your Skip List allows duplicate keys. The implementation above skips duplicates on insertion. If duplicates are needed, modify the insertion logic to always create a new node and use a stable ordering.
- Profile memory usage: Each forward pointer consumes memory. For memory-constrained environments, consider a compact representation that stores levels in a single array or uses a different p value to reduce average node height.
Real-World Applications
Skip Lists are used in several production systems. Redis employs them for sorted sets, leveraging their efficient range query support and straightforward concurrent access. LevelDB and RocksDB use MemTables backed by Skip Lists for in-memory sorted storage of write operations. The Lucene search engine also uses Skip Lists to accelerate postings list traversal. These applications demonstrate that Skip Lists are not merely an academic curiosity but a practical, battle-tested data structure.
Conclusion
Skip Lists offer an elegant balance between simplicity and performance. By layering probabilistically constructed express lanes over a sorted linked list, they achieve O(log n) expected time for search, insertion, and deletion without the intricate rebalancing logic required by self-balancing trees. Their natural support for ordered traversal and range queries, combined with the ease of implementing concurrent variants, makes them a compelling choice for many systems. Whether you are building an in-memory index, a database component, or simply exploring probabilistic data structures, understanding and implementing Skip Lists is a valuable addition to any developer's toolkit.