CSSE 230
SkipList Programming Assignment

Overview

The purpose of this exercise is to understand in detail the mechanics of insertion and removal of elements from skip lists.

We discussed two different data-structure approaches to implementation in class. In the first approach, each node contains a Comparable element and an ArrayList of pointers. This is like the picture on the board and the applet used in class. The ArrayList size will be between 1 and some fixed maximum - for this assignment, that maximum will always be 10. In the second approach (from the Goodrich and Tomassia book, which was in the PowerPoint slides), a skip list node is itself a list of nodes, each with four pointers (up, down, left, right).

For this assignment, you are to use the first approach. Thus a Node in a SkipList has only two fields:
   private T element;
   private ArrayList<Node> links;

  1. This is an individual assignment.
  2. Checkout the SkipList project from your individual CSSE 230 SVN repository.
  3. Implement public boolean insert(T e) and public boolean remove(T e) methods.
  4. The header node is to have a size of MAX_LINKS (10). This is the maximum size of any node in the skip list.
  5. For testing purposes, your SkipList constructor needs to receive an array of integers, either 0 or 1. Use these numbers instead of the random number generator. 1 means to add another level to the node and 0 means stop. The first 0 in the array is used for the header node, but is ignored because that node always has MAX_LINKS pointers. All numbers in the array after that zero and up to and including the next zero are used in the initialization of the first data-containing node that is inserted into the skip list. For example, if the first numbers in the array were 0, 1, 1, 0, 1, 0, the first inserted node would contain 3 pointers and the second inserted node would contain 2 pointers. If there are enough insertions so that the array runs out (as in the first JUnit test's first skip list), simply "wrap around" by going back to the beginning of the array.
  6. Here is a more concrete example. Constructing a SkipList with the following initialization array: [0,0,1,1,0,1,0,1,1,1,0,1,1,0] and inserting the following numbers in this order: 5,7,6,6,4, results in the following skip list: 
    [r [0: 4][1: 4][2: 4][3: 6][4: null][5: null][6: null][7: null][8: null][9: null]]
[4 [0: 5][1: 6][2: 6]]
[5 [0: 6]]
[6 [0: 6][1: 6][2: 7][3: null]]
[6 [0: 7][1: 7]]
[7 [0: null][1: null][2: null]]
  7. Testing: For testing purposes, we have added
    1. A method getNodesVisited() to SkipList, which returns the number of nodes that have been visited during insertion and deletion. You must increment the corresponding field every time your code visits a node in the skip list (other than the root or tail).
    2. A method getRoot() to SkipList, which returns the root (header) node of the SkipList. You don't need to do anything extra here.
    3. A method getLinks() to Node which returns an ArrayList of the node's links. You don't need to do anything extra here.
  8. We have provided some preliminary JUnit tests, enough for you to at least see how the interface works. We welcome additional unit test contributions from students - just email them to your instructor!
  9. It may be helpful to write a toString() method in the SkipList and Node classes, which enables you to visualize the nodes and their links. Such methods were used to produce the output shown above.
  10. Even better, you may find it helpful to write a graphical display of your SkipList like shown in the applet . We'll give +10% for simple displays showing the nodes of various heights, and even more for interactive ones that allow the user to insert or delete elements (like the applet).
  11. Commit your completed code to your repository.