Old skip list implementation

skiplist.cpp

#include <cstdio>
#include <cstdlib>

#include <set>
using namespace std;

const int N = 10000000;

const int maxLevel = 20;

struct skip_list
{
	// Node record for each element in the skip list including head and tail
	struct node
	{
		node **next;
		int data, levels;

		node(int ndata, int nlevels) : data(ndata), levels(nlevels)
		{
			next = new node *[nlevels];
		}
	};

	node *head, *tail, *trd[maxLevel+1];
	int nTrd;
	
	// Constructor
	skip_list()
	{
		head = new node(INT_MIN, maxLevel+1);
		tail = new node(INT_MAX, maxLevel+1);
		for (int i = 0; i <= maxLevel; ++i) head->next[i] = tail;
	}

	// Checks if the container is empty
	bool empty() { return head->next[0] == tail; }

	// Helper function. Traverses the list looking for an element and
	// maintains a stack of elements (trd) that point to or over the element
	// at each level
	void findprev(int query)
	{
		nTrd = 0;
		node *it = head;
		for (int l = maxLevel; l >= 0; --l)
		{
			while (query > it->next[l]->data) it = it->next[l];
			trd[nTrd++] = it;
		}
	}

	// Determines whether a particular element is in the skip list
	bool find(int query)
	{
		findprev(query);
		return query == trd[nTrd - 1]->next[0]->data;
	}

	// Inserts an element into the skip list
	void insert(int ndata)
	{
		findprev(ndata);
		if (ndata != trd[nTrd - 1]->next[0]->data)
		{
			int randomLevel = 0;
			while (randomLevel < maxLevel && rand() & 1)
				++randomLevel;	

			node *newNode = new node(ndata, randomLevel + 1);
			for (int i = 0; i <= randomLevel; ++i)
			{
				newNode->next[i] = trd[nTrd - i - 1]->next[i];
				trd[nTrd - i - 1]->next[i] = newNode;
			}
		}
	}

	// Removes an element from the skip list
	void remove(int query)
	{
		findprev(query);
		if (query == trd[nTrd - 1]->next[0]->data)
		{
			node *deletee = trd[nTrd - 1]->next[0];
			for (int i = 0; i < deletee->levels; ++i)
				trd[nTrd - 1 - i]->next[i] = deletee->next[i];
			delete deletee;
		}
	}
};

int main(int argc, char **argv)
{
	srand(1111);

	if (argc > 1)
	{
		skip_list SL;
		for (int i = 0; i < N; ++i)
			SL.insert(rand() % 1000000);
		for (int i = 0; i < N; ++i)
			SL.find(rand () % 1000000);
	}
	else
	{
		set<int> S;
		for (int i = 0; i < N; ++i)
			S.insert(rand() % 1000000);
		for (int i = 0; i < N; ++i)
			S.find(rand () % 1000000) != S.end();
	}

	return 0;
}