What
A 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