Updated April 10, 2023
Introduction to Skip List Java
Skip List Java is a Data Structure used for storing a sorted list of elements with help of a Linked list hierarchy that connects to subsequences of elements. Skip List allows to process item look up in an efficient manner. Skip list is a probabilistic data structure, which means it skips several elements in the entire list and hence known as a Skip list. We can take the skip list to be an extended version of a linked list. Similar to how the Linked list allows insertion, removal, and perform a search for the elements, the Skip list too allows to search elements, remove elements from the list, and insert elements. It will contain a base list that includes a set of elements that would maintain the link hierarchy of subsequent elements.
Syntax:
Skip List does not have a particular syntax, but it has an Algorithm. Before looking at the Algorithm, we need to check on the Types of Basic Skip List Operations.
- Insertion Operation: In Skip list, it is used to add a new node to a particular location in a specific situation
- Search Operation: In Skip list, it is used to search a particular node
- Deletion Operation: In Skip list, it is used to delete a node in a specific situation
Working of Skip List in Java
So let’s see How Skip List actually works in an Algorithmic way.
Insertion Algorithm
Step 1: Deciding node levels as each element in the list is represented by node and level of a node is chosen randomly at the time of insertion in the list
Step 2: Level for a node is decided based on the below steps
Step 3: Find Max Level to be the upper bound on the count of levels in the skip list, which is determined by L(N) = logp/2N. This assures that random level will be greater than Max Level
Step 4: Insertion starts from the highest level and compares next node of the current node
Step 5: If Next node key is less than inserted key, then we can move forward with the same level
Step 6: If next node key is greater than inserted key, then we need to store a pointer to current node I and move one level down continuing the search.
Search Algorithm
Step 1: As the searching element is very much similar to searching a spot to insert element in Skip list.
Step 2: If next node key is less than the search key, then we can move forward on the same level
Step 3: If next node key is greater than inserted key, then we need to store a pointer to the current node I and move one level down continuing the search.
Step 4: At the lowest level, if the next element to the rightmost element has keys equal to the search key, then we have found the key else it is a failure.
Deletion Algorithm
Step 1: To delete any element, say k, first we need to locate the element in the Skip list using Search Algorithm.
Step 2: Once we have found the element using Search Algorithm, pointer rearrangement is done to remove the element from the list as we do in a Single linked list.
Step 3: We need to start from the lowest level of the skip list and rearrange elements next to I not element k.
Step 4: After element deletion, there can be a situation where levels with no elements, So we need to remove these levels by decrementing the Skip list level.
Example of Skip List in Java
Code:
import java.util.Iterator;
import java.util.Random;
import java.util.NoSuchElementException;
public class SkipListJava<K extends Comparable<K>, V> implements Iterable<K> {
private int listsize;
private double pb;
protected static final Random randomGen = new Random();
protected static final double DEFAULT_PB = 0.5;
private NodeKeyValue<K, V> head;
public SkipListJava() {
this(DEFAULT_PB);
}
public SkipListJava(double pb) {
this.head = new NodeKeyValue<K, V>(null, null, 0);
this.pb = pb;
this.listsize = 0;
}
public V get(K key) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode.getKey().compareTo(key) == 0)
return listnode.getValue();
else
return null;
}
public void add(K key, V value) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode.getKey() != null && listnode.getKey().compareTo(key) == 0) {
listnode.setValue(value);
return;
}
NodeKeyValue<K, V> newlistNode = new NodeKeyValue<K, V>(key, value, listnode.getLevel());
horizontalInsertList(listnode, newlistNode);
int curLevel = listnode.getLevel();
int headlistLevel = head.getLevel();
while (isBuildLevel()) {
if (curLevel >= headlistLevel) {
NodeKeyValue<K, V> newHeadEle = new NodeKeyValue<K, V>(null, null, headlistLevel + 1);
verticalLink(newHeadEle, head);
head = newHeadEle;
headlistLevel = head.getLevel();
}
while (listnode.getUp() == null) {
listnode = listnode.getPrevious();
}
listnode = listnode.getUp();
NodeKeyValue<K, V> tmp = new NodeKeyValue<K, V>(key, value, listnode.getLevel());
horizontalInsertList(listnode, tmp);
verticalLink(tmp, newlistNode);
newlistNode = tmp;
curLevel++;
}
listsize++;
}
public void remove(K key) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode == null || listnode.getKey().compareTo(key) != 0)
throw new NoSuchElementException("Key does not exist!");
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
NodeKeyValue<K, V> previous = null;
NodeKeyValue<K, V> next = null;
for (; listnode != null; listnode = listnode.getUp()) {
previous = listnode.getPrevious();
next = listnode.getNext();
if (previous != null)
previous.setNext(next);
if (next != null)
next.setPreviousVal(previous);
}
while (head.getNext() == null && head.getDownList() != null) {
head = head.getDownList();
head.setUp(null);
}
listsize--;
}
public boolean contains(K key) {
return get(key) != null;
}
public int listsize() {
return listsize;
}
public boolean empty() {
return listsize == 0;
}
protected NodeKeyValue<K, V> findNode(K key) {
NodeKeyValue<K, V> listnode = head;
NodeKeyValue<K, V> next = null;
NodeKeyValue<K, V> down = null;
K nodeKey = null;
while (true) {
next = listnode.getNext();
while (next != null && lessThanEqual(next.getKey(), key)) {
listnode = next;
next = listnode.getNext();
}
nodeKey = listnode.getKey();
if (nodeKey != null && nodeKey.compareTo(key) == 0)
break;
down = listnode.getDownList();
if (down != null) {
listnode = down;
} else {
break;
}
}
return listnode;
}
protected void checkKeyValid(K key) {
if (key == null)
throw new IllegalArgumentException("Key must be not null!");
}
protected boolean lessThanEqual(K a, K b) {
return a.compareTo(b) <= 0;
}
protected boolean isBuildLevel() {
return randomGen.nextDouble() < pb;
}
protected void horizontalInsertList(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {
b.setPreviousVal(a);
b.setNext(a.getNext());
if (a.getNext() != null)
a.getNext().setPreviousVal(b);
a.setNext(b);
}
protected void verticalLink(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {
a.setDown(b);
b.setUp(a);
}
@Override
public String toString() {
StringBuilder stringbuild = new StringBuilder();
NodeKeyValue<K, V> listnode = head;
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
while (listnode.getPrevious() != null)
listnode = listnode.getPrevious();
if (listnode.getNext() != null)
listnode = listnode.getNext();
while (listnode != null) {
stringbuild.append(listnode.toString()).append("\n");
listnode = listnode.getNext();
}
return stringbuild.toString();
}
@Override
public Iterator<K> iterator() {
return new SkipListIterator<K, V>(head);
}
protected static class SkipListIterator<K extends Comparable<K>, V> implements Iterator<K> {
private NodeKeyValue<K, V> listnode;
public SkipListIterator(NodeKeyValue<K, V> listnode) {
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
while (listnode.getPrevious() != null)
listnode = listnode.getPrevious();
if (listnode.getNext() != null)
listnode = listnode.getNext();
this.listnode = listnode;
}
@Override
public boolean hasNext() {
return this.listnode != null;
}
@Override
public K next() {
K result = listnode.getKey();
listnode = listnode.getNext();
return result;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
protected static class NodeKeyValue<K extends Comparable<K>, V> {
private K key;
private V value;
private int skiplevel;
private NodeKeyValue<K, V> up, down, next, previous;
public NodeKeyValue(K key, V value, int skiplevel) {
this.key = key;
this.value = value;
this.skiplevel = skiplevel;
}
@Override
public String toString() {
StringBuilder stringbuild = new StringBuilder();
stringbuild.append("Node[")
.append("key:");
if (this.key == null)
stringbuild.append("None");
else
stringbuild.append(this.key.toString());
stringbuild.append(", value:");
if (this.value == null)
stringbuild.append("None");
else
stringbuild.append(this.value.toString());
stringbuild.append("]");
return stringbuild.toString();
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public int getLevel() {
return skiplevel;
}
public void setLevel(int skiplevel) {
this.skiplevel = skiplevel;
}
public NodeKeyValue<K, V> getUp() {
return up;
}
public void setUp(NodeKeyValue<K, V> up) {
this.up = up;
}
public NodeKeyValue<K, V> getDownList() {
return down;
}
public void setDown(NodeKeyValue<K, V> down) {
this.down = down;
}
public NodeKeyValue<K, V> getNext() {
return next;
}
public void setNext(NodeKeyValue<K, V> next) {
this.next = next;
}
public NodeKeyValue<K, V> getPrevious() {
return previous;
}
public void setPreviousVal(NodeKeyValue<K, V> previous) {
this.previous = previous;
}
}
public static void main(String[] args) {
SkipListJava<Integer, String> skip = new SkipListJava<>();
for (int i = 20; i < 35; i++) {
skip.add(i, String.valueOf(i));
}
System.out.println(skip);
assert skip.listsize() == 10;
int count = 0;
for (Integer i : skip)
assert i.equals(count++);
skip.remove(23);
System.out.println(skip);
skip.remove(25);
skip.remove(33);
skip.remove(30);
System.out.println(skip);
skip.remove(28);
skip.add(25, "25");
System.out.println(skip);
assert skip.listsize() == 0;
assert skip.empty();
}
}Output:
We have written this code for adding into skip list, searching in skip list, and removing from skip list.
Conclusion
With this, we shall conclude this topic ‘Skip List Java’. We have seen what Skip list Java is and how it works with Algorithm for Search, Insert and Delete/ Remove Element from Skip list. Also, have a good example that has all of the operations of skip list at one go. You can still try on with quite other examples or logic you may get in your mind. The concept of Skip list is the same in any programming language, one of the major Algorithm in Data Structure.
Recommended Articles
This is a guide to Skip List Java. Here we discuss Introduction, syntax, and Types of Basic Skip List Operations, Algorithm, examples with code implementation. You may also have a look at the following articles to learn more –
