skiplist_example.C File Reference

Skip List: A probabilistic alternative to balanced trees. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <vector>
#include <set>
#include <tpl_dynSkipList.H>
#include <tclap/CmdLine.h>

Include dependency graph for skiplist_example.C:

Go to the source code of this file.

Functions
void	demonstrate_basic_operations ()
	Demonstrate basic Skip List operations.
void	demonstrate_string_set ()
	Demonstrate skip list with strings.
void	demonstrate_functional ()
	Demonstrate functional programming features.
void	benchmark_comparison (size_t n, unsigned seed, bool verbose)
	Benchmark skip list vs std::set.
void	visualize_structure ()
	Visualize skip list structure (small example)
int	main (int argc, char *argv[])

Detailed Description

Skip List: A probabilistic alternative to balanced trees.

This example demonstrates Skip Lists, an elegant randomized data structure invented by William Pugh in 1990. Skip Lists provide expected O(log n) performance for search, insert, and delete operations without the complexity of balanced tree rotations, making them easier to implement and understand.

What is a Skip List?

A Skip List is a probabilistic data structure that uses multiple sorted linked lists at different "levels" to enable fast search. Think of it as a subway system with express trains (higher levels) and local trains (lower levels).

How Skip Lists Work

Structure

A Skip List consists of multiple linked lists (levels):

• Level 0: Contains ALL elements in sorted order (base level)
• Level 1: Contains ~50% of elements (express lane)
• Level 2: Contains ~25% of elements (super express)
• Level i: Contains ~(1/2)^i of elements

Example Structure

For elements {3, 6, 7, 9}:

Level 2:  HEAD -------------------------> 6 -------------------------> NIL
Level 1:  HEAD ---------> 3 ---------> 6 ---------> 9 ---------> NIL
Level 0:  HEAD -> 3 -> 6 -> 7 -> 9 -> NIL

Search Algorithm

1. Start at highest level (HEAD)
2. Move right while next element < target
3. If can't go right, go down one level
4. Repeat until found or reach level 0

Key insight: Higher levels act as "express lanes" allowing you to skip over many elements quickly.

Insertion Algorithm

1. Search for insertion point (as in search)
2. Insert at level 0
3. "Flip a coin" (random): With 50% probability, promote to level 1
4. If promoted, flip again for level 2, etc.
5. Stop when coin flip fails

Randomization: Each element has 50% chance of being at level i+1 if it's at level i. This creates the probabilistic structure.

Advantages Over Balanced Trees

Simplicity

• No rotations: Unlike AVL or Red-Black trees
• No rebalancing: Structure maintained probabilistically
• Easier to implement: Simpler code, fewer edge cases
• Easier to debug: Linear structure easier to visualize

Concurrency

• Skip lists are often used as a basis for concurrent sets/maps
• This example demonstrates a single-threaded container API

Performance

• Expected O(log n): Same as balanced trees
• Good constants: Often faster in practice

Flexibility

• Ordered iteration: Efficient in-order traversal via iterators
• Dynamic: Easy to add/remove levels

Disadvantages

❌ Probabilistic: No worst-case guarantee (though extremely unlikely) ❌ Memory overhead: Multiple pointers per element ❌ Randomization: Requires good random number generator

Complexity

Operation	Expected	Worst Case	Notes
Search	O(log n)	O(n)	Extremely rare worst case
Insert	O(log n)	O(n)	Includes search + insertion
Delete	O(log n)	O(n)	Includes search + deletion
Range scan (by iteration)	O(n)	O(n)	Iterate and filter as needed

Expected height: O(log n) with high probability Worst case height: O(n) but probability is negligible

Applications

Database Systems

• Redis: Sorted sets (ZSET) use skip lists
• LevelDB/RocksDB: Memtable implementation
• Apache Cassandra: Index structures

Concurrent Data Structures

• Lock-free skip lists: High-performance concurrent maps
• Multi-threaded applications: Thread-safe containers

Range Queries

• Time-series data: Efficient range scans
• Spatial data: Range queries on sorted data

Educational

• Teaching data structures: Simpler than balanced trees
• Algorithm courses: Demonstrates randomization

Comparison with Balanced Trees

Feature	Skip List	Balanced Tree (AVL/RB)
Implementation	Simpler	More complex
Rotations	None	Required
Worst-case guarantee	Probabilistic	Guaranteed
Concurrent version	Easier	Harder
Cache performance	Good	Variable
Memory overhead	Higher	Lower

When to Use Skip Lists

✅ Good for:

• When simplicity matters
• Concurrent applications
• Range queries needed
• Educational purposes

❌ Not good for:

• When worst-case guarantees critical
• Memory-constrained environments
• Deterministic performance required

Usage Example

DynSkipList<int> skip_list;
 
skip_list.insert(10);
skip_list.insert(5);
skip_list.insert(15);
 
if (skip_list.search(10))
  cout << "Found 10!\n";
 
skip_list.remove(5);

See also

tpl_dynSkipList.H Skip List implementation

dynset_trees.C Balanced tree alternatives

Pugh, W. "Skip Lists: A Probabilistic Alternative to Balanced Trees" (1990)

Author

Leandro Rabindranath León

Definition in file skiplist_example.C.

Function Documentation

benchmark_comparison()

void benchmark_comparison	(	size_t	n,
		unsigned	seed,
		bool	verbose
	)

Benchmark skip list vs std::set.

Definition at line 337 of file skiplist_example.C.

References StlAlephIterator< SetName >::end(), Aleph::DynSkipList< Key, Compare >::has(), Aleph::DynSkipList< Key, Compare >::insert(), Aleph::DynList< T >::insert(), Aleph::maps(), rng, Aleph::HTList::size(), Aleph::DynSkipList< Key, Compare >::size(), and Aleph::verbose.

Referenced by main().

demonstrate_basic_operations()

void demonstrate_basic_operations

(

)

Demonstrate basic Skip List operations.

DynSkipList is an ordered set (not a map). Each element is stored and accessed by its own value.

Definition at line 211 of file skiplist_example.C.

References Aleph::DynSkipList< Key, Compare >::get_it(), Aleph::DynSkipList< Key, Compare >::has(), Aleph::DynSkipList< Key, Compare >::Iterator::has_curr(), Aleph::DynSkipList< Key, Compare >::insert(), Aleph::maps(), Aleph::DynSkipList< Key, Compare >::remove(), Aleph::DynSkipList< Key, Compare >::search(), and Aleph::DynSkipList< Key, Compare >::size().

Referenced by main().

demonstrate_functional()

void demonstrate_functional

(

)

Demonstrate functional programming features.

Definition at line 309 of file skiplist_example.C.

References FunctionalMethods< Container, T >::all(), FunctionalMethods< Container, T >::exists(), FunctionalMethods< Container, T >::for_each(), Aleph::DynList< T >::insert(), Aleph::maps(), and Aleph::sum().

Referenced by main().

demonstrate_string_set()

void demonstrate_string_set

(

)

Demonstrate skip list with strings.

Definition at line 279 of file skiplist_example.C.

References Aleph::DynSkipList< Key, Compare >::get_it(), Aleph::DynSkipList< Key, Compare >::has(), Aleph::DynSkipList< Key, Compare >::Iterator::has_curr(), Aleph::DynSkipList< Key, Compare >::insert(), and Aleph::maps().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 444 of file skiplist_example.C.

References benchmark_comparison(), demonstrate_basic_operations(), demonstrate_functional(), demonstrate_string_set(), Aleph::maps(), Aleph::size(), Aleph::verbose, and visualize_structure().

visualize_structure()

void visualize_structure

(

)

Visualize skip list structure (small example)

Definition at line 421 of file skiplist_example.C.

References Aleph::maps().

Referenced by main().