Skip List implementation

Question

Skip lists are a probabilistic alternative to balanced trees, they are balanced by consulting a random number generator, that determines how many pointers^{called 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.

Answer 1

Your code is a real pleasure to read because it is clean and well written - I wish more of the code here at CR were like this.

Stilistically the focus could be improved by factoring all key properties into a traits class. This would make the skip list code key-agnostic, so that it could be used without change for different kinds of key. This can be advantageous even before the class is turned into a template, and it would make the step from concrete class to a class template a lot easier.

At the moment the maximum node height is fixed; this means it is bound to be overkill for small numbers of elements and insufficient for big numbers. Most of the code could simply look at the head node to find the current max but the insert code would have to decide whether an increase is warranted (i.e. whenever the element count gains a new 1-bit at the front then a new 'express-way' should be opened by increasing the head node height). This would give more even performance over greater ranges of element counts than is currently the case.

Using a std::vector in every node gives a lot of flexibility and greatly facilitates experimentation. However, it also makes the skip list very resource-hungry. Since height of nodes is fixed at creation (apart from head nodes, but those can be dealt with differently) an alternative for high-performance production implementations would be a special-purpose allocator in the spirit of buddy systems.

It can be very instructive to run systematic performance tests with geometrically increasing element counts (e.g. 10^1, 10^2, ..., 10^10) separately for search, insert and delete, and to compare the results to (sorted) std::vector<>, std::map<>, std::unordered_map<> and so on, to get a feel for how skip lists behave. Unfortunately there's no B-tree template in the standard, so there's no data structure available for comparison that can take a bit of load (i.e. that's suitable for more than homoeopathic numbers of elements).

It can be similarly instructive to compare expected behaviour to actual behaviour. E.g. compare theoretically predicted comparison counts to actual comparison counts by instrumenting the code, for example with an interposer class for the key traits that wraps the less() predicate.

There's a well-written article on skip lists on MSDN that is very good for getting into the spirit of things. It's part of a series of articles on data structures: Part 4: Building a Better Binary Search Tree It starts with binary trees and lists but more than half of it is devoted to skip lists.

Answer 2

First of all, as DarthGizka mentioned, your code is mostly easy to read and understand and except for the memory leak I mentioned in the comments I don't see any errors.

I can't really contribute on the general question, of how effective skiplists are or what would be the best algorithm to determine the height of each node, however, I think there are still a few things that can be improved in your current implementation:

General Interface

I believe this is more of a proof-of-concept, but on if you go on with it, you should probably strive to make a interface more similar to STL-like associative containers. Meaning in particular: providing iterators, template the class on the member (and key type), providing the typical typedefs and functions (e.g. size()) etc. As mentioned by others, this would also make it easier to compare it to other data structures.

Making Skip_Node a nested class

Skip_Node is an implementation detail that should not be visible outside of the class, so you can just make it an nested class of Skip_list.

Const correctness and static member functions

You have a few member functions that should be specified const (print, find) or even static (nodeLevel, makeNode).

Structure

It seems that you assume, that you will never add an item to the container with the same key as the NIL key. If that is the case, you should probably document and assert that. However, this also means, that there is no need to treat the NIL node in a special way. More to the point: The main reason for using dedicated head and NIL nodes is so that your member functions don't have to care about empty lists, or whether a new node is the first or last node in the list.
If you embrace this concept, then you can e.g. make nodeLevel a one liner that simply returns the size of the vector.

Also, insert and erase seem a little long to me and share a nontrivial amount of code, so you might want to refactor the common functionality in a separate function.

Finally, std::vector seems to be a pretty heavy member for the list nodes (due to the size overhead and the additional memory allocation). If the maximum level is a compiletime constant, you could try e.g. a member array instead (possibly using multiple different node classes of different sizes, as suggested by DarthGizka).

Dead Code

With the above in mind and when you carefully think, about what invariants hold at each line of code, you might see, that there is a lot of test that always evaluate to true or false and code that never gets executed.

Comments

Nice to see a thoroughly commented code. Personally I would write the function documentation at the point of declaration (in the class definition) and I also try to avoid to write comments basically repeat the code the code.

After reviewing and refactoring your code, I ended up with the following (some of the changes are just personal style):

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>


class Skip_list {
public:
    Skip_list();
    ~Skip_list();

    // non-modifying member functions

    /*
    It prints the key, value, level
    of each node of the skip list.

    Prints two nodes per line.
    */
    void print() const;

    /*  
    It searches the skip list and
    returns the element corresponding
    to the searchKey; otherwise it returns
    failure, in the form of null pointer.
    */
    std::string* find(int searchKey) const;

    // modifying member functions

    /*
    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 insert(int searchKey, const std::string& newValue);

    /*
    It deletes the element containing
    searchKey, if it exists.
    */
    void erase(int searchKey);

private:

    struct Node {
        int key;
        std::string value;

        // pointers to successor nodes
        std::vector<Node*> forward;

        Node(int k, const std::string& v, int level): 
            key(k), value(v),forward(level,nullptr)
        {}          
    };  

    // Generates node levels in the range [1, maxLevel).    
    int randomLevel() const;    

    //Returns number of incoming and outgoing pointers
    static int nodeLevel(const Node* v);

    //creates a node on the heap and returns a pointer to it.   
    static Node* makeNode(int key, std::string val, int level);

    // Returns the first node for which node->key < searchKey is false  
    Node* lower_bound(int searchKey) const ;

    /*
    * Returns a collection of Pointers to Nodes
    * result[i] hold the last node of level i+1 for which result[i]->key < searchKey is true
    */
    std::vector<Node*> predecessors(int searchKey) const ;

    // data members 
    const float probability;
    const int maxLevel;
    Node* head; // pointer to first node
    Node* NIL;  // last node
};


//==============================================================================
// Class Skip_list member implementations

Skip_list::Skip_list() :
    probability(0.5), 
    maxLevel(16)
{   
    int headKey = std::numeric_limits<int>::min();
    head = new Node(headKey, "head", maxLevel); 

    int nilKey = std::numeric_limits<int>::max();
    NIL = new Node(nilKey, "NIL", maxLevel);

    std::fill(head->forward.begin(), head->forward.end(), NIL);
}

Skip_list::~Skip_list() {
    auto node = head;
    while (node->forward[0]) {
        auto tmp = node;
        node = node->forward[0];
        delete tmp;
    }
    delete node;
}

std::string* Skip_list::find(int searchKey) const {
    std::string* res{};
    if (auto x = lower_bound(searchKey)) {
        if (x->key == searchKey && x!=NIL) {
            res = &(x->value);
        }
    } 
    return res; 
}

void Skip_list::print() const {
    Node* list = head->forward[0];
    int lineLenght = 0;

    std::cout << "{";

    while (list != NIL) {
        std::cout << "value: " << list->value
            << ", key: " << list->key
            << ", level: " << nodeLevel(list);

        list = list->forward[0];

        if (list != NIL) std::cout << " : ";

        if (++lineLenght % 2 == 0) std::cout << "\n";
    }
    std::cout << "}\n";
}

void Skip_list::insert(int searchKey, const std::string& newValue) {
    auto preds = predecessors(searchKey);

    {//reassign value if node exists and return
        auto next = preds[0]->forward[0];
        if (next->key == searchKey && next != NIL) {
            next->value = newValue;
            return;
        }
    }

    // create new node
    const int newNodeLevel = randomLevel();
    auto newNodePtr = makeNode(searchKey, newValue, newNodeLevel);

    // connect pointers of predecessors and new node to respective successors
    for (int i = 0; i < newNodeLevel; ++i) {
        newNodePtr->forward[i] = preds[i]->forward[i];
        preds[i]->forward[i] = newNodePtr;
    }   
}


void Skip_list::erase(int searchKey) {
    auto preds = predecessors(searchKey);

    //check if the node exists
    auto node = preds[0]->forward[0];   
    if (node->key != searchKey || node == NIL) {
        return;
    }

    // update pointers and delete node 
    for (size_t i = 0; i < nodeLevel(node); ++i) {
        preds[i]->forward[i] = node->forward[i];
    }
    delete node;        
}

//###### private member functions ######
int Skip_list::nodeLevel(const Node* v) {
    return v->forward.size();
}

Skip_list::Node* Skip_list::makeNode(int key, std::string val, int level)  {
    return new Node(key, val, level);
}

int Skip_list::randomLevel() const {
    int v = 1;
    while (((double)std::rand() / RAND_MAX) < probability &&
        v < maxLevel) {
        v++;
    }
    return v;
}

Skip_list::Node* Skip_list::lower_bound(int searchKey) const{
    Node* x = head;

    for (unsigned int i = nodeLevel(head); i-- > 0;) {
        while ( x->forward[i]->key < searchKey) {
            x = x->forward[i];
        }
    }
    return x->forward[0];
}

std::vector<Skip_list::Node*> Skip_list::predecessors(int searchKey) const {
    std::vector<Node*> result(nodeLevel(head),nullptr);
    Node* x = head;

    for (unsigned int i = nodeLevel(head); i-- > 0;) {
        while (x->forward[i]->key < searchKey) {
            x = x->forward[i];
        }
        result[i] = x;
    }
    return result;
}



//==================================================
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();
    std::cout << std::endl;

    // 3. find()        
    auto f = s.find(10);
    if (f) std::cout << "Node found!\nvalue: " << f << '\n';
    else std::cout << "Node NOT found!\n";

    // 4. insert() - reassign
    s.insert(40, "TEST");

    // 4a. print()
    s.print();
    std::cout << std::endl;

    // 5. erase()
    s.erase(40);

    // 5a. print();
    s.print();
    std::cout << std::endl;

    std::cout << "\nDone!\n";
    getchar();
}