Leetcode 1206. Design Skiplist
Problem explanation
This problem requires us to build a skip list data structure that allows for fast search, add, and erase operations. The skip list is essentially a series of sorted linked lists, with each subsequent list skipping over a certain number of elements. This allows for fast operations as we can "skip" over many elements when performing searches, additions, or deletions, hence the name "skip list".
For example, suppose we have a skip list consisting of the numbers [30, 40, 50, 60, 70, 90]. If we were to add the number 45 into the skip list, it would be inserted between 40 and 50 in all the linked lists where these two numbers exist. This is because skip lists maintain sorted order of elements within each linked list.
This problem specifies three operations that need to be implemented in the skip list:
search(target)
: this should return whether a given target number exists in the skip list.add(num)
: this should insert a given number into the skip list.erase(num)
: this should remove a given number from the skip list. If the number does not exist in the skip list, nothing should be done and the function should returnfalse
. If multiple instances of the number exist in the skip list, only one instance needs to be removed.
Solution Walk-Through
The solution uses a Node
structure to represent individual elements of the skip list. Each node has a value and two pointers, next
and down
. next
points to the next node in the current linked list, whereas down
points to the node in the linked list below with the same value.
The SkipList
is implemented as a stack of linked lists. The top of the stack is a dummy node with a -1
value. This dummy node serves as a "sentinel" node that simplifies the code by eliminating the need to deal with edge cases where operations need to be performed on the first node in a linked list.
In search()
, we start from the top linked list and work our way down each linked list. In each linked list, we move forward until we reach a node whose next node has a value greater than or equal to the target. If we find a node with a value equal to the target, we return true
. If we have traversed all the linked lists and haven't found the target value, we return false
.
In add()
, we again start from the top linked list and work our way down until we reach the appropriate position for the new number in each linked list. As we find these positions, we keep track of the nodes preceding these positions in a stack. We then pop nodes from the stack and insert the new number after each popped node, linking the new nodes together using the down
pointers. There's a random element involved at this step, as we randomly decide whether to insert the new number into the next linked list down.
In erase()
, we iterate through each linked list and delete the first node with the given value that we find. If we don't find any node with the given value after traversing all linked lists, we return false
. If we have found and removed a node with the given value, we return true
.
Solution in Python
1 2python 3import random 4 5class Node: 6 def __init__(self, value=None, right=None, down=None): 7 self.value = value 8 self.right = right 9 self.down = down 10 11class Skiplist: 12 def __init__(self): 13 self.head = Node() 14 15 def search(self, target): 16 node = self.head 17 while node: 18 while node.right and node.right.value < target: 19 node = node.right 20 if node.right and node.right.value == target: 21 return True 22 node = node.down 23 return False 24 25 def add(self, num): 26 nodes = [] 27 node = self.head 28 while node: 29 while node.right and node.right.value < num: 30 node = node.right 31 nodes.append(node) 32 node = node.down 33 34 insert_up = True 35 down_node = None 36 while insert_up and nodes: 37 node = nodes.pop() 38 node.right = Node(num, node.right, down_node) 39 down_node = node.right 40 insert_up = (random.randint(0, 1) == 1) 41 42 if insert_up: 43 self.head = Node(None, None, self.head) 44 45 def erase(self, num): 46 node = self.head 47 found = False 48 while node: 49 while node.right and node.right.value < num: 50 node = node.right 51 if node.right and node.right.value == num: 52 node.right = node.right.right 53 found = True 54 node = node.down 55 return found
Solution in Java
1 2java 3public class Skiplist { 4 5 private Node head = new Node(0, 20); 6 7 public boolean search(int target) { 8 for (Node p = head; p != null; p = p.down) { 9 while (p.next != null && p.next.val < target) { 10 p = p.next; 11 } 12 if (p.next != null && p.next.val == target) { 13 return true; 14 } 15 } 16 return false; 17 } 18 19 public void add(int num) { 20 Node cur = head; 21 ArrayDeque<Node> stack = new ArrayDeque<>(); 22 for (; cur != null; cur = cur.down) { 23 while (cur.next != null && cur.next.val < num) { 24 cur = cur.next; 25 } 26 stack.push(cur); 27 } 28 boolean insertUp = true; 29 Node downNode = null; 30 while (insertUp && !stack.isEmpty()) { 31 Node node = stack.pop(); 32 node.next = new Node(num, node.next, downNode); 33 downNode = node.next; 34 insertUp = (Math.random() < 0.5); 35 } 36 if (insertUp) { 37 head = new Node(0, head); 38 } 39 } 40 41 public boolean erase(int num) { 42 boolean exists = false; 43 for (Node p = head; p != null; p = p.down) { 44 while (p.next != null && p.next.val < num) { 45 p = p.next; 46 } 47 if (p.next != null && p.next.val == num) { 48 exists = true; 49 p.next = p.next.next; 50 } 51 } 52 return exists; 53 } 54 55 class Node { 56 int val; 57 Node down; 58 Node next; 59 public Node(int val, Node next) { 60 this.val = val; 61 this.next = next; 62 } 63 public Node(int val, Node down, Node next) { 64 this.val = val; 65 this.down = down; 66 this.next = next; 67 } 68 } 69}
Solution in JavaScript
1 2javascript 3var Node = function(val, right=null, down=null) { 4 this.val = val === undefined ? 0 : val; 5 this.right = right; 6 this.down = down; 7} 8 9var Skiplist = function() { 10 this.head = new Node(); 11} 12 13Skiplist.prototype.search = function(target) { 14 let node = this.head; 15 while(node) { 16 // move right in the list 17 while(node.right && node.right.val < target) { 18 node = node.right; 19 } 20 // check the node 21 if(node.right && node.right.val === target) return true; 22 // move down in the list 23 node = node.down; 24 } 25 return false; 26} 27 28Skiplist.prototype.add = function(num) { 29 let nodes = []; 30 let node = this.head; 31 // traverse right and down, similar to search to find the spot 32 while(node) { 33 while(node.right && node.right.val < num) { 34 node = node.right; 35 } 36 nodes.push(node); 37 node = node.down 38 } 39 // insert nodes 40 let insertUp = true; 41 let downNode = null; 42 while(insertUp && nodes.length) { 43 node = nodes.pop(); 44 node.right = new Node(num, node.right, downNode); 45 downNode = node.right; 46 insertUp = Math.random() < 0.5; 47 } 48 // insert new head 49 if(insertUp) { 50 this.head = new Node(-1, null, this.head); 51 } 52} 53 54Skiplist.prototype.erase = function(num) { 55 let node = this.head; 56 let found = false; 57 while(node) { 58 while(node.right && node.right.val < num) { 59 node = node.right; 60 } 61 if(node.right && node.right.val === num) { 62 node.right = node.right.right; 63 found = true; 64 } 65 node = node.down; 66 } 67 return found; 68}
This JavaScript implementation follows the same logic as the Python and Java implementations. The Node constructor is defined to represent nodes in the skip list. The Skiplist constructor is used to initialize the head of the list. The search, add, and erase methods are implemented in the Skiplist prototype to carry out their respective operations on the skip list.
In JavaScript, we use the push()
function to add nodes to the nodes
array and pop()
to remove nodes from it. Similar to the Python and Java implementations, we use a while loop to traverse the nodes, and we use Math.random()
to randomly decide whether to insert into the next linked list down.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.