1206. Design Skiplist

• Time:
  • Constructor: $O(1)$
  • search(target: int): $O(\log n)$
  • add(num: int): $O(\log n)$
  • erase(num: int): $O(\log n)$
• Space: $O(|\texttt{add()}|)$

C++JavaPython

struct Node {
  int val = -1;
  shared_ptr<Node> next;
  shared_ptr<Node> down;
};

class Skiplist {
 public:
  bool search(int target) {
    for (shared_ptr<Node> node = dummy; node; node = node->down) {
      advance(node, target);
      if (node->next && node->next->val == target)
        return true;
    }
    return false;
  }

  void add(int num) {
    // Collect nodes that are before the insertion point.
    stack<shared_ptr<Node>> nodes;
    for (shared_ptr<Node> node = dummy; node; node = node->down) {
      advance(node, num);
      nodes.push(node);
    }

    shared_ptr<Node> down;
    bool shouldInsert = true;
    while (shouldInsert && !nodes.empty()) {
      shared_ptr<Node> prev = nodes.top();
      nodes.pop();
      prev->next = make_shared<Node>(num, prev->next, down);
      down = prev->next;
      shouldInsert = rand() % 2 == 1;
    }

    // Create a topmost new level dummy that points to the existing dummy.
    if (shouldInsert)
      dummy = make_shared<Node>(-1, nullptr, dummy);
  }

  bool erase(int num) {
    bool found = false;
    for (shared_ptr<Node> node = dummy; node; node = node->down) {
      advance(node, num);
      if (node->next && node->next->val == num) {
        node->next = node->next->next;
        found = true;
      }
    }
    return found;
  }

 private:
  shared_ptr<Node> dummy = make_shared<Node>(-1);

  void advance(shared_ptr<Node>& node, int target) {
    while (node->next && node->next->val < target)
      node = node->next;
  }
};

class Node {
  public int val;
  public Node next;
  public Node down;
  public Node(int val, Node next, Node down) {
    this.val = val;
    this.next = next;
    this.down = down;
  }
}

class Skiplist {
  public boolean search(int target) {
    for (Node node = dummy; node != null; node = node.down) {
      node = advance(node, target);
      if (node.next != null && node.next.val == target)
        return true;
    }
    return false;
  }

  public void add(int num) {
    // Collect nodes that are before the insertion point.
    Deque<Node> nodes = new ArrayDeque<>();
    for (Node node = dummy; node != null; node = node.down) {
      node = advance(node, num);
      nodes.push(node);
    }

    Node down = null;
    boolean shouldInsert = true;
    while (shouldInsert && !nodes.isEmpty()) {
      Node prev = nodes.poll();
      prev.next = new Node(num, prev.next, down);
      down = prev.next;
      shouldInsert = Math.random() < 0.5;
    }

    // Create a topmost new level dummy that points to the existing dummy.
    if (shouldInsert)
      dummy = new Node(-1, null, dummy);
  }

  public boolean erase(int num) {
    boolean found = false;
    for (Node node = dummy; node != null; node = node.down) {
      node = advance(node, num);
      if (node.next != null && node.next.val == num) {
        node.next = node.next.next;
        found = true;
      }
    }
    return found;
  }

  private Node dummy = new Node(-1, null, null);

  private Node advance(Node node, int target) {
    while (node.next != null && node.next.val < target)
      node = node.next;
    return node;
  }
}

from dataclasses import dataclass


@dataclass
class Node:
  val: int = -1
  next: 'Node' = None
  down: 'Node' = None


class Skiplist:
  def __init__(self):
    self.dummy = Node()

  def search(self, target: int) -> bool:
    node = self.dummy
    while node:
      while node.next and node.next.val < target:
        node = node.next
      if node.next and node.next.val == target:
        return True
      # Move to the next level
      node = node.down
    return False

  def add(self, num: int) -> None:
    # Collect nodes that are before the insertion point.
    nodes = []
    node = self.dummy
    while node:
      while node.next and node.next.val < num:
        node = node.next
      nodes.append(node)
      # Move to the next level
      node = node.down

    shouldInsert = True
    down = None
    while shouldInsert and nodes:
      node = nodes.pop()
      node.next = Node(num, node.next, down)
      down = node.next
      shouldInsert = random.getrandbits(1) == 0

    # Create a topmost new level dummy that points to the existing dummy.
    if shouldInsert:
      self.dummy = Node(-1, None, self.dummy)

  def erase(self, num: int) -> bool:
    node = self.dummy
    found = False
    while node:
      while node.next and node.next.val < num:
        node = node.next
      if node.next and node.next.val == num:
        # Delete the node
        node.next = node.next.next
        found = True
      # Move to the next level
      node = node.down
    return found

  # Move to the node s.t. node.next.val >= target
  def _advance(self, node: Node, target: int) -> None:
    while node.next and node.next.val < target:
      node = node.next