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, SkipList, in your individual repository.
  2. Implement public boolean insert(T e) and public boolean remove(T e) methods.
  3. The head (root) node is to have a size of MAX_LINKS (10). This is the maximum size of any node in the skip list. You may also want to add a dummy tail node.
  4. For testing purposes, your SkipList constructor receives an integer that is used to seed the random number generator. Using a fixed seed is helpful for debugging. 1 means to add another level to the node and 0 means stop. All numbers in the array up to and including the first 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 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.
  5. Here is a more concrete example. Constructing a SkipList with the seed 3226867 gives this sequence of random numbers: [0,1,1,0,1,0,1,1,1,0,1,1,0]. 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]]
  6. Note in the example shown above that inserting duplicates is allowed, and that the duplicate item should be inserted before the original one. (Look at the 6 above - if you don't understand why the one of height 4 comes before the one of height 2, re-read bullet 4 above.)
  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 head or tail).
    2. A method getHead() to SkipList, which returns the head 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.