Custom SkipList implementation in Java

Question

I recently studied SkipList and thought I would create one on my own. This implementation uses a 2 layer `SkipList where the size of the support list is roughly square root of the size of the original list.

package skiplists.skiplist;
public class SkipList<T extends Comparable<T>> {
private SkipNode<T> start;
private SkipNode<T> end;
private SkipNode<T> supportStart;
private SkipNode<T> supportEnd;
private int size;
private int sizeSupport;
public T getStart() {
 return start.getData();
}
public T getEnd() {
 return end.getData();
}
public int getSize() {
 return size;
}
public void add(T data){
 if(start == null){
 insertAsFirstElement(data);
 }
 else{
 insert(data);
 }
}
private void insertAsFirstElement(T data){
 SkipNode<T> node = new SkipNode<>(data);
 start = node;
 end = node;
 size++;
 SkipNode<T> supportNode = new SkipNode<>(data); 
 supportStart = supportNode;
 supportEnd = supportNode;
 supportNode.setDown(node);
 sizeSupport++;
}
//Adding element in the end assuming user enters data in ascending order
private void insert(T data){
 SkipNode<T> node = new SkipNode<>(data);
 end.setNext(node);
 node.setPrevious(end);
 end = node;
 size++;
 int expectedSupportSize = (int) Math.sqrt(size);
 if(sizeSupport < expectedSupportSize){
 SkipNode<T> supportNode = new SkipNode<>(data);
 supportEnd.setNext(supportNode);
 supportNode.setPrevious(supportEnd);
 supportEnd = supportNode;
 supportNode.setDown(node);
 sizeSupport++;
 if(sizeSupport > 2)
 reAjustSupportList();
 }
}
/*readjusting the support list so that they point to the correct nodes when new 
*support nodes are added
*/
private void reAjustSupportList(){
 SkipNode<T> navigationNode = supportStart.getNext();
 int i = 1; 
 while(navigationNode != supportEnd){
 SkipNode<T> tempNode = navigationNode.getDown();
 for(int j = 1 ; j <= i ; j++){
 tempNode = tempNode.getNext();
 }
 navigationNode.setDown(tempNode);
 navigationNode.setData(tempNode.getData());
 navigationNode = navigationNode.getNext();
 i++;
 }
}
public boolean search(T data){
 SkipNode<T> navigationNode = supportStart;
 if(data.compareTo(navigationNode.getData()) < 1){
 return false;
 }
 while(navigationNode != null && navigationNode.getNext() != null && (data.compareTo(navigationNode.getNext().getData()) > 0 || data.compareTo(navigationNode.getData()) == 0)){
 navigationNode = navigationNode.getNext();
 }
 SkipNode<T> searchNodeStart = navigationNode.getDown();
 SkipNode<T> searchNodeEnd = navigationNode.getNext().getDown();
 while(searchNodeStart != searchNodeEnd){
 if(searchNodeStart.getData().compareTo(data) == 0){
 return true;
 }
 searchNodeStart = searchNodeStart.getNext();
 }
 return false;
}
private static class SkipNode<T>{
 public SkipNode(T data){
 this.data = data;
 }
 private SkipNode<T> next = null;
 private SkipNode<T> previous = null;
 private SkipNode<T> down = null;
 private T data;
 public SkipNode<T> getNext() {
 return next;
 }
 public void setNext(SkipNode<T> next) {
 this.next = next;
 }
 public SkipNode<T> getPrevious() {
 return previous;
 }
 public void setPrevious(SkipNode<T> previous) {
 this.previous = previous;
 }
 public SkipNode<T> getDown() {
 return down;
 }
 public void setDown(SkipNode<T> down) {
 this.down = down;
 }
 public T getData() {
 return data;
 }
 public void setData(T data) {
 this.data = data;
 }
}
}

I would like to receive review comments on this code (better ways to search in a SkipList and the adjusting mechanism). I have assumed the user enters the numbers in ascending order. I will apply some sorting mechanism later and post that code too.

• Landei: The one-based for-loop makes my eyes bleed...
• thepace: Could you provide me the source of your implementation? For size= 10 what are the support sizes and for size = 17, what are the support sizes? This will help me to optimise your code.
• thepace: I feel that the readjustSupportList can be optimised. So could you answer my above query for a thorough review.
• Ishan Soni: @thepace geeksforgeeks.org/skip-list

Answer 1

Unit testing

This is a fairly complex problem. It's good to have unit tests to verify the implementation is correct. Here are some examples:

public class SkipListTest {
 @Test
 public void test_with_30_50() {
 SkipList<Integer> list = new SkipList<>();
 list.add(30);
 list.add(50);
 assertEquals(2, list.getSize());
 assertEquals(new Integer(30), list.getStart());
 assertEquals(new Integer(50), list.getEnd());
 assertTrue(list.search(30)); // -> false
 assertTrue(list.search(50)); // -> npe
 assertFalse(list.search(51)); // -> npe
 assertFalse(list.search(33)); // -> npe
 }
 @Test
 public void test_with_30_40_50_60_70_80_90() {
 SkipList<Integer> list = new SkipList<>();
 list.add(30);
 list.add(40);
 list.add(50);
 list.add(60);
 list.add(70);
 list.add(80);
 list.add(90);
 assertEquals(7, list.getSize());
 assertEquals(new Integer(30), list.getStart());
 assertEquals(new Integer(90), list.getEnd());
 assertTrue(list.search(30)); // -> false
 assertTrue(list.search(40));
 assertTrue(list.search(50));
 assertTrue(list.search(60)); // -> false
 assertTrue(list.search(70)); // -> npe
 assertTrue(list.search(80)); // -> npe
 assertTrue(list.search(90)); // -> npe
 assertFalse(list.search(33));
 assertFalse(list.search(51));
 assertFalse(list.search(63)); // -> npe
 assertFalse(list.search(133)); // -> npe
 }
}

Notice the test cases where I added comments at the end of the line:

• // -> false -- these assertions fail, the calls don't produce the expected value
• // -> npe -- these assertions throw a NullPointerException

In other words, the search method is buggy.

Alternative implementation of .search

This implementation passes the above tests:

public boolean search(T data) {
 SkipNode<T> navigationNode = supportStart;
 int compare;
 while ((compare = data.compareTo(navigationNode.getData())) > 0
 && navigationNode.getNext() != null) {
 navigationNode = navigationNode.getNext();
 }
 if (compare == 0) {
 return true;
 }
 if (compare < 0) {
 navigationNode = navigationNode.getPrevious();
 }
 navigationNode = navigationNode.getDown().getNext();
 while ((compare = data.compareTo(navigationNode.getData())) > 0
 && navigationNode.getNext() != null) {
 navigationNode = navigationNode.getNext();
 }
 return compare == 0;
}

This implementation relies on the fact that the class supports only 2 layers. The algorithm is relatively simple:

• Iterate in the upper layer as long as the node value is smaller than the target
• If found an exact match, return
• If the node value is greater than the target, step back to the previous node
• Step down: we know there shouldn't be an NPE here, as we're in the top layer now
• Iterate in the lower layer as long as the node value is smaller than the target
• If the last comparison was equal, return true, otherwise return false

Notice the similarity in the iteration of the upper and lower layers. With a little more effort probably this can be generalized to support more layers.

Other implementation notes

This implementation covers only a small subset of the operations of a skip list:

• no real insert, items must be appended in ascending order
• no delete
• no multiple levels
• quite far from the concept explained on wikipedia, most notably there's no p factor

Naming

Some of the method and variable names are not great. I suggest renaming some of them:

• add is fine as it is, as it behaves like List.add, appending at the end
• Instead of insertAsFirstElement, how about simply insertFirst
• insert is really inappropriate, because the comment above it says, it adds an element at the end. So append would be better.
• sizeSupport is not a great name, usually it's better to make things like size, count, index and num as suffixes instead of prefixes. Also note that supportSize will line up nicely with the existing variables supportStart and supportEnd

Answer 2

For data structures it would be really nice to have some testing code as well, just to play with it and obviously for you to make sure it works. Also, the SkipList doesn't implement any interface, but I'm sure it would be easy to implement at least List, Iterable, oh yeah and toString would be nice as well.

Anyway I'll just start with some points I noticed; in general I think this looks good though.

• Formatting is a bit off, but that be copy&paste issues; SkipNode doesn't use the same amount of space between methods and the two comments can be formatted nicer.
• Using <> is great.
• Avoid Math.sqrt, you can simply square sizeSupport instead for the comparison.
• reAjustSupportList is missing a "d".
• The single extremely long line in search is not nice. Either put each condition in a single line, or move it into a method if you don't like that.

For the algorithmic part, well I guess since you only add at the end this is okay, but from what I gather from Wikipedia there is a bit more to skiplists in general; in particular the readjustment shouldn't be necessary (please correct me if I'm wrong on that one).

Answer 3

Some tips:

1. Your skip list consists of two lists. So use the same logic to search both the list:

   • traverse from supportStart to supportEnd to get the navigationNode.
   • traverse from navigationNode.down to navigationNode->next.down to get the searched node (as you have done).

2. Null checks:

   //data could be null.
   if(data.compareTo(navigationNode.getData()) < 1){
    return false;
   }
   // navigationNode.getNext() could be null.
   SkipNode<T> searchNodeEnd = navigationNode.getNext().getDown();
   

The search() looks fine other than this.