Skip List

Skip List is a probabilistic data structure that allows for efficient search, insertion, and deletion operations. It is similar to a linked list, but with multiple layers of linked lists (known as "levels") that act as shortcuts, making the search process faster.

To understand the Skip List, let's start by implementing the basic operations: search, insert, and delete.

1. Node Class: First, we'll define a Node class that represents a node in the Skip List. Each node contains a value and a list of pointers to the next nodes at each level.

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

1. Skip List Class: Next, we'll define the SkipList class that will implement the operations.

class SkipList:
    def __init__(self):
        self.head = Node()  # Create a dummy head node
        self.max_level = 1  # Initialize the maximum level of the Skip List

    def search(self, target):
        # Start from the top-level and move down
        curr = self.head
        for level in range(self.max_level - 1, -1, -1):
            # Traverse the current level until finding a node with a greater or equal value
            while curr.next[level] and curr.next[level].val < target:
                curr = curr.next[level]

        # Move to the next node at the bottom level
        curr = curr.next[0]

        # Check if the target value is found
        if curr and curr.val == target:
            return True
        else:
            return False

    def insert(self, num):
        # Generate the level for the new node
        level = self._generate_level()

        # Create a new node with the given value
        new_node = Node(num)

        # Update the head's next pointers if the new node has a higher level
        if level > self.max_level:
            for _ in range(self.max_level, level):
                self.head.next.append(None)
            self.max_level = level

        # Start from the top-level and move down
        curr = self.head
        for i in range(self.max_level - 1, -1, -1):
            # Traverse the current level until finding a node with a greater or equal value
            while curr.next[i] and curr.next[i].val < num:
                curr = curr.next[i]

            # Insert the new node at the current level
            if i < level:
                new_node.next.append(curr.next[i])
                curr.next[i] = new_node

    def delete(self, num):
        # Start from the top-level and move down
        curr = self.head
        for i in range(self.max_level - 1, -1, -1):
            # Traverse the current level until finding a node with a greater or equal value
            while curr.next[i] and curr.next[i].val < num:
                curr = curr.next[i]

            # Delete the node with the target value at the current level
            if curr.next[i] and curr.next[i].val == num:
                curr.next[i] = curr.next[i].next[i]

    def _generate_level(self):
        # Generate a random level for a new node
        level = 1
        while level < self.max_level and random.random() < 0.5:
            level += 1
        return level

In the SkipList class, we initialize the Skip List with a dummy head node and set the maximum level to 1. The search method performs a search operation by traversing the levels and nodes until finding the target value. The insert method inserts a new node into the Skip List, considering the node's level and updating the pointers accordingly. The delete method deletes a node with a specific value by updating the pointers.

Now, let's solve a problem from LeetCode using the Skip List.

Problem: "Design Skiplist" Design a Skiplist data structure that supports the standard operations (search, insert, delete) and efficiently utilizes the Skip List concept.

You can find the problem details and constraints here: https://leetcode.com/problems/design-skiplist/

Here's the complete code for the "Design Skiplist" problem:

import random


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


class Skiplist:
    def __init__(self):
        self.head = Node()
        self.max_level = 1

    def search(self, target):
        curr = self.head
        for level in range(self.max_level - 1, -1, -1):
            while curr.next[level] and curr.next[level].val < target:
                curr = curr.next[level]

        curr = curr.next[0]

        if curr and curr.val == target:
            return True
        else:
            return False

    def add(self, num):
        level = self._generate_level()
        new_node = Node(num)

        if level > self.max_level:
            for _ in range(self.max_level, level):
                self.head.next.append(None)
            self.max_level = level

        curr = self.head
        for i in range(self.max_level - 1, -1, -1):
            while curr.next[i] and curr.next[i].val < num:
                curr = curr.next[i]

            if i < level:
                new_node.next.append(curr.next[i])
                curr.next[i] = new_node

    def erase(self, num):
        curr = self.head
        for i in range(self.max_level - 1, -1, -1):
            while curr.next[i] and curr.next[i].val < num:
                curr = curr.next[i]

            if curr.next[i] and curr.next[i].val == num:
                curr.next[i] = curr.next[i].next[i]

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

The Skiplist class implements the Skip List data structure with the search, insert, and delete operations. We use the Node class defined earlier.

The time complexity of the Skip List operations is as follows:

• Search: O(log N), where N is the number of elements in the Skip List.
• Insert: O(log N), where N is the number of elements in the Skip List.
• Delete: O(log N), where N is the number of elements in the Skip List.

The space complexity of the Skip List is O(N), where N is the number of elements in the Skip List, as we store each element in a separate node.

By using the Skip List data structure, we can achieve efficient search, insert, and delete operations with a time complexity that is logarithmic with respect to the number of elements in the list.