Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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.

Solution

A Skiplist is a data structure that allows for fast insertion, deletion, and search by maintaining multiple layers of sorted linked lists. Each higher layer levels up randomly and contains a subset of the elements from the lower level, making searching operations more efficient by skipping over large numbers of elements at once.

Method 1 - Designing with custom node class

Here is the approach:

  1. Node Class: Define a Node class to store the value and references to the nodes in different levels.
  2. Skiplist Class:
    • Initialization: Set up the Skiplist with a predefined maximum level and a head node that acts as the start of the Skiplist.
    • Random Level: Implement a method to randomly determine the level of a new node.
    • Search: Implement a method to search for a target value in the Skiplist by traversing from the top level down.
    • Add: Implement a method to add a value to the Skiplist, adjusting the levels and pointers accordingly.
    • Erase: Implement a method to remove a value from the Skiplist by updating the pointers of the nodes in different levels.

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

class Skiplist {
    class Node {
        int val;
        Node[] next;

        public Node(int val, int size) {
            this.val = val;
            this.next = new Node[size];
        }
    }

    private static final int MAX_LEVEL = 16;
    private final Node head;
    private final Random rand;
    private int level;

    public Skiplist() {
        this.head = new Node(-1, MAX_LEVEL);
        this.rand = new Random();
        this.level = 1;
    }

    public boolean search(int target) {
        Node curr = head;
        for (int i = level - 1; i >= 0; i--) {
            while (curr.next[i] != null && curr.next[i].val < target) {
                curr = curr.next[i];
            }
        }
        curr = curr.next[0];
        return curr != null && curr.val == target;
    }

    public void add(int num) {
        Node curr = head;
        Node[] update = new Node[MAX_LEVEL];
        for (int i = level - 1; i >= 0; i--) {
            while (curr.next[i] != null && curr.next[i].val < num) {
                curr = curr.next[i];
            }
            update[i] = curr;
        }
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level; i < newLevel; i++) {
                update[i] = head;
            }
            level = newLevel;
        }
        Node newNode = new Node(num, newLevel);
        for (int i = 0; i < newLevel; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
    }

    public boolean erase(int num) {
        Node curr = head;
        Node[] update = new Node[MAX_LEVEL];
        for (int i = level - 1; i >= 0; i--) {
            while (curr.next[i] != null && curr.next[i].val < num) {
                curr = curr.next[i];
            }
            update[i] = curr;
        }
        curr = curr.next[0];
        if (curr == null || curr.val != num) {
            return false;
        }
        for (int i = 0; i < level; i++) {
            if (update[i].next[i] != curr) {
                break;
            }
            update[i].next[i] = curr.next[i];
        }
        while (level > 1 && head.next[level - 1] == null) {
            level--;
        }
        return true;
    }

    private int randomLevel() {
        int lvl = 1;
        while (lvl < MAX_LEVEL && rand.nextInt(2) == 1) {
            lvl++;
        }
        return lvl;
    }
}
 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
52
53
54
55
56
57
58
59
60
61

class Node:
    def __init__(self, val: int, size: int):
        self.val = val
        self.next = [None] * size

class Skiplist:
    MAX_LEVEL = 16

    def __init__(self):
        self.head = Solution.Node(-1, self.MAX_LEVEL)
        self.level = 1
        self.random = random.Random()

    def search(self, target: int) -> bool:
        curr = self.head
        for i in range(self.level - 1, -1, -1):
            while curr.next[i] and curr.next[i].val < target:
                curr = curr.next[i]
        curr = curr.next[0]
        return curr is not None and curr.val == target

    def add(self, num: int) -> None:
        update = [None] * self.MAX_LEVEL
        curr = self.head
        for i in range(self.level - 1, -1, -1):
            while curr.next[i] and curr.next[i].val < num:
                curr = curr.next[i]
            update[i] = curr
        new_level = self.random_level()
        if new_level > self.level:
            for i in range(self.level, new_level):
                update[i] = self.head
            self.level = new_level
        new_node = Solution.Node(num, new_level)
        for i in range(new_level):
            new_node.next[i] = update[i].next[i]
            update[i].next[i] = new_node

    def erase(self, num: int) -> bool:
        update = [None] * self.MAX_LEVEL
        curr = self.head
        for i in range(self.level - 1, -1, -1):
            while curr.next[i] and curr.next[i].val < num:
                curr = curr.next[i]
            update[i] = curr
        curr = curr.next[0]
        if curr is None or curr.val != num:
            return False
        for i in range(self.level):
            if update[i].next[i] != curr:
                break
            update[i].next[i] = curr.next[i]
        while self.level > 1 and self.head.next[self.level - 1] is None:
            self.level -= 1
        return True

    def random_level(self) -> int:
        lvl = 1
        while lvl < self.MAX_LEVEL and self.random.randint(0, 1):
            lvl += 1
        return lvl

Complexity

  • ⏰ Time complexity: The time complexity for search, add, and erase operations is O(log(n)) on average due to the probabilistic balancing. The worst-case time complexity is O(n), but this happens very rarely due to the random level mechanism.
  • 🧺 Space complexity: O(n) where n is the number of elements in the Skiplist.