What

probabilistic data structure that allows average complexity for search and insertion within a ordered sequence of n elements.
Not Cache friendly.

How

The idea: create multiple layers so that we can skip some nodes.

Why

Search in a sorted linked list better than time

Code

import random
 
class SkipNode:
    def __init__(self, value, level):
        """
		value: The value to be stored in the node.
		level: The level of this node (determines how many forward pointers it has).
			   A node at level 'k' has k+1 forward pointers (indices 0 to k).
        """
        self.value = value
        self.forward = [None] * (level + 1)
 
class SkipList:
    def __init__(self, max_level=16, p=0.5):
        """
		max_level (int): The maximum possible level for any node in the skip list.
						 This helps in pre-allocating the head node's forward pointers.
		p (float): The probability used to determine the level of a new node.
				   Typically 0.5 or 0.25.
        """
        self.max_level = max_level
        self.p = p  # Probability for a node to be promoted to the next level
        self.head = SkipNode(float('-inf'), self.max_level)
        self.level = 0
 
    def _random_level(self):
        lvl = 0
        while random.random() < self.p and lvl < self.max_level -1: # Corrected upper bound
            lvl += 1
        return lvl
 
    def search(self, value):
        """
		value: The value to search for.
		Returns: SkipNode: The node containing the value if found, otherwise None.
        """
        current = self.head
        for i in range(self.level, -1, -1):  # Iterate downwards from current max level
            # Move forward at the current level as long as the next node's value is less
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
 
        # After the loops, current is the node just before the potential position
        # of 'value' at level 0. Move to the actual node at level 0.
        current = current.forward[0]
 
        # Check if the node at level 0 has the target value
        if current and current.value == value:
            return current
        return None
 
    def insert(self, value):
        """
        Inserts a value into the skip list.
        If the value already exists, it's not inserted again (or you can modify to allow duplicates).
        Args:
            value: The value to insert.
        """
        # update[i] will store the pointer to the node that should precede
        # the new node at level i.
        update = [None] * (self.max_level + 1) # +1 to align with head's forward array size
        current = self.head
 
        # Find insertion points at each level
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current # current is the node whose forward[i] will be updated
 
        # current is now at level 0, pointing to the node before where 'value' should be.
        # Move to the node that would be right after the new node at level 0.
        current = current.forward[0]
 
        # If value already exists, do nothing (or handle as per requirement)
        if current and current.value == value:
            # print(f"Value {value} already exists. Not inserting.")
            return
 
        # Determine the level for the new node
        new_node_level = self._random_level()
 
        # If the new node's level is greater than the current highest level of the list,
        # update the list's level and initialize update pointers for new levels from head.
        if new_node_level > self.level:
            for i in range(self.level + 1, new_node_level + 1):
                update[i] = self.head # New levels start from head
            self.level = new_node_level # Update the list's current max level
 
        # Create the new node
        new_node = SkipNode(value, new_node_level)
 
        # Insert the new node by updating forward pointers
        for i in range(new_node_level + 1):
            # The new node's forward pointer at level i points to what update[i]'s
            # forward pointer at level i used to point to.
            new_node.forward[i] = update[i].forward[i]
            # Update update[i]'s forward pointer at level i to point to the new node.
            update[i].forward[i] = new_node
        
        # print(f"Inserted {value} at level {new_node_level}")
 
 
    def delete(self, value):
        """
		value: The value to delete.
		Returns: bool: True if the value was found and deleted, False otherwise.
        """
        update = [None] * (self.max_level + 1)
        current = self.head
 
        # Find the node to be deleted and its predecessors at each level
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current
 
        # current is now the predecessor of the node to be deleted (or where it would be) at level 0.
        # Move to the actual node that might contain the value.
        current = current.forward[0]
 
        # If the node is found
        if current and current.value == value:
            # Bypass the node at each level it exists in
            for i in range(len(current.forward)): # Iterate up to the level of the node being deleted
                # If update[i]'s forward pointer at level i is not the node to delete,
                # it means this level i is higher than the node's actual level, or
                # we are at a level where 'current' is not the direct successor of update[i].
                # This check is important.
                if update[i].forward[i] != current:
                    continue # Should not happen if logic is correct for finding update[]
                update[i].forward[i] = current.forward[i]
 
            # After deleting, check if any levels became empty and decrease self.level
            while self.level > 0 and self.head.forward[self.level] is None:
                self.level -= 1
            
            # print(f"Deleted {value}")
            return True
        
        # print(f"Value {value} not found for deletion.")
        return False