Answer to Question #241629 in C for Ram

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 x;
    	Node **forward;
    	Node(int, int);
};




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




class SkipList
{
	
	int MAX;
	float p;
	int lev;
	Node *header;
public:
	SkipList(int, float);
	int randomLev();
	Node* createNode(int, int);
	void addElement(int);
	void search_Ele(int);
	
};

SkipList::SkipList(int MAX, float P)
{
	this->MAX = MAX;
	this->P = P;
	lev = 0;
	header = new Node(-1, MAX);
};
int SkipList::randomLev()
{
	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 x, int level)
{
	Node *m = new Node(x, level);
	return m;
};
void SkipList::addElement(int x)
{
	Node *cur = header;
	Node *update[MAX+1];
	memset(update, 0, sizeof(Node*)*(MAX+1));
	for(int i = lev; i >= 0; i--)
	{
		while(cur->forward[i] != NULL &&
			cur->forward[i]->x < x)
			cur = cur->forward[i];
		update[i] = cur;
	}
	cur = cur->forward[0];
	if (cur == NULL || cur->x != x)
	{
		int rlev = randomLev();
		if(rlev > lev)
		{
			for(int i=lev+1;i<rlev+1;i++)
				update[i] = header;
			lev = rlev;
		}
		Node* m = createNode(x, rlev);
		for(int i=0;i<=rlev;i++)
		{
			m->forward[i] = update[i]->forward[i];
			update[i]->forward[i] = m;
		}
		cout<<"key Successfully Inserted "<<x<<"\n";
	}
};


void SkipList::search_Ele(int x)
{
	Node *cur = header;

	for(int i = lev; i >= 0; i--)
	{
		while(cur->forward[i] &&
			cur->forward[i]->x < x)
			cur = cur->forward[i];

	}
	cur = cur->forward[0];
	if(cur and cur->x == x)
		cout<<"key found: "<<x<<"\n";
};

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

	SkipList l(3, 0.5);
	l.addElement(3);
	l.addElement(7);
	l.addElement(8);
	
	l.search_Ele(7);
}