# Skip List: Design and Applications

Source: https://www.techinterview.org/post/3233473472/lld-skip-list-design/
Updated: 2026-04-18 · techinterview.org

A skip list is a probabilistic data structure that provides O(log n) average time for search, insertion, and deletion — the same asymptotic complexity as a balanced BST, but with simpler implementation and better cache behavior. It achieves this by layering multiple linked lists, where higher layers contain fewer elements, creating "express lanes" that skip over most elements during traversal. Redis uses skip lists as the underlying data structure for sorted sets.

## Structure

A skip list consists of multiple levels of linked lists. Level 0 contains all elements in sorted order — the base linked list. Level 1 contains roughly half the elements (every other element from level 0). Level 2 contains roughly half the elements from level 1. And so on, up to a maximum level (typically log₂(n)). Each element has a tower of forward pointers — one per level it participates in. A sentinel head node points to the first element at each level; a sentinel tail marks the end.

## Search

To search for a target: start at the highest level of the head node. At each level, advance forward as long as the next node's key is less than the target. When advancing further would overshoot (next key >= target) or reach the end, drop down one level. Repeat until level 0. Check if the current node's key equals the target. This traversal visits O(log n) nodes on average — the higher levels skip over large portions of the list, narrowing the search range geometrically.

## Insertion and Level Randomization

When inserting a new element: find the correct position using the search algorithm (track the rightmost node at each level that is less than the new element). Randomly determine the new node's level: flip a coin; if heads, increment the level; repeat until tails or the maximum level is reached. This gives level 1 with probability 1, level 2 with probability 1/2, level 3 with probability 1/4, and so on. Link the new node into the list at each of its levels, updating the tracked predecessor nodes' forward pointers. No rebalancing is ever required — the probabilistic level assignment maintains expected O(log n) height.

## Why Redis Uses Skip Lists for Sorted Sets

Redis sorted sets (ZADD, ZRANGE, ZRANK, ZRANGEBYSCORE) require: insertion with O(log n) time, rank queries ("what position is this element?"), and range queries ("return all elements between score 100 and 200"). Skip lists support all of these efficiently. Unlike a BST, skip lists are simpler to implement in C without tree rotations. Skip lists also support O(log n) rank queries by augmenting each forward pointer with a span count — the number of nodes it skips. Redis's skip list implementation stores each element in both a hash table (for O(1) key lookup) and a skip list (for score-ordered operations).

## Range Queries

To retrieve all elements with score between lo and hi: search for lo using the standard search; this lands on the first element with score >= lo. Traverse level 0 forward, collecting elements until score > hi. This is O(log n + k) where k is the number of results — optimal for range queries. This is why ZRANGEBYSCORE in Redis is efficient: the skip list's sorted structure makes range scans a simple level-0 traversal after finding the start position.

## Skip List vs. Balanced BST

Same asymptotic complexity (O(log n) search, insert, delete). Skip lists win on: simpler implementation (no rotations, no rebalancing logic), better concurrent access (updating a skip list node only requires modifying predecessor pointers, making lock-free implementations viable), and cache efficiency for traversal (level-0 traversal is a linked list scan). BSTs win on: deterministic worst-case performance (skip lists have O(n) worst case with low probability), smaller constant factor for small n, and sorted order traversal without a separate level-0 scan. Choose skip lists when concurrency matters and O(log n) average is sufficient; choose BSTs when worst-case guarantees are required.

See also: [Meta Interview Guide 2026: Facebook, Instagram, WhatsApp Engineering](https://www.techinterview.org/post/3233460272/meta-interview-guide-2026-facebook-instagram-whatsapp-engineering/)

See also: [Uber Interview Guide 2026: Dispatch Systems, Geospatial Algorithms, and Marketplace Engineering](https://www.techinterview.org/post/3233460273/uber-interview-guide-2026-dispatch-systems-geospatial-algorithms-and-marketplace-engineering/)

See also: [Netflix Interview Guide 2026: Streaming Architecture, Recommendation Systems, and Engineering Excellence](https://www.techinterview.org/post/3233460274/netflix-interview-guide-2026-streaming-architecture-recommendation-systems-and-engineering-excellence/)

See also: [Scale AI Interview Guide 2026: Data Infrastructure, RLHF Pipelines, and ML Engineering](https://www.techinterview.org/post/3233460275/scale-ai-interview-guide-2026-data-infrastructure-rlhf-pipelines-and-ml-engineering/)

See also: [LinkedIn Interview Guide 2026: Social Graph Engineering, Feed Ranking, and Professional Network Scale](https://www.techinterview.org/post/3233460278/linkedin-interview-guide-2026-social-graph-engineering-feed-ranking-and-professional-network-scale/)

See also: [Airbnb Interview Guide 2026: Search Systems, Trust and Safety, and Full-Stack Engineering](https://www.techinterview.org/post/3233460279/airbnb-interview-guide-2026-search-systems-trust-and-safety-and-full-stack-engineering/)

See also: [Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture](https://www.techinterview.org/post/3233460280/databricks-interview-guide-2026-spark-internals-delta-lake-and-lakehouse-architecture/)

See also: [Anthropic Interview Guide 2026: Process, Questions, and AI Safety](https://www.techinterview.org/?p=3233460282)

See also: [Atlassian Interview Guide](https://www.techinterview.org/post/3233459919/atlassian-interview/)

See also: [Coinbase Interview Guide](https://www.techinterview.org/post/3233459920/coinbase-interview/)

See also: [Shopify Interview Guide](https://www.techinterview.org/post/3233459924/shopify-interview/)

See also: [Snap Interview Guide](https://www.techinterview.org/post/3233459923/snap-interview/)

See also: [Lyft Interview Guide 2026: Rideshare Engineering, Real-Time Dispatch, and Safety Systems](https://www.techinterview.org/post/3233460306/lyft-interview-guide-2026-rideshare-engineering-real-time-dispatch-and-safety-systems/)

See also: [Stripe Interview Guide 2026: Process, Bug Bash Round, and Payment Systems](https://www.techinterview.org/post/3233460268/stripe-interview-guide-2026-process-bug-bash-round-and-payment-systems/)