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 };
};

• seabiscuit: I could use some clarification with regards to Your constructors should be explicit . Thank you for your work and thank you in advance for clarifications.
• user128454: Due to historical reasons, single argument constructors allow for the implicit creation of objects. This is almost always undesirable, so single-arguments should be marked with the explicit keyword unless you really need implicit conversion support.

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.