LeetCode Solutions Blog

Design Skiplist

Difficulty: Hard

Problem Description

Design a Skiplist, a data structure that allows for efficient insertion, deletion, and search operations in O(log(n)) time complexity. The Skiplist consists of multiple layers of sorted linked lists, where each layer allows for skipping over elements to improve performance.

Key Insights

A Skiplist uses multiple layers of linked lists to create a probabilistic data structure that allows for fast search, insertion, and deletion.
Each layer can be thought of as a sorted linked list, where the top layers allow for skipping over multiple elements in the lower layers, enabling logarithmic time complexity.
The average time complexity for search, add, and erase operations is O(log(n)), while the space complexity is O(n).

Space and Time Complexity

Time Complexity: O(log(n)) for search, add, and erase operations on average.
Space Complexity: O(n), where n is the number of elements in the Skiplist.

Solution

To implement the Skiplist, we will use a linked list structure where each node contains a value and references to multiple forward nodes (representing the levels in the Skiplist). The number of levels for each node is determined randomly, allowing for efficient traversal. The key operations are:

Search: Traverse from the highest level down to the lowest, moving forward until the target is found or we reach a node with a forward reference that is null.
Add: Insert a new node at the appropriate level(s) based on the random level generation. This involves finding the correct position at each level and inserting the node.
Erase: Similar to search, traverse to find the node and then adjust the forward references to remove the node from the list.

Code Solutions

import random

class SkiplistNode:
    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * (level + 1)

class Skiplist:
    def __init__(self):
        self.max_level = 16  # Maximum level for the Skiplist
        self.header = SkiplistNode(-1, self.max_level)
        self.level = 0

    def random_level(self):
        level = 0
        while random.random() < 0.5 and level < self.max_level:
            level += 1
        return level

    def search(self, target):
        current = self.header
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < target:
                current = current.forward[i]
        current = current.forward[0]
        return current is not None and current.value == target

    def add(self, num):
        update = [None] * (self.max_level + 1)
        current = self.header
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < num:
                current = current.forward[i]
            update[i] = current
        current = current.forward[0]

        if current is None or current.value != num:
            new_level = self.random_level()
            if new_level > self.level:
                for i in range(self.level + 1, new_level + 1):
                    update[i] = self.header
                self.level = new_level

            new_node = SkiplistNode(num, new_level)
            for i in range(new_level + 1):
                new_node.forward[i] = update[i].forward[i]
                update[i].forward[i] = new_node

    def erase(self, num):
        update = [None] * (self.max_level + 1)
        current = self.header
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < num:
                current = current.forward[i]
            update[i] = current
        current = current.forward[0]

        if current is not None and current.value == num:
            for i in range(self.level + 1):
                if update[i].forward[i] != current:
                    break
                update[i].forward[i] = current.forward[i]

            while self.level > 0 and self.header.forward[self.level] is None:
                self.level -= 1
            return True
        return False