Skip List
Introduction
Skip Lists were introduced by William Pugh in 1989 as an alternative to balanced binary search trees. Instead of performing rotations or rebalancing, Skip Lists use multiple linked levels to achieve efficient searching.
Why Do We Need Skip List?
Searching in a normal linked list requires traversing every node, resulting in O(n) time complexity. Skip Lists introduce multiple shortcut levels that allow large portions of the list to be skipped, reducing the average search complexity to O(log n).
Real-Life Example
Imagine searching a word in a dictionary. Instead of checking every page one by one, you first jump to the appropriate alphabet section and then narrow your search. Skip Lists follow a similar principle by allowing jumps through higher levels before moving to lower levels.
Properties of Skip List
- Probabilistic Data Structure.
- Multiple linked-list levels.
- Higher levels contain fewer nodes.
- Searching starts from the topmost level.
- No tree rotations are required.
- Average complexity is O(log n).
- Simple implementation.
Basic Structure of Skip List
Figure 1 : Multi-level Skip List.
| Component | Description |
|---|---|
| Header | Starting node of all levels. |
| Level | Horizontal linked list. |
| Node | Stores key and forward pointers. |
| Forward Pointer | Points to the next node at the same level. |
| Bottom Level | Contains all elements. |
Node Structure in Skip List
Each Skip List node contains the data value and one or more forward pointers. The number of forward pointers depends upon the randomly assigned level of the node.
| Field | Description |
|---|---|
| Key | Stores the actual value. |
| Forward[] | Array of pointers to the next nodes. |
| Level | Maximum level occupied by the node. |
Levels in Skip List
A Skip List consists of multiple horizontal linked lists. The bottom level (Level 0) contains every element. Each higher level contains fewer nodes, allowing the search operation to skip multiple nodes at once.
- Level 3 : 13 → 37 → 55
- Level 2 : 7 → 13 → 37 → 55
- Level 1 : 3 → 7 → 13 → 19 → 37 → 43 → 55 → 61
- Level 0 : All elements
Searching in Skip List
Searching begins from the highest level. Move horizontally while the next node is smaller than the search key. Whenever the next node becomes larger than the required key, move vertically down one level. Continue until the key is found or the bottom level is reached.
Figure 2 : Searching Key = 19
Search Algorithm
current ← Header
for level = HighestLevel downto 0
while current→next.key < Key
current ← current→next
Move Down
if current→next.key == Key
Return FOUND
else
Return NOT FOUND
Worked Example
| Step | Current Node | Action |
|---|---|---|
| 1 | Header | Start from highest level. |
| 2 | 13 | Move Right. |
| 3 | 37 | 19 < 37, Move Down. |
| 4 | 13 | Move Right. |
| 5 | 19 | Key Found. |
Insertion in Skip List
Insertion first searches the correct position. The new node is always inserted at Level 0. A random process (coin flip) determines whether the node is promoted to higher levels. This probabilistic balancing keeps the Skip List efficient.
Figure 3 : Inserting Key = 19
Insertion Algorithm
Search correct position
Insert node at Level 0
Flip Coin
while Heads
Promote node to next level
Stop when Tail occurs
Deletion in Skip List
Deletion in a Skip List begins by locating the node using the search algorithm. Once the required node is found, it is removed from every level in which it appears. Unlike balanced trees, Skip Lists do not require rotations or restructuring after deletion.
Figure 4 : Deleting Key = 19 from a Skip List.
Deletion Algorithm
Search the required key
Store predecessor nodes
If key exists
Remove the node from every level
Update forward pointers
If highest level becomes empty
Reduce current maximum level
Deletion Example
| Step | Operation |
|---|---|
| 1 | Search Key = 19 |
| 2 | Locate node at all levels |
| 3 | Update forward pointers |
| 4 | Delete node from every level |
| 5 | Skip List remains balanced |
Time Complexity Analysis
The average performance of a Skip List is comparable to balanced binary search trees. However, its implementation is considerably simpler.
Figure 5 : Complexity Analysis of Skip List.
| Operation | Average Case | Worst Case |
|---|---|---|
| Search | O(log n) | O(n) |
| Insertion | O(log n) | O(n) |
| Deletion | O(log n) | O(n) |
| Space | O(n) | O(n) |
Average vs Worst Case
Because Skip Lists use randomization, the average performance is extremely efficient. Although the theoretical worst case is O(n), such cases occur with very low probability.
- Search → O(log n)
- Insertion → O(log n)
- Deletion → O(log n)
Worst Case
- Search → O(n)
- Insertion → O(n)
- Deletion → O(n)
Why is Skip List Efficient?
- Multiple shortcut levels reduce traversal.
- Higher levels contain fewer nodes.
- Randomized balancing avoids expensive rotations.
- Searching begins from the highest level.
- Simple linked-list implementation.
Comparison of Skip List with Other Data Structures
Skip Lists offer the simplicity of linked lists while achieving search performance comparable to balanced binary search trees.
Figure 6 : Skip List Comparison with Linked List and Binary Search Tree.
| Feature | Linked List | Binary Search Tree | Skip List |
|---|---|---|---|
| Searching | O(n) | O(log n) | O(log n) |
| Insertion | O(1) | O(log n) | O(log n) |
| Deletion | O(1) | O(log n) | O(log n) |
| Balancing Required | No | Yes | No |
| Implementation | Very Easy | Difficult | Easy |
Applications of Skip List
Skip Lists are widely used in applications that require efficient searching, insertion and deletion while maintaining simple implementation.
Figure 7 : Real-world Applications of Skip List.
- Database Indexing
- Redis In-Memory Database
- Apache Lucene Search Engine
- Concurrent Data Structures
- Distributed Systems
- Routing Tables
- Dictionary Applications
- Caching Systems
- Memory Management
- High-Performance Searching
Advantages of Skip List
- Simple implementation.
- No rotations or rebalancing.
- Average O(log n) searching.
- Efficient insertion and deletion.
- Supports dynamic datasets.
- Easy to implement compared to AVL Trees.
- Good cache performance.
Disadvantages of Skip List
- Worst-case complexity is O(n).
- Requires additional forward pointers.
- Performance depends upon randomization.
- Consumes more memory than linked lists.
Frequently Asked Interview Questions
- What is a Skip List?
- Why is Skip List called a probabilistic data structure?
- Explain searching in Skip List.
- Explain insertion in Skip List.
- Explain deletion in Skip List.
- Differentiate Skip List and Linked List.
- Differentiate Skip List and AVL Tree.
- What is the average complexity of Skip List?
- Where is Skip List used?
- Why doesn't Skip List require balancing?
AKTU Examination Questions
- Explain the structure of Skip List with a neat diagram.
- Describe the searching algorithm of Skip List.
- Explain insertion and deletion with suitable examples.
- Derive the time complexity of Skip List.
- Compare Skip List with AVL Tree.
- Compare Skip List with Linked List.
- Discuss the applications of Skip List.
Practice Questions
- Create a Skip List for the keys 5, 12, 18, 25, 32 and 40.
- Perform search operation for key 25.
- Insert key 30 into the Skip List.
- Delete key 18 from the Skip List.
- Compare Skip List with Binary Search Tree.
Key Takeaways
- Skip List is a probabilistic data structure.
- Searching begins from the highest level.
- Higher levels help skip unnecessary nodes.
- Average complexity is O(log n).
- No rotations or balancing operations are required.
- Simple implementation with excellent performance.
Summary
A Skip List is an efficient probabilistic data structure that supports searching, insertion and deletion in average O(log n) time. It combines the simplicity of linked lists with performance comparable to balanced binary search trees by maintaining multiple levels of forward pointers. Due to its simplicity and excellent average performance, Skip Lists are widely used in modern databases, search engines and concurrent systems.