Question

Skip list, needs to be implemented in Java:

- Implement the class NodeSkipList with two components, namely key node and array of successors. You can also add a constructor, but you do not need to add any method. - In the class SkipList implement a constructor SkipList(long maxNodes).

The parameter maxNodes determines the maximal number of nodes that can be added to a skip list. Using this parameter we can determine the maximal height of a node, that is, the maximal length of the array of successors.

As the maximal height of a node it is usually taken the logarithm of the parameter. Further, it is useful to construct both sentinels of maximal height.

- In the class SkipList it is useful to write a method which simulates coin flip and returns the number of all tosses until the first head comes up. This number represents the height of a node to be inserted.

2 - In the class SkipList implement the following methods:

(i) insert, which accepts an integer and inserts it into a skip list. The method returns true, if the element is successfully inserted and false, if the element already exists in the data structure.

(ii) search, which accepts an integer and finds it in a skip list. The method returns true, if the element is successfully found and false otherwise.

(iii) delete, which accepts an integer and deletes it from a skip list. The method returns true, if the element is successfully deleted and false otherwise.

Answer 1

public class Node {
    int element;

    public Node(int value) {
        element = value;
    }

    public Node() {
    }
}

------------------------------------------------

public class NodeSkipList {
    Node key;
    Node[] successors;

    public NodeSkipList(int maxNodes) {
        key = new Node();
        successors = new Node[maxNodes];
    }
}

------------------------------------------------

public class SkipList {
    private NodeSkipList nodeSkipList;
    private int maxNodes;

    SkipList(long maxNodes) {
        this.maxNodes = (int) Math.log(maxNodes);
        nodeSkipList = new NodeSkipList(this.maxNodes);
    }

    private long simulateCoinFlip() {
        long count = 0;
        while (true) {
            if (Math.random() < 0.5)
                count++;
            else
                return count;
        }
    }

    boolean insert(int value) {
        if (search(value))
            return false;
        long height = simulateCoinFlip();
        if (maxNodes <= height)
            return false;
        nodeSkipList.successors[(int) height] = new Node(value);
        return true;
    }

    boolean search(int value) {
        for (Node node : nodeSkipList.successors) {
            if (null != node && node.element == value)
                return false;
        }
        return true;
    }

    boolean delete(int value) {
        int position = 0;
        for (Node node : nodeSkipList.successors) {
            if (null != node && node.element == value) {
                nodeSkipList.successors[position] = null;
                return true;
            }
            position++;
        }
        return false;
    }
}