Implementing Skip List in C++

Question

[SOLVED]

So I decided to try and create a sorted doubly linked skip list...

I'm pretty sure I have a good grasp of how it works. When you insert x the program searches the base list for the appropriate place to put x (since it is sorted), (conceptually) flips a coin, and if the "coin" lands on a then that element is added to the list above it(or a new list is created with element in it), linked to the element below it, and the coin is flipped again, etc. If the "coin" lands on b at anytime then the insertion is over. You must also have a -infinite stored in every list as the starting point so that it isn't possible to insert a value that is less than the starting point (meaning that it could never be found.)

To search for x, you start at the "top-left" (highest list lowest value) and "move right" to the next element. If the value is less than x than you continue to the next element, etc. until you have "gone too far" and the value is greater than x. In this case you go back to the last element and move down a level, continuing this chain until you either find x or x is never found.

To delete x you simply search x and delete it every time it comes up in the lists.

For now, I'm simply going to make a skip list that stores numbers. I don't think there is anything in the STL that can assist me, so I will need to create a class List that holds an integer value and has member functions, search, delete, and insert.

The problem I'm having is dealing with links. I'm pretty sure I could create a class to handle the "horizontal" links with a pointer to the previous element and the element in front, but I'm not sure how to deal with the "vertical" links (point to corresponding element in other list?)

If any of my logic is flawed please tell me, but my main questions are:

1. How to deal with vertical links and whether my link idea is correct
2. Now that I read my class List idea I'm thinking that a List should hold a vector of integers rather than a single integer. In fact I'm pretty positive, but would just like some validation.
3. I'm assuming the coin flip would simply call int function where rand()%2 returns a value of 0 or 1 and if it's 0 then a the value "levels up" and if it's 0 then the insert is over. Is this incorrect?
4. How to store a value similar to -infinite?

Edit: I've started writing some code and am considering how to handle the List constructor....I'm guessing that on its construction, the "-infinite" value should be stored in the vectorname[0] element and I can just call insert on it after its creation to put the x in the appropriate place.

Answer 1

1. Just store 2 pointers. One called above, and one called below in your node class.
2. Not sure what you mean.
3. According to wikipedia you can also do a geometric distribution. I'm not sure if the type of distribution matters for totally random access, but it obviously matters if you know your access pattern.
4. I am unsure of what you mean by this. You can represent something like that with floating point numbers.

Answer 2

http://msdn.microsoft.com/en-us/library/ms379573(VS.80).aspx#datastructures20_4_topic4

http://igoro.com/archive/skip-lists-are-fascinating/

The above skip lists are implemented in C#, but can work out a c++ implementation using that code.

Answer 3

You're making "vertical" and "horizontal" too complicated. They are all just pointers. The little boxes you draw on paper with lines on them are just to help visualize something when thinking about them. You could call a pointer "elephant" and it would go to the next node if you wanted it to.

eg. a "next" and "prev" pointer are the exact same as a "above"/"below" pointer.

Anyway, good luck with your homework. I got the same homework once in my data structures class.