Skip List
Subject: Computer and Technology noun /ˈskɪp ˌlɪst/ 1 definition
- data-structures
- search-algorithms
- probabilistic-algorithms
- computer-science
-
Definition (noun)
Entry #46 · UpdatedA 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_84721among 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.