Watch 9 video solutions for Design Skiplist, a hard level problem involving Linked List, Design. This walkthrough by Hua Hua has 3,955 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Design a Skiplist without using any built-in libraries.
A skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists is just simple linked lists.
For example, we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way:
Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons
You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add, erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n).
See more about Skiplist: https://en.wikipedia.org/wiki/Skip_list
Implement the Skiplist class:
Skiplist() Initializes the object of the skiplist.bool search(int target) Returns true if the integer target exists in the Skiplist or false otherwise.void add(int num) Inserts the value num into the SkipList.bool erase(int num) Removes the value num from the Skiplist and returns true. If num does not exist in the Skiplist, do nothing and return false. If there exist multiple num values, removing any one of them is fine.Note that duplicates may exist in the Skiplist, your code needs to handle this situation.
Example 1:
Input ["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"] [[], [1], [2], [3], [0], [4], [1], [0], [1], [1]] Output [null, null, null, null, false, null, true, false, true, false] Explanation Skiplist skiplist = new Skiplist(); skiplist.add(1); skiplist.add(2); skiplist.add(3); skiplist.search(0); // return False skiplist.add(4); skiplist.search(1); // return True skiplist.erase(0); // return False, 0 is not in skiplist. skiplist.erase(1); // return True skiplist.search(1); // return False, 1 has already been erased.
Constraints:
0 <= num, target <= 2 * 1045 * 104 calls will be made to search, add, and erase.Problem Overview: Design a data structure that supports search, add, and erase operations efficiently. The structure should behave like a balanced sorted list where operations run in logarithmic time on average.
Approach 1: Basic Level Implementation (O(n) search, O(n) space)
This approach builds a simplified skiplist using multiple linked lists stacked as levels. Each level skips over some nodes from the level below, but level promotion is handled manually rather than probabilistically. To search, you traverse horizontally until the next node exceeds the target, then drop down a level. Because balancing is not guaranteed, the structure can degrade and operations may reach O(n) time in the worst case. Useful for understanding how layered navigation works before introducing randomization.
Approach 2: Advanced Implementation with Probability Factor (Average O(log n) time, O(n) space)
This version introduces probabilistic balancing. When inserting a node, you repeatedly flip a virtual coin to decide how many levels the node should occupy. Higher levels contain fewer nodes, creating exponentially decreasing density. During search, you start from the highest level and move right while values are smaller than the target, dropping down levels when necessary. Random level assignment maintains balanced height statistically, giving average O(log n) search, insertion, and deletion.
Approach 3: Classic Skiplist with Random Levels (Average O(log n) time, O(n) space)
The classic skiplist maintains a head node with multiple forward pointers. Each inserted node receives a random level using geometric probability (commonly p = 0.5). During insertion, you track predecessor nodes at each level while traversing from the top layer downward. After generating the new node's level, you update forward pointers for all affected layers. This implementation closely follows the original skiplist design and provides efficient ordered operations comparable to balanced trees without complex rotations.
Approach 4: Deterministic Balanced Skiplist (O(log n) time, O(n) space)
A deterministic version removes randomness and enforces level structure using a fixed promotion rule. Nodes are promoted based on deterministic balancing criteria or fixed probability thresholds. When the structure becomes unbalanced, level reduction or restructuring keeps height near log n. This design improves predictability and avoids randomness while still maintaining fast navigation across layers. It is useful in environments where deterministic behavior is preferred.
Recommended for interviews: The classic probabilistic skiplist is what interviewers usually expect. Implementing random levels shows understanding of probabilistic balancing and layered traversal. The basic implementation helps explain the concept, but the optimized random-level design demonstrates stronger design skills and efficient use of linked list structures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Basic Level Implementation | O(n) | O(n) | Learning the layered linked-list concept before adding probabilistic balancing |
| Advanced Probability-Based Skiplist | O(log n) average | O(n) | General implementation where probabilistic balancing keeps operations fast |
| Classic Random Level Skiplist | O(log n) average | O(n) | Most common interview implementation matching original skiplist design |
| Deterministic Balanced Skiplist | O(log n) | O(n) | Systems requiring predictable structure without randomness |