Skip-list that uses a singly linked list implementation

Question

I've implemented this skip-list yesterday, and I'd like suggestions on how to improve this code, and my coding practices.

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class SkipList<T extends Comparable <T>> {

    List<Node<T>> levels;

    public SkipList(){
        this.levels = new ArrayList<Node<T>>(1);
        this.levels.add(new Node<T>());
    }


    public T search(T value){
        Node<T> focus = this.levels.get(levels.size()-1);
        if(focus.next != null && focus.next.value.compareTo(value)<0)
            focus = focus.next;
        while(value != focus.value){
            // go as far as you can on this level
            while(focus.next != null && value.compareTo(focus.next.value) > 0)
                focus = focus.next;

            if(value == focus.value)    return value;
            // if not go down one level
            if(focus.down == null)  return null;
            else    focus = focus.down;
        }
        return null;
    }

    public void insert(T value){
        if(search(value) != null)
            return;
        // coin flips
        Random rand = new Random();
        int coinFlip = 0;
        while(rand.nextInt(2)==1)
            coinFlip++;
        // check levels height is not less then coin flip
        int before = levels.size();
        if(coinFlip >= before){
            for(int i=coinFlip ; i >= before ; i--)
                levels.add(new Node<T>());
            for(int i=levels.size()-1 ; i > 0 ; i--)
                levels.get(i).down = levels.get(i-1);
        }
        // insert to all lower level
        Node<T> ins = new Node<T>(value);
        Node<T> remember = ins;
        for(int i=coinFlip ; i >= 0 ; i--){
            // insert to all the levels from coin flip down and remember to set down
            insertToLevel(ins,i);
            if(i == 0) break;
            remember = ins;
            ins = new Node<T>(value);
            remember.down = ins;
        }
    }

    private void insertToLevel(Node<T> node,int i){
        Node<T> focus = levels.get(i);
        Node<T> prev = focus;
        if(focus.next == null){
            focus.next = node;
            return;
        }
        prev = focus;
        focus = focus.next;
        while( focus.next != null && node.value.compareTo(focus.value) > 0 ) {
            prev = focus;
            focus = focus.next;
        }
        if(focus.value == null || focus.value.compareTo(node.value) < 0)    focus.next = node;
        else{
            prev.next = node;
            node.next = focus;
        }
    }

    public void delete(T value){
        int highestLevelFound = levels.size()-1;
        Node<T> focus = this.levels.get(highestLevelFound);
        while( !( focus.next != null && focus.next.value.compareTo(value)<=0 )  ){
            focus = focus.down;
            highestLevelFound--;
        }
        focus = focus.next;
        while(value != focus.value){
            // go as far as you can on this level
            while(focus.next != null && value.compareTo(focus.value) > 0)
                focus = focus.next;

            // if it's a hit break, it's on this level
            if(value == focus.value) break;
            // if not go down one level
            if(focus.down == null)  return;
            else{
                focus = focus.down; 
                highestLevelFound--;
            }
        }
        for(int i=highestLevelFound ; i >= 0 ; i--){
            deleteFromLevel(value,i);
        }
        while(this.levels.get(highestLevelFound).next == null && highestLevelFound>0){
            this.levels.remove(highestLevelFound);
            highestLevelFound--;
        }
    }

    private void deleteFromLevel(T value,int i) {
        Node<T> focus = levels.get(i);
        Node<T> prev = focus;
        while(value != focus.value){
            prev = focus;
            focus = focus.next;
        }
        prev.next = focus.next;
    }

}

class Node<T>{
    T value;
    Node<T> next;
    Node<T> down;

    public Node(){}

    public Node(T value){
        this.value = value;
    }
}

Answer 1

This is a code review at a high level, as I'm a bit rusty on my java, and I don't have the time to go into detail, but I do have some comments to your code.

Choose an indentation style

In your code you have multiple indentation styles, and this makes your code harder to read and understand. At some point in time it will most likely cause errors as well. This was your code:

   if(focus.value == null || focus.value.compareTo(node.value) < 0)    focus.next = node;
   else{
       prev.next = node;
       node.next = focus;
   }

This just doesn't look nice. You have a single line hidden after the if without braces, and then you have yammed the else up there, and it is kind of hard when reading the code to see what is really happening here.

Two suggestions: Always have braces around the blocks belonging to if``,whileandfor`, and make a choice and stick to it regarding where to put starting braces. Either choose to have starting braces on the same line, or the next line. Here is an example using the next line:

   if(focus.value == null || focus.value.compareTo(node.value) < 0)  
   {
       focus.next = node;
   }
   else
   {
       prev.next = node;
       node.next = focus;
   }

Avoid repetition of code

It seems like you duplicate some of the code. When searching, deleting and inserting, you will use the same code to find your point of action. This can extracted into a separate method, and thus simplifying the other three.

As a general note, if you keep copy-and-paste code, you need to reconsider if is not better to use a function instead!

Single consern

A neat principle to consider is the single concern principle, which states that a method/class/whatever should do only one thing, and do that well. In order to achieve this you would need to make more methods, and simplify the logic. Given that the logic is correct, a somewhat remodelled insert could become:

public void insert(T value)
{
  // Break out, if value is already in the list
  if (search(value) != null) {
     return;
  }

  int levelHeight = checkAndModifyLevelHeight();

  insertNewNodeAtCorrectLevel(newLevelHeight, value);
}

Not sure if I understood your concept, but you get the gist of it. Simplify to a point where it is easy to understand what any given method does. Move stuff which is not essential to a method into a submethod, i.e. the coinflip stuff.

Answer 2

To extend helroys answer: you should also think about spaces inside of braces or around operators. Sometimes you have spaces between braces and a statement:

while( focus.next == null || focus.value.compareTo(node.value) < 0 )

But not every time (here also with operator):

while(rand.nextInt(2)==1)

Or you are mixing:

for(int i=coinFlip ; i >= before ; i--)

Next I noticed in search() and insertToLevel and delete

focus.next.value.compareTo(node.value) < 0
node.value.compareTo(focus.next.value) > 0

This is the same thing written in to ways. You have to think about both lines. It is not like "hey, I saw this three lines ago, they doing the same". And those lines have a potential NullPointer bug: you check for focus.next not to be null, but don't check focus.next.value. And you don't check value not to be null.

---

Your search()-method is very strange.

First I thought: you named the Node focus But you working with focus.next. So focus isn't really your focus until you found the right node.

But then I noticed: you have a while loop which says "do following stuff until focus has the same value like value. But inside the loop you are returning a value which (by the condition) shouldn't be there.

Then the if statement before the while loops: they seem to do the same thing like the while loops. Even though this handles the first node, you probably don't need this.

Maybe you could get rid of then inner while loop and make the whole much Easier and cleaner.

Last thing here: you compare two generic objects by ==. You should compare with equals(), so you can search for a logical equal object.

Now talking about the semantics of search(): you give it a value and its returning the same value or null. If you are going to use equals, you probably could return the original object from your list. Than you can search for a logical equal object in your list. But I think this should be a contains()-method which returns true or false.

---

Ever time you call insert() you create a Random object. This is ok, because you get a Random object with a new seed. But you should make this a class property, so you only have to create one of it. This is a performance bug.

Maybe you can extract the coin flip behavior in a CoinFlipper class.

---

The second parameter of insertToLevel() has a bad name. It should be level. (You could name the control variable of the for loop in insert() level as well). See deleteFromLevel as well.

---

As you wrote in a comment blow your post you can improve delete(). Like helroy wrote, you should write a new method which searches for a node and one method for the previous node, after which a new node will be inserted. This would make many methods smaller and cleaner.

In general this is code is a good start. I don't know if you have written unit tests, you should to find other bugs. You also should read the whole code again and try to think about the big picture: how should the class and its methods be used? Which inputs will it get? How often will a method get called (like insert which will be called often, and the new Random object could be a bottleneck)? Hat is the semantics of a method? Is a method or the class really doing only one think (like coin flipping; here it probably is okey, because it is not worth to create a new class for such a little feature, or searching for a node and then inserting, inserting needs the search but it shouldn't be done in the same method)?

I don't know anything about your background (if you just started to learn, study, or do programming for some years) I don't want to scare you off in any way. I think to refactor a class to make it clean and shiny you could twice or mor of the time you needed to write it in the first place! And to ask other developers is on of the best steps in the right direction you can do!