Implementing a Skip List for Efficient Search in Sorted Data

A skip list is a layered linked data structure that keeps values sorted while making search, insertion, and deletion fast on average. It offers many of the practical benefits of a balanced search tree, but its implementation is often easier to understand because it relies on linked nodes and random level selection rather than tree rotations.

The basic idea is to build several linked lists on top of a base list. The lowest layer contains every item in order, while higher layers contain selected “express” links that allow a search to jump over large ranges. A query starts at the highest level and moves forwards until the next node would exceed the target.

This structure is useful when data changes frequently and maintaining a sorted order matters. Examples include ordered indexes, event streams, in-memory ranking systems, and time-based records. A team processing ASX price updates, for instance, could use a skip list to maintain sorted keys while avoiding the complexity of a full balanced tree implementation.

Skip lists are a useful addition to a programmer’s toolkit alongside the structures covered in algorithm tutorials. They demonstrate how a small amount of randomness can produce reliable average performance without requiring a rigid balancing algorithm.

How A Skip List Organises Sorted Values

At the bottom of a skip list is an ordinary sorted linked list. Each node stores a key, an optional value, and a collection of forward references. The first node is usually a sentinel with a key smaller than every valid key. It simplifies boundary cases because every operation begins from the same known position.

Higher levels act as shortcuts. Suppose the base list contains 3, 8, 12, 19, 24, 31, and 40. A higher level might link 3 to 12, 12 to 24, and 24 to 40. A search for 31 can travel quickly across the upper layer, drop down near 24, then continue along the base list.

Unlike a binary search tree, a skip list does not store left and right child pointers. It also does not need rotations after an insertion or deletion. This makes the code attractive for educational projects and systems where straightforward pointer manipulation is preferable.

Choosing Levels With Randomness

When a node is inserted, the implementation randomly decides how many levels it should occupy. Every node appears at level zero, some nodes appear at level one, fewer reach level two, and so on. A common rule promotes a node while a random number is below a probability such as 0.5.

The probability controls the shape of the structure. With a promotion probability of one half, the expected number of nodes at each higher level falls by roughly half. The maximum level is normally capped, often at log2(n) plus a small margin, where n is the expected maximum number of elements.

A random level function can be written as follows:

random_level():
    level = 0
    while random() < promotion_probability
          and level < maximum_level:
        level += 1
    return level

A seeded random generator is helpful during testing because it produces repeatable layouts. Production code may use a thread-local generator or another concurrency-safe option. The structure remains probabilistic: its familiar logarithmic performance is expected rather than guaranteed for every possible random outcome.

Building The Core Python Structure

A Python implementation needs two classes: one for a node and one for the skip list. The node’s forward array has one entry for each level it occupies. The list itself stores a sentinel, the current highest active level, and the probability used by the random level generator.

import random

class Node:
    def __init__(self, key, value, level):
        self.key = key
        self.value = value
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level=16, probability=0.5):
        self.max_level = max_level
        self.probability = probability
        self.level = 0
        self.head = Node(None, None, max_level)

    def random_level(self):
        level = 0
        while (random.random() < self.probability
               and level < self.max_level):
            level += 1
        return level

The sentinel has a forward slot for every possible level. Real nodes can be shorter, which keeps memory usage proportional to the levels they actually receive. In an application that stores strings, records, or objects, the value can hold the payload while key controls sorted order.

A few implementation decisions should be settled early:

• Decide whether duplicate keys replace existing values or create separate records.
• Define how missing keys are represented, such as None or a raised exception.
• Choose whether keys must support only < comparisons or a richer ordering interface.
• Set a maximum level based on the expected collection size.
• Keep the random generator injectable if deterministic tests are important.

Searching Inserting And Removing Nodes

Search starts at the highest active level and moves forwards while the next node’s key is less than the target. When moving forward would pass the target, the algorithm drops one level. At level zero, the next node either contains the key or proves that it is absent.

Insertion uses an update array. For every level, update[level] records the last node before the position where the new key belongs. If the key already exists, the value can be replaced. Otherwise, a new random height is selected and the new node is linked into every relevant level.

def find(self, key):
    current = self.head
    for level in range(self.level, -1, -1):
        while (current.forward[level] is not None
               and current.forward[level].key < key):
            current = current.forward[level]

    current = current.forward[0]
    return current.value if current and current.key == key else None

Deletion follows the same path-building process. Once the target is located, each predecessor in update skips over the target at levels where that link exists. If the highest levels become empty, the list lowers its active level value. This prevents future searches from inspecting unused layers.

A complete insert method should also deal with an existing key before creating a node. That small detail determines whether the structure behaves like a map, a multimap, or a sorted set. For a map-like interface, replacing the value is usually the least surprising choice.

Complexity And Practical Tradeoffs

The expected time for search, insertion, and deletion is O(log n). The expected memory cost is O(n), with an additional pointer per node on average determined by the promotion probability. Traversing the lowest level in order takes O(n), so a skip list can also support range scans and ordered iteration naturally.

The worst case for an individual operation is O(n) if the random levels produce an unfavourable layout. In practice, a suitable probability and maximum level make this uncommon. A balanced tree offers stronger worst-case guarantees, while a skip list often wins in simplicity and can be easier to adapt for concurrent algorithms.

For large datasets, pointer-heavy nodes may consume more memory than arrays or packed indexes. Python adds object and reference overhead, so a production implementation may need profiling before it is used for millions of entries. In-memory use cases are usually the best fit; disk-backed indexes need a design that considers page locality.

The structure also suits ordered graph-related work as a supporting index, although it does not replace graph algorithms. For example, when studying minimum spanning trees, a review of Kruskal’s algorithm shows how sorted edge processing affects performance; a skip list could maintain a changing ordered collection of candidate edges, while a disjoint-set structure handles connectivity.

Testing And Adapting The Implementation

Testing should compare the skip list with a trusted reference, such as a Python dictionary for exact lookup and a sorted list for ordering. Insert random keys, update existing keys, remove a mixture of present and absent keys, and check that iteration remains sorted after every operation.

Australian developers may test with data patterns that reflect real services: timestamps arriving in Australian Eastern Time, postcode-like integer keys from Sydney or Perth, or price updates from an ASX-style feed. These examples expose duplicate timestamps, bursts of updates during market hours, and records arriving slightly out of order.

Useful checks include:

• Searching an empty list and a one-node list.
• Inserting keys in ascending, descending, and random order.
• Replacing a value when the key already exists.
• Removing the smallest, largest, and only remaining key.
• Verifying every forward level remains sorted.
• Comparing range results with a separately sorted reference list.

For a small command-line project, a straightforward class is enough. In a larger service, consider locking around mutations, defining an iterator that detects modification, and recording metrics for height distribution. A team in Melbourne might use the structure for a live dashboard, while a regional Australian service with limited compute could favour its simple operations and predictable memory planning.

Performance tests should measure realistic workloads rather than relying only on theoretical complexity. Vary the number of elements, lookup hit rate, duplicate frequency, and promotion probability. Repeat each benchmark with several random seeds so that one unusually tall or short layout does not distort the result.

Further extensions can include range queries, reverse traversal, custom comparators, and support for duplicate keys. A reverse index needs backward references or a separate traversal strategy, which increases memory cost. For most educational and general-purpose implementations, forward links and a clear map-like API provide the best balance of readability and capability.