This project implements a Skip List data structure in C++, providing an efficient alternative to balanced trees for implementing associative arrays. Skip lists are probabilistic data structures that offer logarithmic time complexity for search, insertion, and deletion operations, making them suitable for various applications where fast access to sorted data is required.
Skip lists consist of multiple linked lists, each with nodes containing references to nodes in lower levels. By "skipping" ahead in multiple linked lists, skip lists provide faster search operations compared to traditional linked lists. Every element has a 1/2 probability to get promoted to the next level. The total number of levels are asymptotic to log n.
- Time Complexity: Average case
- Search: O(log n)
- Insertion: O(log n)
- Deletion: O(log n)
- Space Complexity: O(n)
Skiplist* obj = new Skiplist();
bool param_1 = obj->search(target);
obj->add(num);
bool param_3 = obj->erase(num);- GitHub Repository: RatulDawar/skip-list
- File: SkipList.cpp
Feel free to explore the repository and use the Skip List implementation in your projects!