This is a leetcode problem Design Skiplist. In this article, let's see what it is, how it works and implement it in code.

Consider this problem: given a list of element then search the target from them.

The simplest way is just a for loop, then the time complexity is O(n). How to make it faster? Well, we can make the list sorted and then use an approach called Binary Search, then the time complexity becomes O(log(n)).

But we still have a problem. What if we want to add/remove element from the list? Because we store the element in an array, add/remove element would be heavy. We may need to move a bunch of memory for one element add/remove.

So what data structure could support fast search and also light add/remove? Binary search tree is one answer. Because binary search tree has a balancing problem, so there are some upgraded version such as AVL Tree or Red Black Tree.

So what is this skiplist then? Well skiplist is another answer for fast search and light add/remove. It just use the simple data structure linked list and simpler than the previous tree structure solutions.

For a simple linked list, we can't access nodes directly. So even we have this linked list sorted, we can't use the binary search way to make the time complexity O(log(n)). For example, if the target is 7, then we need to iterate all the nodes before node 7.

1 -> 3 -> 5 -> 7 -> 9

The idea of skip list is to add shortcuts between elements. So if we make the linked list as below, then we first go to node 5, then go to node 7.

1 ------> 5 ------> 9
1 -> 3 -> 5 -> 7 -> 9

Instead of one level of shortcuts, we could make more if the the number of elements become bigger.

1 ----------------> 5 ----------------> 9
1 ------> 3 ------> 5 ------> 7 ------> 9
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

What can you see fromt these shortcuts? Yes, binary search. Just like binary search, we go from higher level to lower level, the time complexity becomes O(log(n)).

So the search is done. How about add/remove? When we add an element, if we want to make the shortcuts balanced as the original one, then we may need to adjust a lot of shortcuts. This is not what we want. Actually we don't need to make the shortcuts balanced as above. We can just decide to make shortcuts by flipping coins. So for each level, we have 50% probability to make a new short cuts, then the overall complexity is the same.

There is a gif in wiki which shows the process of adding a new element and adding shortcuts by flipping coins. Follow it and you should know the exact process.

Now let see the code.

class SkiplistNode {
    val: number;
    next: SkiplistNode | null; // go next(same level)
    down: SkiplistNode | null; // go down(one level down)

    constructor(val: number, next: SkiplistNode | null, down: SkiplistNode | null) {
        this.val = val;
        this.next = next;
        this.down = down;
    }
}

class Skiplist {
    head: SkiplistNode;
    constructor() {
        // head is a dummy node for start
        this.head = new SkiplistNode(-1, null, null);
    }

    search(target: number): boolean {
        let cur: SkiplistNode | null = this.head;
        while(cur !== null) {
            // cur lower than target, go next
            while(cur.next !== null && cur.next.val < target) {
                cur = cur.next;
            }
            // next equals to target, found
            if (cur.next !== null && cur.next.val === target) {
                return true;
            }
            // next bigger than target, go down
            cur = cur.down;
        }
        return false;
    }

    add(num: number): void {
        let cur: SkiplistNode | null = this.head;

        // keep track of stops on each level
        let stops: SkiplistNode[] = [];
        while(cur !== null) {
            while(cur.next !== null && cur.next.val < num) {
                cur = cur.next;
            }
            stops.push(cur);
            cur = cur.down;
        }

        // keep poping nodes from stops
        // flip coin to decide if new link should be added
        let shouldInsert = true;
        let down: SkiplistNode | null = null;
        while(shouldInsert) {
            const node = stops.pop();
            if (node === undefined) break;

            // insert newNode between node and node.next
            const newNode = new SkiplistNode(num, node.next, down);
            node.next = newNode;

            // keep track of previous newNode as next newNode's down
            down = newNode;

            // flip coin to decide if added another link is needed
            shouldInsert = (Math.random() < 0.5);
        }

        // if there is new link between head and the newNode
        // then a new dummy head is added(new level)
        if (shouldInsert) {
            this.head = new SkiplistNode(-1, null, this.head);
        }
    }

    erase(num: number): boolean {
        let cur: SkiplistNode | null = this.head;
        let isFound = false;
        // same logic as in search
        while(cur !== null) {
            while(cur.next !== null && cur.next.val < num) {
                cur = cur.next;
            }
            // found target, delete node
            if (cur.next !== null && cur.next.val === num) {
                isFound = true;
                cur.next = cur.next.next;
            }
            cur = cur.down;
        }
        return isFound;
    }
}