CS35 Lab5: Skip Lists

Due 11:59pm Wednesday, 24 February 2010
For this assignment, you will explore multiple implementations of an ordered lis. You will primarily implement a SkipList which allows fast searching for data and fast updates. You should save your programs in your cs35/labs/05 directory. You may work with one partner on this assignment. If you work with a partner, be sure to put both names on your assignment when submitting.
Ordered List
In you cs35/homework/05 folder, you will find a description of an OrderedList interface in orderedList.h for storing a collection of integers in sorted order. A student directory is also an OrderedList, sorted alphabetically by last name, but for simplicity in this assignment, we are just storing integers. Review the interface description in orderedList.h and be sure you understand what each method is trying to do before you implement it. Note that the insert method must add a new element to the list in sorted order (smaller integers first). The find method just returns a Boolean value indicating if the particular item or key was found in the list. Note it is possible to store more than one copy of the same integer in the OrderedList. Your assignment is to implement and test the OrderedList interface in three different ways: using a LinkedList, using an ArrayList, and implementing a new structure called the SkipList. The LinkedList and ArrayList implementations have been completed for you. You will just need to test these. You will need to both implement and test the SkipList
SkipLists
While an ArrayList implementation offers faster get and find methods than the LinkedList, updates (insert and remove) are still slow in both implementations. You will implement a SkipList from scratch to allow faster updates. A description of SkipLists can be found in section 8.4 of your text on page 394. A simple implementation of a SkipNode is included in your homework folder. Feel free to modify this class if you do not like it. Your SkipList class must also implement the OrderedList interface.

The SkipList might seem overly complicated at first, but draw a few examples on the board or trace through some examples in the text. It will be helpful to implement SkipSearch, SkipInsert, and insertAfterAbove according the book's description. Once these are implemented, you should find that many of the methods in the OrderedList interface can be implemented on top of these methods.

Psuedocode for SkipSearch and SkipInsert are included below. Some details on degenerate cases hav been omitted. You will need to add in these cases.

SkipSearch(k):
  //return a pointer to the SkipNode on the bottom level which
  //has the largest value <= k
  p = upperleftmost skip Node
  while the node below p is not null:
    p = below(p)
    while value(after(p)) <= k:
      p = after(p)
  return p

SkipInsert(k):
  //Inserts a new tower of nodes containing the value k into the skip list
  //in sorted order
  p = SkipSearch(k)
  q = InsertAfterAbove(p, NULL, k)
  while a coinflip is heads:
    while above(p) is null:
      p = before(p)
    p=above(p)
    q=InsertAfterAbove(p,q,k)
    //TODO: if p is upperleftmost skip Node then add a new level

The book refers to special nodes that store the values positive and negative infinity. In C++, you can use the special values INT_MAX and INT_MIN from <climits> to represent these limits. You can use these numbers just like any other integer.

Think about how to implement get and remove. You implementation of get does not need to be fast. An O(n) algorithm is fine.

Tips/Corrections
The initial version of the skipList.cpp code had a bad constructor (copy/paste error on the instructors part). A correct constructor is shown below
SkipList::SkipList(){
 n=0;
 start=new SkipNode(INT_MIN);
 SkipNode* ur = new SkipNode(INT_MAX);
 SkipNode* ll = new SkipNode(INT_MIN);
 SkipNode* lr = new SkipNode(INT_MAX);

 start->after=ur;
 start->below=ll;

 ll->after=lr;
 ll->above=start;

 lr->before=ll;
 lr->above=ur;

 ur->before=start;
 ur->below=lr;
}
Submitting
Along with your C++ source code, you should hand in a file named README. Your README should include a brief summary of your results, including a discussion of the advantages/disadvantages of the three implementations of OrderedList. Describe how you tested your implementations. Do you have any problems/bugs in your code? For each of the following operations: insert, remove, get, and find, describe which implementations you think gives the best/worst performance. You do not have to give big-Oh run times.