DSA Notes

Hub Algorithm vs Data Structure - Key Differences Real-World Applications of DSA Time and Space Complexity Overview What is DSA? Data Structures and Algorithms Why Learn Data Structures and Algorithms Asymptotic Analysis - Understanding Algorithm Growth Best, Average, and Worst Case Analysis Big O Notation - Upper Bound Analysis Big Omega Notation - Lower Bound Analysis Big Theta Notation - Tight Bound Analysis Space Complexity - Memory Analysis Time Complexity Examples and Analysis Array Interview Problems and Solutions Array Operations - Insert, Delete, Search Array Rotation Techniques Array Searching Techniques Arrays - Fundamental Data Structure Dynamic Arrays - Flexible Sizing Multidimensional Arrays - 2D and Beyond Sliding Window Technique for Arrays Anagram Problems - Character Rearrangement Palindrome Problems and Solutions Pattern Searching in Strings String Interview Problems Collection String Matching Algorithms - Pattern Searching String Operations - Concatenation, Substring, Manipulation String Data Structure - Fundamentals Circular Linked List - Ring Structure Doubly Linked List - Bidirectional Traversal Linked List Interview Problems Linked List - Data Structure Fundamentals Linked List Operations - Insert, Delete, Reverse Reverse Linked List - Iterative and Recursive Singly Linked List - Implementation and Operations Balanced Parentheses - Stack Application Infix, Prefix, Postfix Expressions - Stack Application Stack Implementation Techniques Stack Interview Problems and Solutions Stack Data Structure - LIFO Principle Stack using Arrays - Static Implementation Stack using Linked Lists - Dynamic Implementation Circular Queue - Efficient Space Usage Deque (Double Ended Queue)Priority Queue - Custom Ordering Queue Applications - Real-World Use Cases Queue Implementation - Array and Linked List Queue Interview Problems and Solutions Queue Data Structure - FIFO Principle AVL Tree - Self-Balancing Binary Search Tree Binary Search Tree (BST)Binary Tree - Structure and Operations Fenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BST Segment Tree - Range Query Data Structure Tree Interview Problems Collection Tree Data Structure Fundamentals Tree Traversals - Inorder, Preorder, Postorder, Level Order Heap Data Structure Heap Operations Heap Interview Problems Max-Heap Min-Heap Implementation and Use Cases Priority Queue using Heap Bellman-Ford Algorithm Breadth-First Search (BFS) Algorithm Depth-First Search (DFS) Algorithm Dijkstra\Floyd-Warshall Algorithm Graph Interview Problems Graph Data Structure Fundamentals Graph Representation Methods Kruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete Comparison Topological Sorting Union-Find (Disjoint Set Union)Separate Chaining Collision Handling Hash Functions Hashing Fundamentals Hashing Interview Problems Open Addressing Bubble Sort - Simple Sorting Algorithm Counting Sort - Non-Comparison Sorting Heap Sort - Heap Based Sorting Insertion Sort - Build Sorted Array Merge Sort - Divide and Conquer Quick Sort - Partition Based Sorting Radix Sort - Digit Based Sorting Selection Sort - Selection Based Sorting Sorting Algorithms Comparison - Choosing the Right Algorithm Sorting Algorithms - Fundamentals and Concepts Binary Search - Efficient Searching Interpolation Search - Intelligent Searching Linear Search - Sequential Search Algorithm Search Algorithms Comparison Searching Algorithm Interview Problems Ternary Search Algorithm Backtracking with Recursion Recursion Fundamentals - Base Case and Recurrence Recursion Problems and Solutions Recursion Tree - Visualizing Function Calls Recursion vs Iteration - Comparing Approaches Tail Recursion - Optimization Technique Dynamic Programming Interview Problems Dynamic Programming Fundamentals Fibonacci with Dynamic Programming 0/1 Knapsack Problem Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain Multiplication Memoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection Problem Fractional Knapsack Greedy Interview Problems Greedy Algorithm Fundamentals Huffman Coding — Data Structures & Algorithms Job Sequencing with Deadlines Backtracking Fundamentals Backtracking Practice Problems N-Queens Problem Rat in a Maze Subset Generation Sudoku Solver Codeforces Guide for Competitive Programmers Common Competitive Programming Techniques Contest Strategies for Competitive Programming Competitive Programming Introduction Fast Input/Output for Competitive Programming LeetCode Guide for Interview Preparation Bit Manipulation - Advanced Techniques Bloom Filter - Probabilistic Data Structure Computational Geometry - Algorithms and Techniques Disjoint Set Union (DSU) - Union Find Randomized Algorithms - Probabilistic Computing Skip List - Probabilistic Balanced Structure Suffix Array - String Indexing Trie - Prefix Tree for Efficient Searching Autocomplete System Using Trie Library Management System Using DSA Route Finder Using Graphs Mini Search Engine Project Social Network Analysis Using Graphs Essential Coding Patterns for Interviews DSA Cheatsheet: Quick Reference Essential DSA Interview Questions FAANG DSA Sheet: Company-Specific Patterns and Problems Problem Solving Strategies for Coding Interviews Complexity Cheatsheet Important Algorithms Summary Best Practice Platforms for DSA Recommended Books for DSA

Skip List - Probabilistic Balanced Structure

Learn skip lists as probabilistic alternative to balanced trees.

What is a Skip List?

A Skip List is a probabilistic data structure that provides O(log n) average-case performance for search, insertion, and deletion operations. It is an alternative to balanced binary search trees (AVL trees, Red-Black trees) that achieves balance through randomization rather than complex rotation rules.

Think of a skip list like an express train system. The bottom level has every station (every element in sorted order). Higher levels skip some stations, acting like express lines. To find a station, you start on the highest express line and drop down levels as needed. This gives you logarithmic search time without the complexity of tree rebalancing.

Implementation in Python

Example

import random class SkipNode: def __init__(self, key, level): self.key = key self.forward = [None] * (level + 1) # Forward pointers for each level class SkipList: def __init__(self, max_level=16, p=0.5): self.max_level = max_level self.p = p self.level = 0 # Current highest level self.header = SkipNode(-float('inf'), max_level) self.size = 0 def random_level(self): """Generate random level using coin flips""" lvl = 0 while random.random() < self.p and lvl < self.max_level: lvl += 1 return lvl def search(self, key): """Search for a key, O(log n) expected""" current = self.header for i in range(self.level, -1, -1): while current.forward[i] and current.forward[i].key < key: current = current.forward[i] current = current.forward[0] return current is not None and current.key == key def insert(self, key): """Insert a key, O(log n) expected""" update = [None] * (self.max_level + 1) current = self.header # Find position at each level for i in range(self.level, -1, -1): while current.forward[i] and current.forward[i].key < key: current = current.forward[i] update[i] = current current = current.forward[0] # If key already exists, skip if current and current.key == key: return # Generate random level for new node new_level = self.random_level() # Update max level if needed if new_level > self.level: for i in range(self.level + 1, new_level + 1): update[i] = self.header self.level = new_level # Create and insert new node new_node = SkipNode(key, new_level) for i in range(new_level + 1): new_node.forward[i] = update[i].forward[i] update[i].forward[i] = new_node self.size += 1 def delete(self, key): """Delete a key, O(log n) expected""" update = [None] * (self.max_level + 1) current = self.header for i in range(self.level, -1, -1): while current.forward[i] and current.forward[i].key < key: current = current.forward[i] update[i] = current current = current.forward[0] if current and current.key == key: for i in range(self.level + 1): if update[i].forward[i] != current: break update[i].forward[i] = current.forward[i] # Reduce level if needed while self.level > 0 and self.header.forward[self.level] is None: self.level -= 1 self.size -= 1 return True return False def display(self): """Print skip list levels""" for i in range(self.level, -1, -1): node = self.header.forward[i] print(f"Level {i}: ", end="") while node: print(f"{node.key} -> ", end="") node = node.forward[i] print("None") # Usage sl = SkipList() for val in [3, 6, 7, 9, 12, 19, 17, 26, 21, 25]: sl.insert(val) sl.display() print(f"Search 19: {sl.search(19)}") # True print(f"Search 15: {sl.search(15)}") # False sl.delete(19) print(f"After delete 19: {sl.search(19)}") # False

Complexity Analysis

Operation	Average Case	Worst Case	Space
Search	O(log n)	O(n)	-
Insert	O(log n)	O(n)	O(log n) per node
Delete	O(log n)	O(n)	-
Space (total)	O(n)	O(n log n)	-

The expected number of levels is O(log n) with probability p = 1/2. Each node has an expected 2 forward pointers (1 + 1/2 + 1/4 + ... = 2), so total expected space is O(n).

Skip List vs Balanced BSTs

Feature	Skip List	AVL/Red-Black Tree
Implementation complexity	Simple	Complex (rotations)
Concurrency	Easy to lock-free	Difficult
Cache performance	Good (sequential)	Poor (pointer chasing)
Worst case guarantee	No (probabilistic)	Yes (deterministic)
Range queries	Natural (forward pointers)	Requires in-order traversal
Space overhead	~2 pointers per node (avg)	2-3 pointers per node
Insertion/Deletion	No rebalancing needed	Rotations required

Why Skip Lists Matter in Practice

Skip lists are used in production systems because of their simplicity and excellent concurrent behavior:

Redis — The sorted set data structure in Redis is implemented using skip lists. Redis chose skip lists over balanced trees because they are simpler to implement, easier to debug, and support range queries naturally.

LevelDB/RocksDB — Google's LevelDB uses skip lists for its in-memory component (memtable). The simplicity and good cache behavior make them ideal for this use case.

Apache Lucene — The search engine library uses skip lists in its posting list structure for fast boolean query processing.

Concurrent programming — Lock-free skip lists are simpler to implement than lock-free balanced trees, making them popular in concurrent data structures.

The Probability Parameter (p)

The promotion probability p affects the trade-off between space and time:

p value	Expected levels	Space per node	Search time
1/2	log₂(n)	2 pointers	O(log n)
1/4	log₄(n)	4/3 pointers	O(log n)
1/e	logₑ(n)	e/(e-1) pointers	O(log n)

p = 1/2 is most common. p = 1/4 uses less space at the cost of slightly more comparisons per search.

Interview Questions

Q1: Why choose a skip list over a balanced BST? A: Skip lists are simpler to implement (no rotations), easier to make concurrent (lock-free variants), and support range queries naturally via forward pointers. Choose them when implementation simplicity or concurrency matters more than worst-case guarantees.

Q2: What is the expected height of a skip list with n elements? A: O(log n) with high probability. Specifically, with p = 1/2, the expected max level is log₂(n).

Q3: Can a skip list degrade to O(n) performance? A: Yes, if all coin flips result in level 0 (extremely unlikely). The probability of this is (1-p)^n, which is astronomically small for any reasonable n.

Q4: How does Redis use skip lists? A: Redis sorted sets (ZSET) use a skip list combined with a hash map. The skip list maintains sorted order for range queries and ranking, while the hash map provides O(1) lookups by member name.

Q5: How would you implement a lock-free skip list? A: Use CAS (Compare-And-Swap) operations for pointer updates. Mark nodes for deletion before physically removing them. The layered structure means conflicts are localized to specific levels, reducing contention compared to tree rotations.

Key Takeaways

Skip lists achieve O(log n) operations through randomization rather than complex rebalancing
They are simpler to implement than AVL or Red-Black trees
They excel in concurrent programming due to easy lock-free implementations
Redis and LevelDB use skip lists in production for their sorted data structures
The trade-off is probabilistic rather than deterministic guarantees

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Skip List - Probabilistic Balanced Structure.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.

Search Terms

data-structures-algorithms, data structures & algorithms, data, structures, algorithms, advanced, topics, skip

Related Data Structures & Algorithms Topics

Continue learning this concept

Advanced TopicsBit Manipulation - Advanced TechniquesMaster bit manipulation techniques, bitwise operations, bit masking, and advanced binary algorithms for competitive programming and interviews.Advanced TopicsBloom Filter - Probabilistic Data StructureLearn about Bloom filters, a space-efficient probabilistic data structure for set membership testing with constant-time operations.Advanced TopicsComputational Geometry - Algorithms and TechniquesMaster computational geometry concepts, geometric algorithms, and problem-solving techniques.Advanced TopicsDisjoint Set Union (DSU) - Union FindMaster DSU with path compression and union by rank for efficient operations.Advanced TopicsRandomized Algorithms - Probabilistic ComputingExplore randomized algorithms and probabilistic approaches.Advanced TopicsSuffix Array - String IndexingEfficient string indexing and pattern matching with suffix arrays.

PreviousRandomized Algorithms - Probabilistic Computing NextSuffix Array - String Indexing