Help with SkipList Implementation in Java

SkipLists Implementation

Write code that implements and exercises skiplists.

Interfaces

Interface SkipList_Interface

package SkipList; /* Interface: The skiplist will provide this collection of operations: insert: in: a string (the element to be stored into the skiplist) return: boolean, return true if insert is successful, false otherwise effect: if the string is already in the skiplist, then there is no change to the skiplist state, and return false if the string is not already in the skiplist, then a new skiplist node is created, the string put into it as data, the new node is linked into the skiplist at the proper place; size is incremented by 1, and return a true remove: in: a string (the element to be taken out of the skiplist) return: boolean, return true if the remove is successful, false otherwise this means return false if the skiplist size is 0 effect: if the element being looked for is in the skiplist, unlink the node containing it and return true (success); size decreases by one if the element being looked for is not in the skiplist, return false and make no change to the skiplist state contains: in: a string (the element to be seaarched for) return: boolean, return true if the string being looked for is in the skiplist; return false otherwise this means return false if skiplist size is 0 effect: no change to the state of the skiplist findMin: in: none return: string, the element value from the skiplist that is smallest effect: no skiplist state change error: is skiplist size is 0, return null findMax: in: none return: string, the element value from the skiplist that is largest effect: no skiplist state change error: is skiplist size is 0, return null size: in: nothing return: number of elements stored in the skiplist effect: no change to skiplist state empty: in: nothing return: boolean, true if the skiplist has no elements in it, true if size is 0 return false otherwise effect: no change to skiplist state level: in: none return: integer, the level of the highest node in the skiplist effect: no change in skiplist state error: return -1 if skiplist is empty (size is 0, only head and tail nodes are there) getHead: in: none return: a skiplist node, the one that is the starter of the entire skiplist means return a null if the skiplist is empty effect: no change to skiplist state */ // ADT operations public interface SkipList_Interface { public boolean insert(String s); public boolean remove(String s); public String findMin(); public String findMax(); public boolean empty(); public boolean contains(String s); public int size(); public int level(); public SkipList_Node getHead(); } 

Class SkipList_Node

package SkipList; public class SkipList_Node { String data; int level; SkipList_Node[] forward; SkipList_Node(String s, int level) { this.data = s; this.level = level; this.forward = new SkipList_Node[level + 1]; }} // --- fill in these methods ------------------------------------------ // // at the moment, they are stubs returning false // or some appropriate "fake" value // // you make them work properly // add the meat of correct implementation logic to them // you MAY change the signatures if you wish... // make the take more or different parameters // have them return different types /* public boolean setForward(int level, SkipList_Node forward) { return false; } String getData() { return null; } */ // --- end fill in these methods -------------------------------------- // -------------------------------------------------------------------- // you may add any other methods you want to get the job done // -------------------------------------------------------------------- } 

Class SkipList

package SkipList; public class SkipList implements SkipList_Interface { SkipList_Node head; SkipList_Node tail; int level; int size; static final int levelSize = 100; double probability = 0.5; SkipList() { head = new SkipList_Node(null, levelSize); tail = new SkipList_Node(null, levelSize); for (int i = 1; i <= levelSize; i++) { head.setForward(i, tail); } level = 0; size = 0; } @Override //used for testing, please leave as is public SkipList_Node getHead() { if (size == 0) return null; return head; } //use this when creaing a new node, please leave as is public int randomLevel() { int level = 1; while (Math.random() < probability) level++; return level; } } 

Notes

In the beginning, there are only two initial nodes called head and tail and all the forward pointers of the head node point to the tail. Their string data is null and they should not be changed in any case.

When a new node is inserted, it needs to be placed between the head and tail nodes and relevant pointers should be rearranged accordingly. A right place for a newly-created node should be searched with forward pointers starting from the head node. When creating a node for insertion, it should get a level along with string data. The level should be determined by using randomLevel method provided in SkipList class, which randomly generates each level with probability 0.5. The maximum level of a node in skiplist is pre-defined as 100 in class SkipList. We expect the probability 0.5^100 is small enough to cover almost all levels generated by randomLevel method for our implementation.

For removing, the target node to be deleted should be first searched with forward pointers starting from the head node as same as insertion. Forward pointers of relevant nodes need to be adjusted correctly and the size of skiplist is decreased by one if remove succeed.