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;
- This is an individual assignment, SkipList, in your individual repository.
- Implement public boolean insert(T e) and public boolean
remove(T e) methods.
- The dummy head 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.
- 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. A randomly-generated 1 means to add another level to the
node and 0 means
stop. In a given sequence of random numbers, all numbers up to and
including the first 0 are
used in the initialization of the first data-containing node that is
inserted into the skip list. For example, if the first numbers were 1,
1, 0, 1, 0, then the first inserted node would contain 3 links and the
second inserted node would contain 2 links.
- 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]]
- 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.)
- Testing: For testing purposes, we have added
- A method getNodesVisited() to SkipList, which returns the total 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). Don't reset it every time you insert or delete.
- A method getHead() to SkipList, which returns the head node of the SkipList. You don't need to do anything extra here.
- A method getLinks() to Node which returns an ArrayList of the node's links. You don't need to do anything extra here.
- 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!
- 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.
- 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).
- Commit your completed code to your repository.