1206. Design Skiplist
Problem Description
The task is to design a Skiplist, a data structure that supports insertion, searching, and deletion operations in O(log(n))
average time complexity. In contrast with other data structures that offer similar performance, like treaps and red-black trees, Skiplists have the advantage of often being easier to implement. A Skiplist is essentially a set of multiple linked lists that together form a hierarchical structure with different levels. Each level is a linked list, and higher levels provide fast lanes for traversing the data structure quickly, as they skip over multiple elements in the lower levels.
The operations that need to be supported are as follows:
Skiplist()
: A constructor that initializes the skiplist.bool search(int target)
: Searches for a value in the skiplist and returnstrue
if the value is found andfalse
if it isn't.void add(int num)
: Inserts a value into the skiplist.bool erase(int num)
: Removes a value from the skiplist, returningtrue
if the operation is successful andfalse
if the value is not found.
The design should handle multiple occurrences of the same number, meaning duplicates are allowed.
Intuition
The intuition behind the Skiplist is to overlay multiple layers of linked lists to enable faster navigation for add
, search
, and erase
operations than would be possible in a standard single-level linked list. Each subsequent layer above the base layer has fewer nodes and skips over multiple nodes of the layer directly beneath it, creating shortcuts. In the context of highway systems, these can be thought of as express lanes where certain exits are skipped to allow for faster transit across long distances.
To implement these operations efficiently, a Node
class is defined, with each node having a val
and an array of pointers, next
, to the subsequent nodes at each level of the Skiplist. In a Skiplist, each node can potentially be part of multiple linked lists at different levels, rather than just one.
The search
operation starts from the top level and moves horizontally until it encounters a node with the next value greater than the target. It then moves down a level and continues this process until it reaches the bottom level to determine if the target exists in the list.
The add
operation involves creating a new node with randomly determined levels to insert it into all applicable levels, maintaining the sorting order.
The erase
operation finds and removes the node across all levels of the list where it exists.
Random level generation (for determining the number of levels a new node should be part of) is crucial as it impacts the balance and performance of the Skiplist. If too many nodes are at high levels, the benefits of skipping will be reduced, whereas too few can lead to numerous lower-level traversals, degenerating the structure to a basic linked list.
The provided solution code thus does the following:
- Manages the pointers between nodes at various levels to maintain the skiplist structure during additions, deletions, and searches.
- Chooses levels randomly during insertion (with an upper limit,
max_level
) to ensure that the average complexity remains logarithmic. - Iteratively performs each step, taking care to handle edge cases such as the need to update the skiplist levels after deletions.
Learn more about Linked List patterns.
Solution Approach
The Skiplist structure is implemented with a Node
class that holds a value and an array of pointers representing the nodes it points to at various levels. The Skiplist
class manages these nodes and performs operations upon them. Here's how the implementation takes shape:
-
Node Structure: Each
Node
consists of a value and an arraynext
that stores pointers to the nodes at various levels that come after the current node. The length of thenext
array determines how many levels the node is part of. -
Initialization: The Skiplist is initialized with a dummy head node at all levels up to
max_level
, which is set to a constant that determines the maximum number of levels a node can have. The actual number of levels a Skiplist is using is stored inself.level
, which starts at 0 and increases as higher-level nodes are added. -
Search Operation: To
search
for a target value, the algorithm starts from the highest level of the head node and traverses to the right until it encounters a node with a value greater than the target. It then drops down one level and continues this process until it either finds the target (returningtrue
) or reaches the bottom level (returningfalse
if the target is not found). -
Random Level Generation: The
random_level
function determines the level of a new node being added by using a loop that continues promoting the level with a probability defined byp
until the level reachesmax_level
or the promotion stops randomly. -
Insertion: The
add
function inserts a node by first determining the random level for the new node. Starting from the top level of the head node, it finds the appropriate spot to insert the node at every level up to the node's level. It rearranges pointers such that eachnext
pointer at a level less than the node's level points to the new node, and the corresponding pointer in the new node points to the next node in the sequence. -
Deletion: The
erase
function searches for the node with the matching value starting from the top level, and if found, rearranges pointers at every level to bypass the node being deleted. If a node is removed, the function also adjusts theself.level
of the Skiplist if the top levels become empty. -
Level Adjustment: After any erase operation, the levels of the skiplist are checked to see if the top level is unused (no nodes except the head). If so, the level is decremented, which helps to keep the skiplist from having unnecessary empty levels at the top.
This implementation takes advantage of the "fast lane" concept with multiple levels of linked lists to provide efficient logarithmic-time operations on average, mimicking what binary search trees offer but in a more lightweight fashion that leverages randomness for balancing.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach for implementing a Skiplist. Consider we are working with a Skiplist that has a max_level
of 3.
-
Initialization: When the Skiplist is created, a dummy head node is initialized with a
next
pointer array of sizemax_level
. Initially, all thenext
pointers point toNone
, indicating that the Skiplist is empty. -
Adding Elements: Let's begin by inserting the numbers 3, 6, and 9 into the Skiplist.
-
When adding
3
, suppose therandom_level
function decides that the new node will only be at level 1 (0-indexed). The new node with value3
is inserted right after the head node at level 1. The Skiplist now looks something like this:Level 2: head -> None Level 1: head -> [3] -> None Level 0: head -> [3] -> None
-
We add
6
next, and let's say it's also added at level 1. The Skiplist updates to:Level 2: head -> None Level 1: head -> [3] -> [6] -> None Level 0: head -> [3] -> [6] -> None
-
Finally, we add
9
, and it is determined to be at level 2. It gets inserted at each level up to level 2:Level 2: head -> [9] -> None Level 1: head -> [3] -> [6] -> [9] -> None Level 0: head -> [3] -> [6] -> [9] -> None
-
-
Searching: Let's search for the number
6
in the Skiplist. The search starts at the highest level (level 2):- At Level 2, the head points directly to
9
, which is greater than6
. So, we go down to the next level (1). - At Level 1, the head points to
3
, and3
points to6
. Since6
is the number we are searching for, we returntrue
.
- At Level 2, the head points directly to
-
Erasing Elements: To erase the number
6
, the operation will start at the highest level (level 2) and work its way down:-
At Level 2, there's no node before
9
that points to6
, so we move down to Level 1. -
At Level 1,
3
points to6
, and6
points to9
. We remove6
and update3
to point to9
. The Skiplist now looks like:Level 2: head -> [9] -> None Level 1: head -> [3] -> [9] -> None Level 0: head -> [3] -> [9] -> None
-
If the removed node happened to be the highest-level node, the Skiplist would also need to update the
self.level
to reflect the removed level.
-
This example demonstrates how a Skiplist can provide logarithmic time complexity for add
, search
, and erase
operations by employing multiple levels of linked lists and using randomization to maintain balance within the structure.
Solution Implementation
1import random
2
3class Node:
4 def __init__(self, value: int, level: int):
5 """
6 Initialize a Node with a given value and level.
7 The level corresponds to the number of forward references (pointers)
8 it has to other nodes.
9 """
10 self.value = value
11 self.next = [None] * level
12
13class Skiplist:
14 MAX_LEVEL = 32 # Maximum level for the skip list
15 P = 0.25 # Probability factor for determining the level of a new node
16
17 def __init__(self):
18 """
19 Initialize the SkipList with a head node of maximum level, setting
20 the current level to 0.
21 """
22 self.head = Node(-1, self.MAX_LEVEL)
23 self.current_level = 0
24
25 def search(self, target: int) -> bool:
26 """
27 Search for a target element in the skip list. Returns True if the
28 element is found, False otherwise.
29 """
30 current = self.head
31 # Traverse from the top level of the skip list down to the bottom
32 for i in range(self.current_level - 1, -1, -1):
33 # Move to the node closest to the target at the current level
34 current = self._find_closest(current, i, target)
35 # Check if the target is found at the current level
36 if current.next[i] and current.next[i].value == target:
37 return True
38 return False
39
40 def add(self, num: int) -> None:
41 """
42 Add a new element to the skip list.
43 """
44 current = self.head
45 new_node_level = self._random_level()
46 new_node = Node(num, new_node_level)
47 # Update the skip list's current level if necessary
48 self.current_level = max(self.current_level, new_node_level)
49 for i in range(self.current_level - 1, -1, -1):
50 current = self._find_closest(current, i, num)
51 # Link the new node if the level is less than the new node's level
52 if i < new_node_level:
53 new_node.next[i] = current.next[i]
54 current.next[i] = new_node
55
56 def erase(self, num: int) -> bool:
57 """
58 Erase an element from the skip list. Returns True if the element was
59 successfully removed, False if it was not found.
60 """
61 current = self.head
62 removed = False
63 # Try to find and remove the node with the given value
64 for i in range(self.current_level - 1, -1, -1):
65 current = self._find_closest(current, i, num)
66 if current.next[i] and current.next[i].value == num:
67 # Skip over the to-be-removed node
68 current.next[i] = current.next[i].next[i]
69 removed = True
70 # Adjust the skip list level if the top level is now empty
71 while self.current_level > 1 and self.head.next[self.current_level - 1] is None:
72 self.current_level -= 1
73 return removed
74
75 def _find_closest(self, current: Node, level: int, target: int) -> Node:
76 """
77 Find the node at the specified level whose value is closest to,
78 but not greater than, the target.
79 """
80 while current.next[level] and current.next[level].value < target:
81 current = current.next[level]
82 return current
83
84 def _random_level(self) -> int:
85 """
86 Randomly determine the level for a new node.
87 """
88 level = 1
89 # Use a geometric distribution with probability P to determine the level
90 while level < self.MAX_LEVEL and random.random() < self.P:
91 level += 1
92 return level
93
94# Example usage:
95# skiplist = Skiplist()
96# skiplist.add(1)
97# print(skiplist.search(1)) # Output: True
98# skiplist.erase(1)
99# print(skiplist.search(1)) # Output: False
100
1import java.util.Random;
2
3public class Skiplist {
4
5 // Maximum level for the skiplist
6 private static final int MAX_LEVEL = 32;
7 // Probability for the randomLevel method
8 private static final double PROBABILITY = 0.25;
9 // Random number generator for generating levels
10 private static final Random random = new Random();
11
12 // The head node of the skiplist
13 private final Node head = new Node(-1, MAX_LEVEL);
14
15 // Current level of the skiplist
16 private int level = 0;
17
18 public Skiplist() {
19 }
20
21 // Search for a value in the skiplist
22 public boolean search(int target) {
23 Node current = head;
24 for (int i = level - 1; i >= 0; --i) {
25 current = findClosest(current, i, target);
26 if (current.next[i] != null && current.next[i].value == target) {
27 // We found the target value
28 return true;
29 }
30 }
31 // Target value not found
32 return false;
33 }
34
35 // Add a value to the skiplist
36 public void add(int num) {
37 Node current = head;
38 int newLevel = randomLevel();
39 Node newNode = new Node(num, newLevel);
40 // Potentially increase skiplist current level
41 level = Math.max(level, newLevel);
42 for (int i = level - 1; i >= 0; --i) {
43 current = findClosest(current, i, num);
44 if (i < newLevel) {
45 newNode.next[i] = current.next[i];
46 current.next[i] = newNode;
47 }
48 }
49 }
50
51 // Erase a value from the skiplist
52 public boolean erase(int num) {
53 Node current = head;
54 boolean found = false;
55 for (int i = level - 1; i >= 0; --i) {
56 current = findClosest(current, i, num);
57 if (current.next[i] != null && current.next[i].value == num) {
58 // Remove the node
59 current.next[i] = current.next[i].next[i];
60 found = true;
61 }
62 }
63 // Reduce the level of the skiplist if needed
64 while (level > 1 && head.next[level - 1] == null) {
65 --level;
66 }
67 return found;
68 }
69
70 // Find the node closest to a given value at a given level
71 private Node findClosest(Node current, int levelIndex, int target) {
72 while (current.next[levelIndex] != null && current.next[levelIndex].value < target) {
73 current = current.next[levelIndex];
74 }
75 return current;
76 }
77
78 // Randomly determine the level for a new node
79 private static int randomLevel() {
80 int newLevel = 1;
81 while (newLevel < MAX_LEVEL && random.nextDouble() < PROBABILITY) {
82 ++newLevel;
83 }
84 return newLevel;
85 }
86
87 // Inner class to represent a node in the skiplist
88 static class Node {
89 int value;
90 Node[] next;
91
92 Node(int value, int level) {
93 this.value = value;
94 this.next = new Node[level];
95 }
96 }
97}
98
99/**
100 * The Skiplist class can be used as follows:
101 * Skiplist skiplist = new Skiplist();
102 * boolean isFound = skiplist.search(target); // Search for 'target' in the skiplist
103 * skiplist.add(number); // Add 'number' to the skiplist
104 * boolean isErased = skiplist.erase(number); // Remove 'number' from the skiplist
105 */
106
1#include <vector>
2#include <climits>
3#include <algorithm>
4using namespace std;
5
6// Definition of a single Node in the skip list.
7struct Node {
8 int value;
9 vector<Node*> forward; // Pointers to next nodes in different levels
10 Node(int val, int lvl) : value(val), forward(lvl, nullptr) {}
11};
12
13class Skiplist {
14private:
15 static const int probability = RAND_MAX / 4; // Probability of level increase
16 static const int maxLevel = 32; // The maximum level a node can have
17 Node* head; // Pointer to the first node (header) of the skip list
18 int currentLevel; // Current maximum level of the skip list
19
20public:
21 Skiplist() {
22 head = new Node(-1, maxLevel);