Explain the concept of skip list implementation java.

607    Asked by ankur_3579 in SQL Server , Asked on Oct 6, 2022
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>{
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;
    }
}
}
Answered by Amit verma

The goal of a skip list implementation java 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 xss=removed xss=removed>

Note the comp helper function. I added that so you can easily make it use a custom Comparable 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 findAllPrevs(T value){
    List pre vs = new ArrayList<>();
    Node start = root;
    while(start!=null){
        if(comp(start.next.value, value) < 0 xss=removed xss=removed while(prevs.get(prevs.size()-1).down!=null){>

Then you only need to update the last depth nodes in prevs when you add or remove a value.



Your Answer