Searching for element in Skip List

Question

I'm having some difficulty coding up a way to find an element in a Skip List.

I'm trying to implement it so that, if we're searching for an element and that element doesn't exist in the List, then return the next largest value; this would make it ideal for insertion. However, if the element is located, then return that element.

I use this for my remove(T key) method; if we find the element, then remove it. If it isn't in the list, throw new java.util.NoSuchElementException().

While my current implementation works okay for insertion, I've come to find out that it doesn't work at finding an existing element--instead, it will get the next value. (It shouldn't technically work for insertion, but it does).

********************** SkipList (size = 3) Level: 2 (null), , , (5) Level: 1 (null), (3), (4), (5) **********************

Above, is what the Skip List looks like currently.

Below, is the structure of the Skip List I'm making. The Left-Hand sentinels are nodes with data that is null; we also have a phantom node acting as the head; the phantom head helps us keep track of the current number of levels in the Skip List. Diagram of structure

private Node<T> search(T key) {
    Node<T> node = head;
    boolean found = false;

    while (!found) {
        while (compare(node.getNext().getData(), key) <= 0) {
            node = node.getNext();
        }
        if (node.getDown() != null) {
            node = node.getDown();
        } else {
            node = node.getNext();
            found = true;
        }
    }
    return node;
}

In its current state, if we try search(4), the returned node will be 5, even though 4 is in the list.

Answer 1

I'm seeing a number of problems here.

1. Where are you actually returning the value? I see no return statement, though I presume you just left out a return node; at the bottom.

2. You're never verifying that the final value is indeed what you're looking for. You need some way to indicate that a value wasn't found, I'm assuming?

3. You currently just decide that you found the node if you weren't able to go down.

I think you need to re-think the algorithm a bit. Try this code:

private Node<T> search(T key) {
    Node<T> node = head;
    boolean found = false;

    while (!found) {
        //special case to return a node containing null - indicates value not in list
        if (node == null) return new Node(null);
        //We found it!
        else if (node.getData().equals(key)) found = true;
        //Go to the next one over if it's not too high.
        else if (node.getNext() != null && compare(node.getNext().getData(), key) <= 0) node = node.getNext();
        //It was too high, so go down instead.
        else node = node.getDown();
    }
    return node;
}

Note the checking for a null condition in the inner while loop - this prevents you from calling getData() on a non-existent next node, which would result in a null pointer exception. Also note how you don't check for null values going down. This is because you only encounter it if it's not in the list, so the special case at the start will catch that null value the next time the loop executes.

You can also tweak how it checks if the values are equal. I used .equals but you can change it to use the compare method, depending on how you check for equality.