Implementation of Skip List Using C++

Question

Skip List Header File

#include <random>
#include <iostream>
#include <algorithm>

struct Node {
    Node(int vv, Node*nn = nullptr) : val{ vv }, next{ nn }{}
    Node() : val{ 0 }, next{ nullptr } {} 
    //Node(const Node &n);      //copy constructor
    //Node& operator=(Node &n); //copy assignment

    ~Node() { 
        std::cout << "node deleted" << std::endl; 
    }
    int val{ 0 };
    int level{ 0 };
    Node* next;

};

class Nodes {
public:

    Nodes(int ss) :sz{ ss }, elem{new Node[ss]} {}
    Nodes() :sz{ 1 }, elem{new Node[1]} {}
    Nodes(const Nodes& n);

    //copy operations not used 
    /*
    Nodes& operator=(const Nodes&n);
    Nodes(Nodes&& n);
    Nodes& operator=(Nodes&& n);
    */

    //subscript operator
    Node& operator[](int i){ return elem[i]; }

    ~Nodes() {
        delete[] elem;
        std::cout << "nodes deleted" << std::endl;
    }
 private:
    int sz;
    Node* elem;

};



class Skip_list {
public:

    // hard coded max height for simplicity
    // creates two Nodes containers for nil and header 
    //links header->nil
    Skip_list():height{20}, header_arr{20}, nil_arr{20} {
        for (int i = 0; i < height; ++i) {
            header_arr[i].level = i;
            header_arr[i].val = INT_MIN;

            nil_arr[i].level = i;
            nil_arr[i].val = INT_MAX;

            header_arr[i].next = &nil_arr[i];
        }
    }

    void print(); // print all values of nodes
    void insert(int val); // add new value to skip list

    // free all memory allocated for nodes between header and nill;
    // header and nil deallocation is handled by Nodes destructor
    ~Skip_list() {
        int count = 0;
        Node* p = &header_arr[0];

        while (p) {
          p=p->next; 
          ++count;
        }
        Node** base=new Node*[count];
        p = &header_arr[0];

        for (int i = 0; i < count; ++i) {
            base[i] = p;
            p = p->next;
        }

        for (int i = 1; i < count-1; ++i) {
           delete[] base[i];
        }
        delete[] base;
        std::cout << "destructor" <<std:: endl;
    }
    void del(int val); // remove item from list and deallocate associated 
memory
    Node* find(int val);

private:
    int height; 
    Nodes header_arr;    
    Nodes nil_arr;     
};


int rand_height(int max); // random number generator;

Skip List cpp File

#include "skip_list.h"

Nodes::Nodes(const Nodes &n) : sz{n.sz}, elem{new Node[n.sz]}{
    for (int i = 0; i < sz; ++i) {
    elem[i] = n.elem[i];
    }
}

// Nodes container copy constructors not necessary for this implementation 
/*
Nodes& Nodes::operator=(const Nodes &n){
    if (sz < n.sz) {
        Node* elem_temp = new Node[n.sz];

        for (int i = 0; i < n.sz; ++i) 
            elem_temp[i] = n.elem[i];

        delete[] elem;
        elem = elem_temp;
        sz = n.sz;
        return *this;
    }
    else{
        for (int i = 0; i < n.sz; ++i) 
            elem[i] = n.elem[i];
        return *this;
    }
}


Nodes::Nodes(Nodes&& n) :sz{ n.sz }, elem{ n.elem } {
    n.sz = 0;
    n.elem = nullptr;
}


Nodes& Nodes::operator=(Nodes&& n) {
    delete[] elem;
    elem = n.elem;
    n.sz = 0;
    n.elem = nullptr;
    return *this;
}
*/

void Skip_list::insert(int val) {
    // create array of nodes with value=val 
    int max_level = height - 1;

    // gets random val between 1 and num elements in header
    int temp_levels = rand_height(height); 

    Node* n_temp=new Node[temp_levels];

    for (int i = 0; i < temp_levels; ++i) {
    n_temp[i].val = val;
    n_temp[i].level = i;
}

    //adding new node/s to Skip_list
    Node* p = &header_arr[max_level];
    Node* p_n = &n_temp[temp_levels - 1];

    for (int i = max_level; i>=0 ;--i) {
        p = &header_arr[i];
        while (p_n->val > p->next->val)
        p = p->next;

        if (p_n->val == p->next->val) {
            std::cout << "value already exsists in table" << std::endl;
            break;
        }

        if (p_n->level == p->level ) {
            p_n->next = p->next;
            p->next = p_n;      
            p_n = --p_n;
        }
    }
}

Node* Skip_list::find(int n) {
    Node* p = &header_arr[height - 1];
    int i = 0;
    for (int i =height-1; i >= 0;--i) {

        p = &header_arr[i];

        while (n > p->next->val) 
            p = p->next;

        if (p->next->val == n) {
            p = p->next;
            p = p - i; //get address of index 0 for array with value n
            return p; 
        }
    }

    return nullptr;

}

void Skip_list::del(int n) {

    Node* p = &header_arr[height - 1];

    for (int i = height - 1; i >= 0; --i) {

        p = &header_arr[i];

        while (n > p->next->val)
            p = p->next;

        if (p->next->val == n) {

            Node* p2 = p->next; // pointer to node w/val n

            //remove array of n from list
            for (int j = 0; j <= i; ++j) {

                // maintain continuity in list
                p->next = p2->next; 

                // decrements vertically in list
                if (j < i) {
                    --p;        
                    --p2;       
                }
            }

            delete[] p2;
            break;
        }
    }
}


void Skip_list::print() {

    Node* p = &header_arr[height-1];

    for (int i = height-1; i >= 0; --i) {
        p = &header_arr[i];

        while (p) {
            std::cout << p->val << ' ';
            p = p->next;
        }
        std::cout << std::endl;
    }
}

int rand_height(int max){
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(1, max);
    return dis(rd);
}

Test of Implementation

/* 
Bjarne Stroustrup's "Programming Principles and Practices Using C++"
Exercise 11 of Chapter 18
Implementation of a Skip list
*/

#include "skip_list.h"

void test() {
    Skip_list sl;
    sl.insert(10 );
    sl.insert(12 );
    sl.insert(5 );
    sl.insert(6);
    sl.insert(7);
    sl.insert(8);
    sl.insert(9);
    sl.print();

    Node* n5 = sl.find(5);
    Node* n10 = sl.find(10);
    Node* n12 = sl.find(12);

    std::cout << n5  <<  ' ' << n5->val << std::endl;
    std::cout << n10 << ' ' << n10->val << std::endl;
    std::cout << n12 << ' ' << n12->val << std::endl;
    sl.del(12);

    Node* n12d= sl.find(12);

    if (n12d!=nullptr)
        std::cout << n12d << ' ' << n12d->val << std::endl;
    else
        std::cout << "not found" << std::endl;
}


int main() {

    test();

    char quit;
    std::cout << std::endl;
    std::cout << "enter a char to exit" << std::endl;
    std::cin >> quit;

    return 0;
}

Please point out any errors or implementation details that should be addressed.

Answer 1

Reviewing just the header:

Missing header guards.

Your Skip List Header File needs header guards.

std::cout is not for logging in final code.

At worse, use std::cerr, but ideally use a proper logging library like spdlog, or a log callback. Otherwise, your class cannot be used in any application that actually uses std::cout for its output.

Using std::cout is ok while developing, but once you are done, it has to go.

Your constructors should be explicit

consider the following:

void foo(Nodes const& n);

...

foo(3);

How misleading!

Don't just comment out the copy constructors and = operators

delete them explicitely instead.

Nodes {
  Nodes(Nodes const&) = delete;
};

Be consistent about in-class inlining.

You have very long functions defined in the header, yet you still have a .cpp file. Be consistent, either implement the whole thing in a header, or move any non-trivial function to the .cpp file.

Be consistent about how you default-initialize things.

Are you doing it in the default constructor, or in the member declaration? make up your mind. I prefer the following:

struct Node {
    Node(int vv, Node*nn = nullptr) : val{ vv }, next{ nn } {}
    Node() = default; 

    int val{ 0 };
    int level{ 0 };
    Node* next{ nullptr };
};

Answer 2

Don’t use naked new/delete. You have a pointer and a sz; why not just use a std::vector? Or in general, use unique_ptr (which works with arrays now) rather than a raw pointer.