Design Skiplist

hard skiplist linked list randomization

Problem

Design a Skiplist without using any built-in libraries. It must support search(target), add(num), and erase(num), all in expected O(log n) time. A skiplist keeps the data sorted and stacks several randomized "express lanes" of linked lists on top of one another; searching starts at the top lane and drops down a level whenever the next node would overshoot the target.

Inputadd(1), add(2), add(3), search(0), add(4), search(1), erase(0), erase(1), search(1)

Output[null, null, null, false, null, true, false, true, false]

search(0) is false (0 was never added); search(1) is true until erase(1) removes it, after which search(1) is false again.

sorted values in skiplist (comma-separated)

search target

import random

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

class Skiplist:
    MAX_LEVEL = 16

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

    def _random_level(self):
        lvl = 1
        while random.random() < 0.5 and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl

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

    def add(self, num):
        update = [self.head] * self.MAX_LEVEL
        cur = self.head
        for i in range(self.level - 1, -1, -1):
            while cur.next[i] and cur.next[i].val < num:
                cur = cur.next[i]
            update[i] = cur
        lvl = self._random_level()
        if lvl > self.level:
            self.level = lvl
        node = Node(num, lvl)
        for i in range(lvl):
            node.next[i] = update[i].next[i]
            update[i].next[i] = node

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

class Node {
  constructor(val, levels) {
    this.val = val;
    this.next = new Array(levels).fill(null);
  }
}

class Skiplist {
  constructor() {
    this.MAX = 16;
    this.head = new Node(-1, this.MAX);
    this.level = 1;
  }

  randomLevel() {
    let lvl = 1;
    while (Math.random() < 0.5 && lvl < this.MAX) lvl++;
    return lvl;
  }

  search(target) {
    let cur = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (cur.next[i] && cur.next[i].val < target) cur = cur.next[i];
    }
    cur = cur.next[0];
    return cur !== null && cur.val === target;
  }

  add(num) {
    const update = new Array(this.MAX).fill(this.head);
    let cur = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (cur.next[i] && cur.next[i].val < num) cur = cur.next[i];
      update[i] = cur;
    }
    const lvl = this.randomLevel();
    if (lvl > this.level) this.level = lvl;
    const node = new Node(num, lvl);
    for (let i = 0; i < lvl; i++) {
      node.next[i] = update[i].next[i];
      update[i].next[i] = node;
    }
  }

  erase(num) {
    const update = new Array(this.MAX).fill(null);
    let cur = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (cur.next[i] && cur.next[i].val < num) cur = cur.next[i];
      update[i] = cur;
    }
    const t = cur.next[0];
    if (t === null || t.val !== num) return false;
    for (let i = 0; i < this.level; i++) {
      if (update[i].next[i] === t) update[i].next[i] = t.next[i];
    }
    return true;
  }
}

class Skiplist {
    static final int MAX = 16;
    static class Node {
        int val;
        Node[] next;
        Node(int val, int levels) { this.val = val; this.next = new Node[levels]; }
    }
    Node head = new Node(-1, MAX);
    int level = 1;
    Random rng = new Random();

    int randomLevel() {
        int lvl = 1;
        while (rng.nextDouble() < 0.5 && lvl < MAX) lvl++;
        return lvl;
    }

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

    public void add(int num) {
        Node[] update = new Node[MAX];
        Arrays.fill(update, head);
        Node cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < num) cur = cur.next[i];
            update[i] = cur;
        }
        int lvl = randomLevel();
        if (lvl > level) level = lvl;
        Node node = new Node(num, lvl);
        for (int i = 0; i < lvl; i++) {
            node.next[i] = update[i].next[i];
            update[i].next[i] = node;
        }
    }

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

class Skiplist {
    static const int MAX = 16;
    struct Node {
        int val;
        vector<Node*> next;
        Node(int v, int levels) : val(v), next(levels, nullptr) {}
    };
    Node* head;
    int level;

    int randomLevel() {
        int lvl = 1;
        while ((rand() & 1) && lvl < MAX) lvl++;
        return lvl;
    }
public:
    Skiplist() { head = new Node(-1, MAX); level = 1; }

    bool search(int target) {
        Node* cur = head;
        for (int i = level - 1; i >= 0; i--)
            while (cur->next[i] && cur->next[i]->val < target) cur = cur->next[i];
        cur = cur->next[0];
        return cur != nullptr && cur->val == target;
    }

    void add(int num) {
        vector<Node*> update(MAX, head);
        Node* cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur->next[i] && cur->next[i]->val < num) cur = cur->next[i];
            update[i] = cur;
        }
        int lvl = randomLevel();
        if (lvl > level) level = lvl;
        Node* node = new Node(num, lvl);
        for (int i = 0; i < lvl; i++) {
            node->next[i] = update[i]->next[i];
            update[i]->next[i] = node;
        }
    }

    bool erase(int num) {
        vector<Node*> update(MAX, nullptr);
        Node* cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur->next[i] && cur->next[i]->val < num) cur = cur->next[i];
            update[i] = cur;
        }
        Node* t = cur->next[0];
        if (!t || t->val != num) return false;
        for (int i = 0; i < level; i++)
            if (update[i]->next[i] == t) update[i]->next[i] = t->next[i];
        return true;
    }
};

Explanation

A skiplist is a clever twist on a sorted linked list. Walking a plain sorted list to find a value is slow because you must step one node at a time. The skiplist adds express lanes on top that let you skip over many nodes at once, giving you O(log n) search.

Each node has a stack of forward pointers, one per level. The bottom level (level 0) contains every value in order. Higher levels contain fewer and fewer nodes. When you insert with add, _random_level flips a coin to decide how tall the new node is — roughly half the nodes reach level 1, a quarter reach level 2, and so on. This randomness keeps the lanes balanced on average without any rebalancing logic.

Searching always starts at the top lane of the head sentinel. On each level you move right while the next value is still less than the target; the moment the next node would overshoot, you drop down one level and continue. At the bottom you check whether the node right after the cursor equals the target.

Both add and erase reuse that same descent, but they record an update array — the last node visited on every level. Those are exactly the nodes whose pointers must be rewired to splice the new node in or unlink the deleted one.

Example: searching for 19 in [3,7,12,19,25,30] starts high and skips past several small values in one hop, drops a level when the next node would exceed 19, and lands exactly on 19 at level 0 — returning true. Searching for 0 falls off the front and returns false.

Time: O(log n) expected per op Space: O(n)