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.
ADVERTISEMENT
Popular Course in this category
JAVA MASTERY - Specialization | 78 Course Series | 15 Mock Tests
Start Your Free Software Development Course
Web development, programming languages, Software testing & others
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, V> implements Iterable { private int listsize; private double pb; protected static final Random randomGen = new Random(); protected static final double DEFAULT_PB = 0.5; private NodeKeyValue head; public SkipListJava() { this(DEFAULT_PB); } public SkipListJava(double pb) { this.head = new NodeKeyValue(null, null, 0); this.pb = pb; this.listsize = 0; } public V get(K key) { checkKeyValid(key); NodeKeyValue 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 listnode = findNode(key); if (listnode.getKey() != null && listnode.getKey().compareTo(key) == 0) { listnode.setValue(value); return; } NodeKeyValue newlistNode = new NodeKeyValue(key, value, listnode.getLevel()); horizontalInsertList(listnode, newlistNode); int curLevel = listnode.getLevel(); int headlistLevel = head.getLevel(); while (isBuildLevel()) { if (curLevel >= headlistLevel) { NodeKeyValue newHeadEle = new NodeKeyValue(null, null, headlistLevel + 1); verticalLink(newHeadEle, head); head = newHeadEle; headlistLevel = head.getLevel(); } while (listnode.getUp() == null) { listnode = listnode.getPrevious(); } listnode = listnode.getUp(); NodeKeyValue tmp = new NodeKeyValue(key, value, listnode.getLevel()); horizontalInsertList(listnode, tmp); verticalLink(tmp, newlistNode); newlistNode = tmp; curLevel++; } listsize++; } public void remove(K key) { checkKeyValid(key); NodeKeyValue 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 previous = null; NodeKeyValue 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 findNode(K key) { NodeKeyValue listnode = head; NodeKeyValue next = null; NodeKeyValue 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 a, NodeKeyValue b) { b.setPreviousVal(a); b.setNext(a.getNext()); if (a.getNext() != null) a.getNext().setPreviousVal(b); a.setNext(b); } protected void verticalLink(NodeKeyValue a, NodeKeyValue b) { a.setDown(b); b.setUp(a); } @Override public String toString() { StringBuilder stringbuild = new StringBuilder(); NodeKeyValue 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 iterator() { return new SkipListIterator(head); } protected static class SkipListIterator, V> implements Iterator { private NodeKeyValue listnode; public SkipListIterator(NodeKeyValue 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, V> { private K key; private V value; private int skiplevel; private NodeKeyValue 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 getUp() { return up; } public void setUp(NodeKeyValue up) { this.up = up; } public NodeKeyValue getDownList() { return down; } public void setDown(NodeKeyValue down) { this.down = down; } public NodeKeyValue getNext() { return next; } public void setNext(NodeKeyValue next) { this.next = next; } public NodeKeyValue getPrevious() { return previous; } public void setPreviousVal(NodeKeyValue previous) { this.previous = previous; } } public static void main(String[] args) { SkipListJava 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.
以上是Skip List Java的詳細內容。更多資訊請關注PHP中文網其他相關文章！
