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 have 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
Draw pictures to help you visualize.
If you do not implement the TODO item if p is upperleftmost skip Node then add a new level mentioned in SkipInsert, it will be hard to insert more than a few elements.
Be careful to note which SkipNode links could be NULL and handle them correctly.
The book has psuedocode showing rand() < 1/2. In C++, rand() returns an integer. So do not use the condition described in the book to implement a coinflip.
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.