Design Skiplist
The design of a Skiplist can be achieved by using multiple levels of linked lists. The lower levels contain more elements, while the upper levels contain fewer elements. Let’s break down the implementation step by step.
Node Definition: We need a node structure that holds the value and references to the next node in the current level and the next node in the level below.
Initialization: Initialize the Skiplist with a header node that has links at every level.
Search Operation: Start from the top-left corner and move right as long as the next value is less than the target. When the next value is greater than or equal to the target, move down one level. Repeat this process until the bottom level is reached. Return
True
if the target is found, otherwiseFalse
.Add Operation: Similar to the search, find the appropriate position for the new number. Create a new node and insert it into the appropriate position. Then, with a certain probability, add the number to the level above. Repeat this process, promoting the number to each successive level with decreasing probability.
Erase Operation: Similar to the search, find the target node. Then remove the target node from each level where it appears.
Here’s the code:
|
|
Here:
Node
class defines the node structure.Skiplist
class contains methods for search, add, and erase.- We maintain different levels in
head
, withmaxLevel
being the maximum number of levels. - The search operation navigates through the levels to find a target.
- The add operation inserts a new node and randomly decides how many levels it should occupy.
- The erase operation removes the node from all levels where it appears.
This implementation ensures (O(\log n)) average time complexity for each operation and (O(n)) space complexity, where (n) is the number of elements in the Skiplist.