DataTerminology.comNEW
A probabilistic layered linked-list structure enabling fast expected-time search, insert, and delete in ordered sequences.
DESCRIPTION
Skip lists maintain multiple levels of forward pointers, allowing searches to skip over large sections of elements. With randomized level promotion, they achieve expected O(log n) operations while being simple to implement. They are used in in-memory indexes, caches, and concurrent maps. Variants support lock-free concurrency and memory efficiency.
ALTERNATIVE DEFINITIONS
Wikipedia
A skip list is a data structure that allows fast search within an ordered sequence of elements.
Focuses on fast search within ordered sequences.
William Pugh
Skip lists are probabilistic data structures that have the same asymptotic expected time bounds as balanced trees, and are simpler, faster and use less space.
Original paper emphasizing probabilistic nature and simplicity vs. trees.
RELATED TERMS
Balanced Tree Binary Search Tree Randomized Algorithm Linked List Ordered Map Concurrent Data Structures Lock-free Structures Indexing Search Algorithm Caching
COMPETING TERMS
AVL Tree Red–Black Tree B-Tree
RELATIONS
- Broader: List
KNOWLEDGE AREAS
Software Engineering Mathematics Data Storage & Operations
TARGET AUDIENCE
Software Developer Software Architect Data Engineer Full Stack Developer
EXTERNAL SOURCES
- Wikipedia - Skip list
- William Pugh - Original skip list paper
- LevelDB - LSM indexing uses skiplists
TOP QUESTIONS
Why use a skip list instead of a balanced tree?
Skip lists are simpler to implement and offer similar expected O(log n) performance, with good cache behavior.
Category: Alternatives
How does search work in a skip list?
Start at the top level, traverse forward until overshoot, then drop to the next level, repeating until found.
Category: How-to
What determines element levels?
Randomized promotion (e.g., coin flips) assigns levels, creating a geometric distribution of tower heights.
Category: Requirements
Are skip lists good for concurrency?
Yes, lock-free and fine-grained locking variants support high concurrency with predictable progress.
Category: Opinion
What’s a common design mistake?
Failing to handle duplicate keys or incorrect pointer updates can corrupt levels. Validate invariants.
Category: Mistakes
Where are skip lists used in practice?
They often back in-memory indexes and caches in LSM-tree databases and key-value stores.
Category: Example
What’s the space complexity?
Expected O(n) with constant-factor overhead for additional pointers per node tower.
Category: Requirements
What is a skip list’s biggest risk?
Poor randomization or pathological data can degrade constants, though expected bounds remain logarithmic.
Category: Risks
How to tune maximum levels?
Choose based on n (e.g., ~log2 n) and branching probability (commonly p=0.5) to balance speed and space.
Category: How-to