Skip lists are a probabilistic alternative to balanced trees, they are balanced by consulting a random number generator, that determines how many pointerscalled node level to successive elements a node will have.
Skip list is a simple data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, each skipping over fewer elements, as depicted on the following figure:
According to the paper this data structure offers same, in some cases even better performance of alternative data structures like: AVL trees, self adjusting trees, as one can see on the following table:
with relatively low implementation cost:
"However, implementing balanced trees is an exacting task and as a result balanced tree algorithms are rarely implemented except as part of a programming assignment in a data structures class. Skip lists are a simple data structure that can be used in place of balanced trees for most applications."
The following code implements a Skip List based on "Skip Lists: A Probabilistic Alternative to Balanced Trees" by W.Pugh.
Skip_list.h
#ifndef SKIP_LIST_H
#define SKIP_LIST_H
//==============================================================================
struct Skip_Node {
int key;
std::string value;
// pointers to successor nodes
std::vector<Skip_Node*> forward;
Skip_Node (int k, const std::string& v, int level);
};
//==============================================================================
class Skip_list {
public:
Skip_list ();
~Skip_list ();
// non-modifying member functions
void print ();
Skip_Node* find (int searchKey);
// modifying member functions
void insert (int searchKey, std::string newValue);
void erase (int searchKey);
private:
// pointer to first node
Skip_Node* head;
// last node
Skip_Node* NIL;
// implicitly used member functions
int randomLevel ();
int nodeLevel(const std::vector<Skip_Node*>& v);
Skip_Node* makeNode (int key, std::string val, int level);
// data members
float probability;
int maxLevel;
};
#include "Skip_list.cpp"
#endif
Skip_list.cpp
// Struct Skip_node member implementations
// constructor
Skip_Node::Skip_Node (int k, const std::string& v, int level)
: key(k), value(v)
{
for (int i = 0; i < level; ++i) forward.emplace_back(nullptr);
}
//==============================================================================
// Class Skip_list member implementations
// constructor
Skip_list::Skip_list()
: probability(0.5), maxLevel(16)
{
// Initialize the head of the skip list
// smallest possible key
int headKey = std::numeric_limits<int>::min();
head = new Skip_Node(headKey, "head", maxLevel);
// Initialize the last element of the list
// largest possible key
int nilKey = std::numeric_limits<int>::max();
NIL = new Skip_Node(nilKey, "NIL", maxLevel);
// Connect start to end
// connect all the levels/forward pointers of the header to NIL
for (size_t i = 0; i < head->forward.size(); ++i) {
head->forward[i] = NIL;
}
}
// destructor
Skip_list::~Skip_list () {
delete head;
delete NIL;
}
// Helper functions
/*
Function: randomLevel()
Use: implicit in class Skip_list
It generates node levels in the range
[1, maxLevel).
It uses rand() scaled by its maximum
value: RAND_MAX, so that the randomly
generated numbers are within [0,1).
*/
int Skip_list::randomLevel () {
int v = 1;
while ((((double)std::rand() / RAND_MAX)) < probability &&
std::abs(v) < maxLevel) {
v += 1;
}
return abs(v);
}
/*
Function: nodeLevel()
Use: Implicitly in most of the member functions.
It returns the number of non-null pointers
corresponding to the level of the current node.
(the node that contains the checked vector of
forward pointers)
If list empty returns 1.
*/
int Skip_list::nodeLevel (const std::vector<Skip_Node*>& v) {
int currentLevel = 1;
// last element's key is the largest
int nilKey = std::numeric_limits<int>::max();
if (v[0]->key == nilKey) {
return currentLevel;
}
for (size_t i = 0; i < v.size(); ++i) {
if (v[i] != nullptr && v[i]->key != nilKey) {
++currentLevel;
} else {
break;
}
}
return currentLevel;
}
// Non-modifying member functions
/*
Function: print()
Use: skip_list_obj.print();
It prints the key, value, level
of each node of the skip list.
Prints two nodes per line.
*/
void Skip_list::print () {
Skip_Node* list = head;
int lineLenght = 1;
std::cout <<"{";
while (list->forward[0] != nullptr) {
std::cout <<"value: "<< list->forward[0]->value
<<", key: "<< list->forward[0]->key
<<", level: "<< nodeLevel(list->forward);
list = list->forward[0];
if (list->forward[0] != nullptr) std::cout <<" : ";
if (++lineLenght % 2 == 0) std::cout <<"\n";
}
std::cout <<"}\n";
}
/*
Function: find()
Use: Skip_Node* found = skip_list_obj.find(searchKey);
It searches the skip list and
returns the element corresponding
to the searchKey; otherwise it returns
failure, in the form of null pointer.
*/
Skip_Node* Skip_list::find(int searchKey) {
Skip_Node* x = head;
unsigned int currentMaximum = nodeLevel(head->forward);
for (unsigned int i = currentMaximum; i-- > 0;) {
while (x->forward[i] != nullptr && x->forward[i]->key < searchKey) {
x = x->forward[i];
}
}
x = x->forward[0];
if (x->key == searchKey) {
return x;
} else {
return nullptr;
}
}
// Modifying member functions
/*
Function: makeNode ()
Use: Implicitly in member function insert().
It wraps the Skip_Node constructor which creates
a node on the heap and returns a pointer to it.
*/
Skip_Node* Skip_list::makeNode (int key, std::string val, int level) {
return new Skip_Node(key, val, level);
}
/*
Function: insert();
Use: void insert(searchKey, newValue);
It searches the skip list for elements
with seachKey, if there is an element
with that key its value is reassigned to the
newValue, otherwise it creates and splices
a new node, of random level.
*/
void Skip_list::insert(int searchKey, std::string newValue) {
// reassign if node exists
Skip_Node* x = nullptr;
x = find(searchKey);
if (x) {
x->value = newValue;
return;
}
// vector of pointers that needs to be updated to account for the new node
std::vector<Skip_Node*> update(head->forward);
unsigned int currentMaximum = nodeLevel(head->forward);
x = head;
// search the list
for (unsigned int i = currentMaximum; i-- > 0;) {
while (x->forward[i] != nullptr && x->forward[i]->key < searchKey) {
x = x->forward[i];
}
update[i] = x;
}
x = x->forward[0];
// create new node
int newNodeLevel = 1;
if (x->key != searchKey) {
newNodeLevel = randomLevel();
int currentLevel = nodeLevel(update);
if (newNodeLevel > currentLevel) {
for (int i = currentLevel + 1; i < newNodeLevel; ++i) {
update[i] = head;
}
}
x = makeNode(searchKey, newValue, newNodeLevel);
}
// connect pointers of predecessors and new node to successors
for (int i = 0; i < newNodeLevel; ++i) {
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
}
/*
Function: delete_node()
Use: skip_list_obj.erase(searchKey)
It deletes the element containing
searchKey, if it exists.
*/
void Skip_list::erase (int searchKey) {
// vector of pointers that needs to be updated to account for the deleted node
std::vector<Skip_Node*> update(head->forward);
Skip_Node* x = head;
unsigned int currentMaximum = nodeLevel(head->forward);
// search and update pointers
for (unsigned int i = currentMaximum; i-- > 0;) {
while (x->forward[i] != nullptr && x->forward[i]->key < searchKey) {
x = x->forward[i];
}
update[i] = x;
}
x = x->forward[0];
// update pointers and delete node
if (x->key == searchKey) {
for (size_t i = 0; i < update.size(); ++i) {
if (update[i]->forward[i] != x) {
break;
}
update[i]->forward[i] = x->forward[i];
}
delete x;
}
}
main
#include <iostream>
#include <time.h>
#include <string>
#include <sstream>
#include <vector>
#include "Skip_list.h"
//==================================================
int main () {
// 1.Initialize an empty Skip_list object
Skip_list s;
// 2. insert()
for (int i = 0; i < 50; ++i){
std::stringstream ss;
ss << i;
s.insert(i, ss.str());
}
// 2a. print()
s.print();
// 3. find()
Skip_Node* f = nullptr;
f = s.find(10);
if (f) std::cout <<"Node found!\nvalue: "<< f->value <<'\n';
else std::cout <<"Node NOT found!\n";
// 4. insert() - reassign
s.insert(40, "TEST");
// 4a. print()
s.print();
// 5. erase()
s.erase(40);
// 5a. print();
s.print();
std::cout << "\nDone!\n";
getchar();
}
I would like suggestions on how to improve the above code and correct any bad code practices.
Note: This is a first draft of solution to Exercise 11 Chapter 18 of C++ Programming: Principles and Practice by B. Stroustrup
Exercise 11 : Look up (e.g. on the web) skip list and implement that kind of list. This is not an easy exercise.
However, implementing balanced trees is an exacting task and as a result balanced tree algorithms are rarely implemented
and because we already have perfect examples implemented for us in the standardstd::map
andstd::set
\$\endgroup\$while
loop which performs "forward deletion" (if this is a thing, i.e. delete from front to back). \$\endgroup\$