c++ skiplist implentation

Question

how to implement a c++ skiplist implemented using a linked list structure, no arrays or vectors allowed for storing nodes

Answer 1

#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

// Maximum level of the skip list

#define MAX_LEVEL 32

// Node class

class Node {

public:

int key;

Node **forward;

int level;

Node(int key, int level) {

this->key = key;

this->level = level;

// Allocate memory to forward

this->forward = new Node*[level+1];

// Fill forward array with 0(NULL)

memset(forward, 0, sizeof(Node*)*(level+1));

}

};

// SkipList class

class SkipList {

private:

Node *header;

int level;

public:

SkipList() {

header = new Node(-1, MAX_LEVEL);

level = 0;

srand(time(0)); // Initialize random number generator

}

// Create random level for node

int randomLevel() {

int lvl = 0;

while(rand()%2 == 1 && lvl < MAX_LEVEL)

lvl++;

return lvl;

}

// Insert given key in skip list

void insert(int key) {

Node *current = header;

// Create update array and initialize it

Node *update[MAX_LEVEL+1];

memset(update, 0, sizeof(Node*)*(MAX_LEVEL+1));

// Start from highest level of skip list

for(int i = level; i >= 0; i--) {

while(current->forward[i] != NULL && current->forward[i]->key < key)

current = current->forward[i];

update[i] = current;

}

// Reached level 0 and forward node to right, which is desired insert position

current = current->forward[0];

// If current is NULL that means we have reached to end of the level or current's key is not same as key to insert that means we have to insert node between update[0] and current node

if(current == NULL || current->key != key) {

// Generate a random level for node

int rlevel = randomLevel();

// If random level is greater than list's current level (node with highest level inserted in list), initialize update value with pointer to header for further use

if(rlevel > level) {

for(int i = level+1; i < rlevel+1; i++)

update[i] = header;

// Update the list current level

level = rlevel;

}

// Create new node with random level generated

Node* n = new Node(key, rlevel);

// Insert node by rearranging references

for(int i = 0; i <= rlevel; i++) {

n->forward[i] = update[i]->forward[i];

update[i]->forward[i] = n;

}

}

}

// Display skip list level wise

void displayList() {

for(int i = 0; i <= level; i++) {

Node *node = header->forward[i];

cout << "Level " << i << ": ";

while(node != NULL) {

cout << node->key << " ";

node = node->forward[i];

}

cout << "\n";

}

}

};

// Driver to test above code

int main() {

SkipList lst;

lst.insert(3);

lst.insert(6);

lst.insert(7);

lst.insert(9);

lst.insert(12);

lst.insert(19);

lst.insert(17);

lst.insert(26);

lst.insert(21);

lst.insert(25);

lst.displayList();

}