I tried my best implementing a Skip List in C++ in which I had a particular idea that I wanted to try out. Instead having every element in the base level be a column vector, I only only have a singly-based list in the base level, and I store simple integers as to what level they are in.
For Example, instead of getting heads 5 times and copying an object of Cat 5 times, I simply did
while(coinFilp() == heads) {
node.level++
}
and then I used node.level as a height indicator.
The following is how I implemented the Skip List:
Iterator<T> after(int level, Iterator<T> it)
{
Node<T> *cNode = it.currentNode;
Node<T> *nextNode = cNode->next;
while (nextNode->level < level && nextNode != ll.getTrailer())
{
nextNode = nextNode->next;
}
return Iterator<T>(nextNode);
}
Iterator<T> skipSearch(T v)
{
Iterator<T> n = Iterator<T>(s);
int currentLevel = s->level;
while (currentLevel > -1)
{
n = Iterator<T>(s);
// make sure one is not null
while (after(currentLevel, n).currentNode != ll.getTrailer() && after(currentLevel, n).getValue() < v)
{
n = after(currentLevel, n);
}
currentLevel--;
}
return n;
}
Iterator<T> skipInsert(T v)
{
Iterator<T> it = skipSearch(v);
Iterator<T> newElement = insertAfterSkip(v, it);
Node<T> *n = newElement.currentNode;
while (n->level >= currentLevel)
{
incrementLevel();
}
return newElement;
}
void incrementLevel()
{
s->level++;
ll.getTrailer()->level++;
currentLevel++;
}
private:
Iterator<T> insertAfterSkip(T val, Iterator<T> p)
{
Iterator<T> it = after(0, p);
Node<T> *no = ll.insert(val, *(it.currentNode));
n++;
return Iterator(*no);
}
These are just a few methods in my Skip List implementation. I mean I feel like instead of copying an object a certain number of times, we can just give it a random number and that would be its level. Firstly, is this implementation of a Skip List correct? And is assigning a number instead of copying objects a better way to approach it?
Thanks
