What is a Skip List?
A Skip List is a data structure that extends the concept of a linked list by adding multiple levels of pointers that allow faster traversal. It maintains elements in sorted order and allows efficient searching, insertion, and deletion. Skip lists are an alternative to balanced trees and are often used in databases and memory caches.
The fundamental idea behind a skip list is to build multiple layers of linked lists, where each higher layer acts as an express lane for elements, skipping over some elements in the lower layers. This helps reduce the number of steps required to find an element.
Skip List Structure
A skip list consists of multiple levels of linked lists:
- The bottom level contains all the elements in sorted order (like a normal linked list).
- The higher levels contain a subset of elements, each linking further ahead in the list.
- The topmost level contains the fewest elements, offering the fastest traversal.
Each node in a skip list contains:
- A key (value of the element).
- Multiple forward pointers pointing to different levels.
- A random level assigned to the node.
What is the Time Complexity with Two Layers?
If a linked list is sorted, searching takes O(n) time because we traverse one node at a time. However, if we introduce two layers, we improve the time complexity significantly.
Consider a linked list with n elements and a second layer where we have √n elements (acting as shortcut pointers). Searching in the second layer takes O(√n) steps, and then searching the remaining nodes in the first layer also takes O(√n). Hence, the overall time complexity reduces to O(√n).
With more layers, the time complexity improves further, approaching O(log n) in an optimized skip list.
Working of the Skip List
A skip list is a layered data structure that allows faster search, insertion, & deletion operations compared to a regular linked list. It achieves this by creating multiple levels of linked lists, where higher levels "skip" over larger portions of data.
How Does It Work?
1. Layered Structure: A skip list consists of multiple levels of linked lists. The bottom level (Level 0) is a standard linked list containing all the elements in sorted order. Each higher level acts as an "express lane" that skips over some elements, making searches faster.
2. Randomized Levels: When a new element is inserted, its level is determined randomly. For example, a coin flip decides whether the element should be promoted to the next level. This randomization ensures the skip list remains balanced without complex rebalancing algorithms.
3. Search Operation: To search for an element, the skip list starts from the topmost level & moves right until it finds a value greater than the target. It then drops down to the next level & repeats the process until the element is found or determined to be absent.
4. Insertion Operation: To insert an element, the skip list first searches for the correct position in the bottom level. Once found, the element is inserted, & its level is determined randomly. If the element is promoted to higher levels, it’s linked accordingly.
5. Deletion Operation: To delete an element, the skip list searches for it across all levels & removes it from each level where it appears.
Example: Implementing a Skip List
import random
class Node:
def __init__(self, val, level):
self.val = val
self.next = [None] (level + 1)
class SkipList:
def __init__(self, max_level):
self.max_level = max_level
self.head = Node(-1, 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 insert(self, val):
update = [None] (self.max_level + 1)
current = self.head
for i in range(self.level, -1, -1):
while current.next[i] and current.next[i].val < val:
current = current.next[i]
update[i] = current
new_level = self.random_level()
if new_level > self.level:
for i in range(self.level + 1, new_level + 1):
update[i] = self.head
self.level = new_level
new_node = Node(val, new_level)
for i in range(new_level + 1):
new_node.next[i] = update[i].next[i]
update[i].next[i] = new_node
def search(self, val):
current = self.head
for i in range(self.level, -1, -1):
while current.next[i] and current.next[i].val < val:
current = current.next[i]
current = current.next[0]
return current and current.val == val
def delete(self, val):
update = [None] (self.max_level + 1)
current = self.head
for i in range(self.level, -1, -1):
while current.next[i] and current.next[i].val < val:
current = current.next[i]
update[i] = current
current = current.next[0]
if current and current.val == val:
for i in range(self.level + 1):
if update[i].next[i] != current:
break
update[i].next[i] = current.next[i]
while self.level > 0 and self.head.next[self.level] is None:
self.level -= 1
You can also try this code with Online Python Compiler
Example Usage
skip_list = SkipList(3)
skip_list.insert(3)
skip_list.insert(6)
skip_list.insert(7)
skip_list.insert(9)
skip_list.insert(12)
print("Search 6:", skip_list.search(6))
print("Search 8:", skip_list.search(8))
skip_list.delete(6)
print("Search 6 after deletion:", skip_list.search(6))
You can also try this code with Online Python Compiler
Output
True
False
False
In this Code:
1. Node Class:
Each node contains a value & a list of pointers (`next`) to nodes at different levels.
2. SkipList Class:
`max_level`: The maximum number of levels the skip list can have.
`head`: The starting point of the skip list.
`level`: The current highest level in use.
3. Insert Operation:
The `insert` method finds the correct position for the new value & inserts it at the appropriate levels based on randomization.
4. Search Operation:
The `search` method starts from the top level & moves right until it finds the target or determines it’s not present.
5. Delete Operation:
The `delete` method removes the node from all levels where it appears.
Example Representation of Skip List
Level 3: [ ] ---> [15] ----------------> [ ]
Level 2: [ ] ---> [7] ---> [15] -----> [25] ---> [ ]
Level 1: [3] ---> [7] ---> [15] -----> [25] ---> [30] ---> [ ]
Level 0: [1] ---> [3] ---> [7] ---> [8] ---> [15] ---> [20] ---> [25] ---> [30] ---> [ ]
Skip List Basic Operations
Skip lists support three primary operations: search, insert, & delete. Each operation is designed to take advantage of the layered structure to achieve efficient performance. Let’s understand each operation in detail.
1. Search Operation
The search operation is used to find whether a specific value exists in the skip list. This is how it works:
- Start from the topmost level of the skip list.
- Move right at the current level until you find a value greater than the target.
- Drop down to the next level & repeat the process.
- When you reach the bottom level, check if the next node contains the target value.
Example for Search Operation
def search(self, val):
current = self.head
for i in range(self.level, -1, -1): Start from the top level
while current.next[i] and current.next[i].val < val:
current = current.next[i] Move right at the current level
current = current.next[0] Move to the bottom level
return current and current.val == val Check if the value matches
You can also try this code with Online Python Compiler
Explanation:
- The search starts at the top level & moves right until it finds a value greater than the target.
- It then drops down to the next level & repeats the process.
- At the bottom level, it checks if the value exists.
2. Insert Operation
The insert operation adds a new value to the skip list while maintaining its sorted order & layered structure. This is how it works:
- Start from the top level & move right until you find the correct position for the new value.
- Insert the new value at the bottom level.
- Randomly determine the number of levels the new value should occupy.
- Link the new value to the appropriate nodes at each level.
Example for Insert Operation
def insert(self, val):
update = [None] (self.max_level + 1) To store nodes to update
current = self.head
Find the correct position for the new value
for i in range(self.level, -1, -1):
while current.next[i] and current.next[i].val < val:
current = current.next[i]
update[i] = current
Randomly determine the number of levels for the new node
new_level = self.random_level()
If the new node has more levels than the current skip list, update the skip list
if new_level > self.level:
for i in range(self.level + 1, new_level + 1):
update[i] = self.head
self.level = new_level
Create the new node
new_node = Node(val, new_level)
Link the new node to the appropriate nodes at each level
for i in range(new_level + 1):
new_node.next[i] = update[i].next[i]
update[i].next[i] = new_node
You can also try this code with Online Python Compiler
Explanation:
- The `update` array stores the nodes that need to be updated at each level.
- The new node’s level is determined randomly using the `random_level` method.
- The new node is linked to the appropriate nodes at each level.
3. Delete Operation
The delete operation removes a value from the skip list while maintaining its structure. Let’s see how it works:
- Start from the top level & move right until you find the node to delete.
- Remove the node from all levels where it appears.
- Update the pointers of the previous nodes to bypass the deleted node.
Example for Delete Operation
def delete(self, val):
update = [None] (self.max_level + 1) To store nodes to update
current = self.head
Find the node to delete
for i in range(self.level, -1, -1):
while current.next[i] and current.next[i].val < val:
current = current.next[i]
update[i] = current
current = current.next[0] Move to the bottom level
If the node is found, remove it from all levels
if current and current.val == val:
for i in range(self.level + 1):
if update[i].next[i] != current:
break
update[i].next[i] = current.next[i] Bypass the deleted node
Reduce the skip list's level if necessary
while self.level > 0 and self.head.next[self.level] is None:
self.level -= 1
You can also try this code with Online Python Compiler
Explanation:
- The `update` array stores the nodes that need to be updated at each level.
- The node is removed from all levels where it appears.
- The skip list’s level is reduced if the top level becomes empty.
Applications of the Skip List
1. Databases & Indexing
Skip lists are used in databases to implement indexes, which speed up search queries. For example, a database can use a skip list to index employee IDs, allowing quick access to specific records. Skip lists provide O(log n) average time complexity for search, insertion, & deletion, making them ideal for maintaining dynamic indexes. They are also easier to implement & maintain compared to balanced trees like AVL or Red-Black trees.
2. Concurrent Data Structures
Skip lists are widely used in concurrent programming because they allow multiple threads to perform operations simultaneously without heavy locking mechanisms. For example, Java’s `ConcurrentSkipListMap` is a concurrent implementation of a skip list. Skip lists use probabilistic balancing, which reduces the need for complex rebalancing operations, making them more suitable for multi-threaded environments.
3. Priority Queues
Skip lists can be used to implement priority queues, where elements are stored in sorted order & the highest-priority element is accessed first. For example, in a task scheduling system, tasks can be stored in a skip list based on their priority. The scheduler can quickly retrieve & execute the highest-priority task. Skip lists maintain elements in sorted order, making them efficient for dynamic priority queues.
4. File Systems
Skip lists are used in some file systems to manage metadata & directory structures. For example, in a distributed file system, skip lists can index file blocks, allowing quick access to specific blocks during read/write operations. Skip lists provide efficient search & update operations, making them suitable for managing file system metadata.
5. Networking & Routing Tables
Skip lists are used in networking to manage routing tables, which store information about paths to different network destinations. For example, in a router, skip lists can store IP addresses & their corresponding next-hop information. When a packet arrives, the router quickly looks up the destination IP in the skip list to determine the next hop. Skip lists provide fast lookups & updates, making them ideal for dynamic routing tables.
6. Memory Allocation
Skip lists are used in memory allocators to manage free memory blocks efficiently. For example, in a memory allocator, skip lists can store free memory blocks sorted by size. When a program requests memory, the allocator quickly finds a suitable block using the skip list. Skip lists allow efficient search & update operations, making them more dynamic than other data structures like binary heaps.
Advantages of Skip List
- Faster search time - Searching takes O(log n) time, making it efficient.
- Simpler implementation - Easier to implement than balanced trees.
- Efficient insertions and deletions - Similar O(log n) time complexity as search.
- Flexible design - Can be adjusted dynamically with different levels.
- Used in memory-efficient applications - Found in databases, in-memory storage, and indexing systems.
Disadvantages of Skip List
- Extra memory usage - Requires additional pointer storage for multiple levels.
- Randomized level assignment - Performance depends on randomization.
- Complexity in maintenance - Keeping levels balanced can be tricky.
Frequently Asked Questions
Where is Skip List used in real applications?
Skip lists are widely used in databases, distributed systems, and caches such as Redis for fast key-value lookups.
Why do we use random levels in a Skip List?
Random levels help in distributing elements across multiple layers efficiently, ensuring O(log n) performance without manual balancing.
How does Skip List compare to a Binary Search Tree?
Both offer O(log n) search time, but Skip List is easier to implement and does not require strict balancing, unlike a Binary Search Tree.
Conclusion
In this article, we discussed about the Skip List data structure, which is an optimized version of a linked list that allows fast search, insertion, and deletion operations using multiple levels of linked lists. Skip lists use probabilistic balancing instead of rebalancing like balanced trees, making them efficient for dynamic data and database indexing. Understanding skip lists helps in improving algorithm efficiency and data retrieval speed.
19+ registered 
