A skip list is a probabilistic data structure. The skip list is used to store a sorted list of elements or data with a linked list. It allows the process of the elements or data to view efficiently. In one single step, it skips several elements of the entire list, which is why it is known as a skip list.

-INF <-----------------------------------------------------> 75.000000 <----> INF
-INF <-----------------------------------------------------> 75.000000 <----> INF
-INF <-------------------> 1.000000 <----------------------> 75.000000 <----> INF
-INF <-------------------> 1.000000 <-----> 10.000000 <----> 75.000000 <----> INF
-INF <--> -100.000000 <--> 1.000000 <-----> 10.000000 <----> 75.000000 <----> INF

Demo

Files

Console.cpp
Console.h
Linked_List.cpp
Linked_List.h
Skip_List.cpp
Skip_List.h
main.cpp
output.txt

Example

std::vector<double> v = {90, 15, -59, 48, -1, -28};
Skip_List skip_list{v};

/// Operations
skip_list.insert(5);
skip_list.remove(90);
Node* node = skip_list.search(-1);
skip_list.remove(5);

/// Console
Console console{skip_list, "output.txt"};
console.write_to_file("output.txt");
console.run();