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, otherwise False.
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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import random

class Node:
    def __init__(self, value=0, levels=0):
        self.value = value
        self.next = [None] * levels

class Skiplist:
    def __init__(self):
        self.maxLevel = 16
        self.head = Node(levels=self.maxLevel)

    def search(self, target: int) -> bool:
        node = self.head
        for level in range(self.maxLevel - 1, -1, -1):
            while node.next[level] and node.next[level].value < target:
                node = node.next[level]
            if node.next[level] and node.next[level].value == target:
                return True
        return False

    def add(self, num: int) -> None:
        nodes = [None] * self.maxLevel
        node = self.head
        for level in range(self.maxLevel - 1, -1, -1):
            while node.next[level] and node.next[level].value < num:
                node = node.next[level]
            nodes[level] = node
        
        level = 0
        while random.randint(0, 1) and level < self.maxLevel - 1:
            level += 1

        newNode = Node(value=num, levels=level+1)
        for i in range(level+1):
            newNode.next[i] = nodes[i].next[i]
            nodes[i].next[i] = newNode

    def erase(self, num: int) -> bool:
        nodes = [None] * self.maxLevel
        node = self.head
        found = False
        for level in range(self.maxLevel - 1, -1, -1):
            while node.next[level] and node.next[level].value < num:
                node = node.next[level]
            nodes[level] = node
            if node.next[level] and node.next[level].value == num:
                found = True
                nodes[level].next[level] = node.next[level].next[level]
        
        return found

Here:

Node class defines the node structure.
Skiplist class contains methods for search, add, and erase.
We maintain different levels in head, with maxLevel 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.