SkipList implementation in Java

The code works fine, but could likely be better. How can I improve it?

From Wikipedia:

A skip list is a data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one. Searching starts in the sparsest subsequence until two consecutive elements have been found, one smaller and one larger than or equal to the element searched for. Via the linked hierarchy, these two elements link to elements of the next sparsest subsequence, where searching is continued until finally we are searching in the full sequence

```
public class SkipList>{

int maxLevels;
Random rand = new Random();
Node first;
int size;

public SkipList(int listLevels){
this.maxLevels = listLevels;

first = new Node(null);
Node d = new Node(null);
first.down = d;

for(int j = listLevels - 2; j >= 0; j--){

d.down = new Node(null);
d = d.down;
}
}

/*
*Makes a new Node containing data and links the node to the node
*previous and after on all levels from the nodes height and below.
*/

public void insert(T data){

int levels = setHeight();
Node newNode = new Node(data);
Node node = first;

for(int i = maxLevels; i > levels; i--){
node = node.down;
}

for(int i = levels; i >= 1; i--){

Node previous = findPreviousNodeOnLevel(data, node);
newNode.next = previous.next;
previous.next = newNode;

if(i > 1){
newNode.down = new Node(data);
newNode = newNode.down;
node = previous.down;
}
}
size++;
}

/*
* Gives a random number between 1 and maxLevels
*/
private int setHeight(){
int n = 0;
int level = 0;
while( n != 1 && level < maxLevels){
n = rand.nextInt(2) + 1;
level ++;
}
return level;
}

/*
* Finds @param data in the list
*/
public

The goal of a skip list is that you can do a find by doing a loop like:

Node find(T value){
    Node start = root;

    while(start!=null && comp(start.value, value) != 0){

        if(comp(start.next.value, value) < 0){
            start = start.next;
        }else{
            start = start.down;
        }

    }
    return start;
}

Note the comp helper function. I added that so you can easily make it use a custom Comparable passed in during construction.

This can be easily expanded to also keep a list of nodes to update should you want to insert/delete a value:

List findAllPrevs(T value){
    List prevs = new ArrayList<>();
    Node start = root;

    while(start!=null){

        if(comp(start.next.value, value) < 0){
            start = start.next;
        }else{
            prevs.add(start);
            start = start.down;
        }

    }
    while(prevs.get(prevs.size()-1).down!=null){
        prevs.add(prevs.get(prevs.size()-1).down);
    }
    return prevs;
}

Then you only need to update the last depth nodes in prevs when you add or remove a value.

StackExchange Code Review Q#157715, answer score: 5