In this assignment, you will implement probabilistic skip lists. You will gain experience working with a probabilistic data structure and implementing reasonably complex insertion and deletion algorithms. You will also solidify your understanding of generics in Java by making your skip lists capable of holding any type of Comparable object. When youre finished, youll have a very powerful and well-constructed container class.
Dont be too intimidated by this assignment (unless thats what it takes to get you to start early, in which case you should be V E R Y I N T I M I D A T E D ! ). This will be a big challenge probably our most challenging assignment this semester but its very much within your grasp. Ive already done a lot of the heavy lifting for you by giving you the basic structure of the program and creating lots of test cases, so you get to focus on the fun part, which is taking your knowledge of how the insertion, deletion, and search algorithms for skip lists work, and translating them into code.
In this assignment, you will implement the probabilistic skip list data structure. It is important that you implement the insertion, deletion, and search operations as described in class. Also, your skip list class must be generic. Since there is an ordering property in skip lists, you must also restrict the type parameter (e.g., AnyType) to classes that implement Comparable.
You will have to implement a Node class, but since you are only submitting one source file via Webcourses (SkipList.java), you must tuck the Node class into SkipList.java. That means the Node class cannot be public. I have provided a sample SkipList.java file that demonstrates how to structure your code so that it will work with my test cases.
Implement the following methods in a class named Node . You may replace AnyType with something else, if you wish (e.g., T ), as long as the method names and return types stay the same.
Node(int height)
This constructor creates a new node with the specified height, which will be greater than zero. Initially, all of the nodes next references should be initialized to null. This constructor will be particularly useful when creating a head node, which does not store anything meaningful in its data field. This constructor may be useful to you in other ways as well, depending how you choose to implement certain of your skip list methods.
Node(AnyType data, int height)
This constructor creates a new node with the specified height, which will be greater than zero, and initializes the nodes value to data. Initially, all of the nodes next references should be initialized to null.
public AnyType value();
An O(1) method that returns the value stored at this node.
public int height();
An O(1) method that returns the height of this node.
For example, if a node has three references (numbered 0 through 2), the height of that node is 3 (even if some of those references are null).
public Node< AnyType> next(int level);
An O(1) method that returns a reference to the next node in the skip list at this particular level. Levels are numbered 0 through (height 1), from bottom to top.
If level is less than 0 or greater than (height 1), this method should return null.
I found the following methods helpful in implementing my skip lists. You might find them helpful as well, but you arent required to implement them. You may also choose to implement these suggested methods with different return types or parameter types. Youre not bound by these method signatures in the same way that youre bound by the required method signatures above.
public void setNext(int level, Node< AnyType> node);
Set the next reference at the given level within this node to node.
public void grow();
Grow this node by exactly one level. (I.e., add a null reference to the top of its tower of next references). This is useful for forcing the skip lists head node to grow when inserting into the skip list causes the lists maximum height to increase.
public void maybeGrow();
Grow this node by exactly one level with a probability of 50%. (I.e., add a null reference to the top of its tower of next references). This is useful for when inserting into the skip list causes the lists maximum height to increase.
public void trim(int height);
Remove references from the top of this nodes tower of next references until this nodes height has been reduced to the value given in the height parameter. This is useful for when deleting from the skip list causes the lists maximum height to decrease.
The height of your skip lists head node should almost always be log 2 n (the ceiling of log 2 n), where n is the number of elements in the skip list (i.e., the number of nodes in the skip list, excluding the head node). Recall that a skip lists head node does not contain an actual value, and therefore does not count as a node in your skip list when calling the size() method described below.
There are three exceptions to this rule for the height of the head node:
1. A skip list that has exactly one element should have a height of 1 (not log 2 (1) , which is 0).
2. If the skip list contains no elements, you may set the height of the head node to either 0 or 1. That choice is yours. You should pick the value that plays nicely with however youre implementing the other methods in your SkipList class.
3. One of the SkipList constructors described below allows the programmer to manually set the height of the head node when the skip list is first created. This is useful if you know that youre going to insert enough elements to cause the skip list to grow several times. In that case, you might as well start off with the skip lists height being greater than 1, even though there are no elements in the skip list to begin with. (This behavior is clarified in a number of test cases included with this assignment.)
Throughout this document, the height of the head node is considered to be synonymous with the height of your skip list.
Implement the following methods in a class named SkipList. You may replace AnyType with something else if you wish (e.g., T ), as long as the function names and return types stay the same.
SkipList();
This constructor creates a new skip list. The height of the skip list is initialized to either 0 or 1, as you see fit. (See note about the height of the head node, above.)
SkipList(int height);
This constructor creates a new skip list and initializes the head node to have the height specified by the height parameter. If the height is less than the default height you have chosen for empty lists (0 or 1), you may instead default to your chosen value of 0 or 1.
The skip list should remain this tall until either it contains so many elements that the height must grow (i.e., when log 2 n exceeds the given height of the skip list), or when an element is successfully deleted from the skip list. For further details, see the insert() and delete() method descriptions, below.
public int size();
In O(1) time, return the number of nodes in the skip list (excluding the head node, since it does not contain a value).
public int height();
In O(1) time, return the current height of the skip list, which is also the height of the head node. Note that this might be greater than log 2 n if the skip list was initialized with a height greater than 1 using the second constructor listed above.
public Node< AnyType> head();
Return the head of the skip list.
public void insert(AnyType data);
Insert data into the skip list with an expected (average-case) runtime of O(log n). If the value being inserted already appears in the skip list, this new copy should be inserted before the first occurrence of that value in the skip list. (See test cases #14 and #15 for further clarification on the order in which duplicate values should be inserted.)
You will have to generate a random height for this node in a way that respects both the maximum height of the skip list and the expected distribution of node heights. (I.e., there should be a 50% chance that the new node has a height of 1, a 25% chance that it has a height of 2, and so on, up to the maximum height allowable for this skip list.)
The maximum possible height of this new node should be either log 2 n or the current height of the skip list whichever is greater. (Recall that the height of the skip list can exceed log 2 n if the list was initialized using the second SkipList constructor described above.)
If inserting this node causes log 2 n to exceed the skip lists current height, you must increase the overall height of the skip list. Recall that our procedure for growing the skip list is as follows: (1) the height of the head node increases by 1, and (2) each node whose height was maxed out now has a 50% chance of seeing its height increased by 1. For example, if the height of the skip list is increasing from 4 to 5, the head node must grow to height 5, and each other node of height 4 has (independently) a 50% chance of growing to height 5.
Test Cases #1 through #3 demonstrate how the insert() method should affect the height of a skip list under a variety of circumstances. Test Cases #4 and #5 speak to the expected height distribution of nodes in a skip list.
public void insert(AnyType data, int height);
Insert data into the skip list using the procedure described above, but do not generate a random height for the new node. Instead, set the nodes height to the value passed in via this methods height parameter. This will be super handy for testing your code with your own sequence of not-so-random values and node heights.
public void delete(AnyType data);
Delete a single occurrence of data from the skip list (if it is present). If there are multiple copies of data in the skip list, delete the first node (that is, the leftmost node) that contains data. The expected runtime for this method should be O(log n), so you cannot perform a linear search for this node along the bottom-most level of node references. You must use the search algorithm for skip lists described in class.
If this method call results in the deletion of a node, and if the resulting number of elements in the list, n, causes log 2 n to fall below the current height of the skip list, you should trim the maximum height of the skip list to log 2 n . When doing so, all nodes that exceed the new maximum height should simply be trimmed down to the new maximum height.
If this method call does not actually result in a node being deleted (i.e., if data is not present in the skip list), you should not modify the height of the skip list.
Test Cases #8 through #11 and Test Case #13 clarify how the delete() method should affect the height of a skip list under a variety of circumstances.
public boolean contains(AnyType data);
Return true if the skip list contains data. Otherwise, return false. The expected (average-case) runtime of this function must be O(log n), and you must use the search algorithm for skip lists described in class. Test Case #6 demonstrates how the runtime of this method might be tested.
public Node< AnyType> get(AnyType data);
Return a reference to a node in the skip list that contains data. If no such node exists, return null. If multiple such nodes exist, return the first such node that would be found by a properly implemented contains() method.
public static double difficultyRating()
Return a double on the range 1.0 (ridiculously easy) through 5.0 (insanely difficult).
public static double hoursSpent()
Return an estimate (greater than zero) of the number of hours you spent on this assignment.
I found the following methods helpful in implementing my skip lists. You might find them helpful as well, but you arent required to implement them. You may also choose to implement these suggested methods with different return types or parameter types. Youre not bound by these method signatures in the same way that youre bound by the required method signatures above.
private static int getMaxHeight(int n)
A method that returns the max height of a skip list with n nodes.
private static int generateRandomHeight(int maxHeight)
Returns 1 with 50% probability, 2 with 25% probability, 3 with 12.5% probability, and so on, without exceeding maxHeight.
private void growSkipList()
Grow the skip list using the procedure described above for the insert() method.
private void trimSkipList()
Trim the skip list using the procedure described above for the delete() method.
None of the methods described above should print anything to the screen. Printing anything to the screen will likely resolve in tragic test case failure.
Recall that your code must compile, run, and produce precisely the correct output on Eustis in order to receive full credit. Heres how to make that happen:
1. To compile your program with one of my test cases:
javac SkipList.java TestCase01.java
2. To run this test case and redirect your output to a text file:
java TestCase01 > myoutput01.txt
3. To compare your programs output against the sample output file Ive provided for this test case:
diff myoutput01.txt sample_output/TestCase01-output.txt
If the contents of myoutput01.txt and TestCase01-output.txt are exactly the same, diff wont print anything to the screen. It will just look like this:
seansz@eustis:~$ diff myoutput01.txt sample_output/TestCase01-output.txt
seansz@eustis:~$ _
Otherwise, if the files differ, diff will spit out some information about the lines that arent the same.