SkipList implementation in Java

Question

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<T extends Comparable<T>>{

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 T get(T data){
    Node node = getPreviousNode(data);
    if(node == null || node.next == null || node.next.data == null){
        return null;
    }
    return getPreviousNode(data).next.data;
}

/*
 * Removes @param data from the list
 */

public boolean remove(T data){
    Node previous = getPreviousNode(data);
    if(previous.next != null){
        Node toRemove = previous.next;
        previous.next = toRemove.next;

        while(toRemove.down != null){
            toRemove = toRemove.down;
            previous = findPreviousNodeOnLevel(data, previous.down);
            previous.next = toRemove.next;
        }

        return true;
    }

    return false;
}

/*
 * Returns the node that is before @param data in the list.
 */
private Node getPreviousNode(T data){
    Node previous = findPreviousNodeOnLevel(data, first);

    while(true){
        if(previous.next != null && previous.next.data.equals(data)){
            return previous;
        }

        if(previous.down != null){
        previous = previous.down;
        previous = findPreviousNodeOnLevel(data, previous);
        }
        else{
            return null;
        }
    }
}

/*
 * Returns the node before @param data at the same height/level as @param current
 */
private Node findPreviousNodeOnLevel(T data, Node current){

    while(current.next != null && current.next.data.compareTo(data) < 0){  
        current = current.next;
    }
    return current;
}


public int getSize(){
    return size;
}

private class Node {

    T data;
    Node next;
    Node down;

    Node(T data){
        this.data = data;
    }
}

}

Answer 1

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<T> 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<Node> findAllPrevs(T value){
    List<Node> 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.