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 , elemnew Node[ss] 
 Nodes() :sz 1 , elemnew 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():height20, header_arr20, nil_arr20 
 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) : szn.sz, elemnew 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.

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

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.