How to implement Skip List in Java? Example Tutorial

Hello friends, we meet again today. hope you all are excited and ready for today's journey. Today, we are gonna learn something that is not very common. It is used not very common, but, if used, it is a great strength to our time complexity reduction. So, what's the wait? Let's start! So, suppose we have a linked list with us which has 10 million records. Now, for searching a particular node, the time taken would be O(N). Where N is the size of the list. Similarly, the time taken for deletion of a Node, Insertion at a particular Node will also take O(N) time. Can we reduce it?

Think for 2 minutes and then we will discuss.

if you guys are thinking that binary search can be used to reduce the time complexity of any search to O(log(N)), for Linked List, for finding the middle Node, we still have to traverse it, So, not so much optimization we would achieve. Is there any other method? The answer is Yes! Let's see what it is.

1. What is Skip List in Java?

A skip list is a data structure that is based on probability. With a linked list, the skip list is used to hold a sorted list of components or data. It enables the pieces or data to be seen efficiently. It skips multiple components of the whole list in a single step, which is why it's called a skip list.

The linked list has been expanded to create the skip list. It allows the user to easily search for, delete, and insert the element. It is made up of a base list and a collection of items that keep the link hierarchy of the succeeding elements intact.

2. How is Skip List built?

You all must be wondering about the structure of the skip list and how it is built. Basically, skip lists has 2 components, the bottom layer, and the top layer/s. There may be multiple layers depending on the need, but there is one bottom layer that is fixed, the base sorted linked list structure. The skip list's bottom layer is a normal sorted linked list, while the above levels are like an "express line" where the entries are skipped.

3. Working of skip list:

Let's look at an example to see how the skip list works. We have a few nodes in this example, which have been split into two levels as indicated in the picture.

As shown in the diagram, the lower layer is a common line that connects all nodes, while the upper layer is an express line that connects just the major nodes.

In this case, let's say you're looking for 45. You'll begin your search at the first node of the express line and continue running until you reach a node that is equal to or greater than 45.

Because 45 does not exist in the express line, you must look for a node with a value smaller than 45, which is 30. Now, you continue the search for Node 45 in the normal lane from 30. As you can see, we achieve node 45 after 2 traversals from node 30.

Here, we have demonstrated the use of 1 layer as the top layer, there can be multiple layers that work similarly and provide more accurate and better results depending upon the need.

4. Basic operations of Skip List:

• Insertion operation: This operation is used to add a new node to a given position in a scenario.
• The deletion operation is used to remove a node from a network in a certain scenario.
• Search Operation: In a skip list, the search operation is used to find a certain node.

Now, you all must be wondering that we now know what a skip list is and how it works! but, we still don't know how it is actually used as far as implementation is concerned. Do not worry, we will check that out now. Let's see the code of the skip list. Brace yourselves as the code is slightly heavy :p

5. Java SkipList Code Example

Here is our complete Java program to implement Skip List and how to use it

import java.util.Random;

interface SkippableList<T extends Comparable<? super T>> {

    int LEVELS = 5;

    boolean delete(T target);
    void print();
    void insert(T data);
    SkipNode<T> search(T data);
}

class SkipNode<N extends Comparable<? super N>> {

    N data;
    @SuppressWarnings("unchecked")
    SkipNode<N>[] next = (SkipNode<N>[]) new SkipNode[SkippableList.LEVELS];

    SkipNode(N data) {
        this.data = data;
    }

    void refreshAfterDelete(int level) {
        SkipNode<N> current = this;
        while (current != null && current.getNext(level) != null) {
            if (current.getNext(level).data == null) {
                SkipNode<N> successor = current.getNext(level).getNext(level);
                current.setNext(successor, level);
                return;
            }

            current = current.getNext(level);
        }
    }

    void setNext(SkipNode<N> next, int level) {
        this.next[level] = next;
    }

    SkipNode<N> getNext(int level) {
        return this.next[level];
    }

    SkipNode<N> search(N data, int level, boolean print) {
        if (print) {
            System.out.print("Searching for: " + data + " at ");
            print(level);
        }

        SkipNode<N> result = null;
        SkipNode<N> current = this.getNext(level);
        while (current != null && current.data.compareTo(data) < 1) {
            if (current.data.equals(data)) {
                result = current;
                break;
            }

            current = current.getNext(level);
        }

        return result;
    }

    void insert(SkipNode<N> skipNode, int level) {
        SkipNode<N> current = this.getNext(level);
        if (current == null) {
            this.setNext(skipNode, level);
            return;
        }

        if (skipNode.data.compareTo(current.data) < 1) {
            this.setNext(skipNode, level);
            skipNode.setNext(current, level);
            return;
        }

        while (current.getNext(level) != null 
                && current.data.compareTo(skipNode.data) < 1 &&
                current.getNext(level).data.compareTo(skipNode.data) < 1) {

            current = current.getNext(level);
        }

        SkipNode<N> successor = current.getNext(level);
        current.setNext(skipNode, level);
        skipNode.setNext(successor, level);
    }

    void print(int level) {
        System.out.print("level " + level + ": [ ");
        int length = 0;
        SkipNode<N> current = this.getNext(level);
        while (current != null) {
            length++;
            System.out.print(current.data + " ");
            current = current.getNext(level);
        }

        System.out.println("], length: " + length);
    }

}

public class SkipList<T extends Comparable<? super T>> implements SkippableList<T> {

    private final SkipNode<T> head = new SkipNode<>(null);
    private final Random rand = new Random();

    @Override
    public void insert(T data) {
        SkipNode<T> skipNode = new SkipNode<>(data);
        for (int i = 0; i < LEVELS; i++) {
            if (rand.nextInt((int) Math.pow(2, i)) == 0) {
                //insert with prob = 1/(2^i)
                insert(skipNode, i);
            }
        }
    }

    @Override
    public boolean delete(T target) {
        System.out.println("Deleting " + target);
        SkipNode<T> victim = search(target, true);
        if (victim == null) return false;
        victim.data = null;

        for (int i = 0; i < LEVELS; i++) {
            head.refreshAfterDelete(i);
        }

        System.out.println("deleted...");
        return true;
    }

    @Override
    public SkipNode<T> search(T data) {
        return search(data, true);
    }

    @Override
    public void print() {
        for (int i = LEVELS-1; i >= 0 ; i--) {
            head.print(i);
        }
        System.out.println();
    }

    private void insert(SkipNode<T> SkipNode, int level) {
        head.insert(SkipNode, level);
    }

    private SkipNode<T> search(T data, boolean print) {
        SkipNode<T> result = null;
        for (int i = LEVELS-1; i >= 0; i--) {
            if ((result = head.search(data, i, print)) != null) {
                if (print) {
                    System.out.println("Found " + data.toString() 
                        + " at level " + i + ", so stopped" );
                    System.out.println();
                }
                break;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        SkipList<Integer> sl = new SkipList<>();
        int[] data = {4,2,7,0,9,1,3,7,3,4,5,6,0,2,8};
        for (int i : data) {
            sl.insert(i);
        }

        sl.print();
        sl.search(4);

        sl.delete(4);

        System.out.println("Inserting 10");
        sl.insert(10);
        sl.print();
        sl.search(10);
    }

}

Output:



Now, let's see it's advantages and disadvantages so that we can be sure where and how to use them accurately.

6. Advantages of skip list:
Because there are no rotations in the skip list, if you wish to add a new node to it, it will be inserted extremely quickly. 
In comparison to the hash table and the binary search tree, the skip list is straightforward to implement. 
Because the nodes are stored in sorted order, finding a node in the list is relatively straightforward. 
The skip list method may be readily changed to create more particular structures like indexable skip lists, trees, or priority queues. 
The skip list is a solid and trustworthy list.

7. Disadvantages of skip list Data Structure
It needs a greater amount of memory than the balanced tree.
Reverse search is not permitted.

Now, after discussing the advantages and disadvantages, lets see if actually is there any scenario where 
skip lists can be used? think for 2 minutes and let us discuss afterwards.

It represents pointers and systems in distributed applications and is utilized in distributed applications.
It's used to create a dynamic, elastic concurrent queue with little lock contention. 
The QMap template class also makes use of it.
In running median issues, the indexing of the ski p list is employed.

So, now I guess you guys would be pretty confident about skip lists. 
Do try hands-on for skip lists and try 
to change levels and observe the time complexity for each one. Let's meet again in the next article! 

Until then, happy skipping :p

Related Java Collection tutorials  you may like
How does get() method of HashMap work in Java? (answer)
Difference between ConcurrentHashMap and HashMap in Java? (answer)
How HashSet internally works in Java? (answer)
How ConcurrentHashMap internally works in Java? (answer)
Difference between HashMap and Hashtable in Java? (answer)
What is the difference between ArrayList and HashMap in Java? (answer)
Difference between HashSet and HashMap in Java? (answer)
HashMap and LinkedHashMap in Java? (answer)

The best way to iterate over HashMap in Java? (answer)

How to sort the HashMap on keys and values in Java? (solution)

3 ways to loop over a Map in Java? (example)

The difference between HashMap and ConcurrentHashMap in Java? (answer)
What is the difference between ArrayList and HashMap? (difference)
How to convert Map to List in Java? (solution)

Thanks for reading this article so far. If you like this SkipList example tutorial in Java then please share with your friends and colleagues. If you have any questions or feedback, please ask in comments. 

P. S. - If you are new to Java Programming and Development and want to learn core Java in depth, you can also checkout these 10 Free Core Java Courses to start with. It contains best free Java courses from Udemy and Coursera for beginners.