Skip to main content
Definition Website Computer and Technology

Skip List

Subject: Computer and Technology noun /ˈskɪp ˌlɪst/ 1 definition

  1. Definition (noun)

    Entry #46 · Updated

    A Skip List is a probabilistic, multi-layered data structure built from stacked sorted linked lists that enables fast ordered search, insertion, and deletion. The bottom layer links every element in sorted order, while each higher layer holds a sparser subset of promoted nodes that act as express lanes to bypass large segments of keys during traversal. By using randomized level assignment instead of deterministic structural rebalancing, a skip list achieves O(log n) average-case time complexity—comparable to balanced binary search trees—while keeping updates localized and straightforward to synchronize in concurrent environments.

    Common Types

    • Standard Probabilistic Skip List: Assigns each newly inserted node a random height via repeated coin flips (commonly with promotion probability 1/2 or 1/4), yielding expected O(log n) search and update times without tree rotations.

    • Concurrent Skip List: Coordinates multi-threaded reads and writes using fine-grained node locks or lock-free atomic compare-and-swap (CAS) operations, powering standard concurrent maps such as Java's ConcurrentSkipListMap.

    • Indexable Skip List: Stores span widths on each forward link to count skipped base-layer elements, enabling O(log n) rank lookups and positional range queries as used in Redis sorted sets.

    • Deterministic Skip List: Replaces randomized promotion with strict gap invariants between nodes at adjacent levels, trading implementation simplicity for guaranteed worst-case O(log n) operation bounds.

    Example

    An in-memory storage engine buffers incoming writes in a concurrent skip list memtable sorted by key before flushing them to disk. When a lookup requests key usr_84721 among 1,000,000 buffered records, the reader traverses the upper express lanes down to the base layer, inspecting only a few dozen nodes instead of scanning the list sequentially.