Answer to Question #244396 in C for Subhasish

Question

Write a program to implement a searching algorithm on a skip list having two layers as
shown in below figure:
Assume that the linked list is already sorted. Write your observations on the time complexity of
the algorithm.

Answer 1

#include <bits/stdc++.h>
using namespace std;
class Node
{
    public:
    	int k;
    	Node **forw;
    	Node(int, int);
};


Node::Node(int k, int level)
{
	this->k = k;
	forw = new Node*[level+1];
	memset(forw, 0, sizeof(Node*)*(level+1));
};


class SkipList
{
	
	int MAX;
	float P;
	int level;
	Node *header;
public:
	SkipList(int, float);
	int randomLevel();
	Node* createNode(int, int);
	void insertElement(int);
	void searchElement(int);
	
};


SkipList::SkipList(int MAX, float P)
{
	this->MAX = MAX;
	this->P = P;
	level = 0;
	header = new Node(-1, MAX);
};
int SkipList::randomLevel()
{
	float r = (float)rand()/RAND_MAX;
	int lvl = 0;
	while(r < P && lvl < MAX)
	{
		lvl++;
		r = (float)rand()/RAND_MAX;
	}
	return lvl;
};


Node* SkipList::createNode(int k, int level)
{
	Node *n = new Node(k, level);
	return n;
};
void SkipList::insertElement(int k)
{
	Node *cur = header;
	Node *update[MAX+1];
	memset(update, 0, sizeof(Node*)*(MAX+1));
	for(int i = level; i >= 0; i--)
	{
		while(cur->forw[i] != NULL &&
			cur->forw[i]->k < k)
			cur = cur->forw[i];
		update[i] = cur;
	}
	cur = cur->forw[0];
	if (cur == NULL || cur->k != k)
	{
		int rlevel = randomLevel();
		if(rlevel > level)
		{
			for(int i=level+1;i<rlevel+1;i++)
				update[i] = header;
			level = rlevel;
		}
		Node* n = createNode(k, rlevel);
		for(int i=0;i<=rlevel;i++)
		{
			n->forw[i] = update[i]->forw[i];
			update[i]->forw[i] = n;
		}
		cout<<"Successfully Inserted key "<<k<<"\n";
	}
};


void SkipList::searchElement(int k)
{
	Node *cur = header;


	for(int i = level; i >= 0; i--)
	{
		while(cur->forw[i] &&
			cur->forw[i]->k < k)
			cur = cur->forw[i];


	}
	cur = cur->forw[0];
	if(cur and cur->k == k)
		cout<<"Found key: "<<k<<"\n";
};




int main()
{
	srand((unsigned)time(0));


	SkipList l(3, 0.5);


	l.insertElement(3);
	l.insertElement(6);
	l.insertElement(7);
	
	l.searchElement(6);
}