import java.util.ArrayList;
public class SkipList {
// Node of the SkipList
public static class SkipListNode<K extends Comparable<K>, V> {
public K key;
public V value;
public ArrayList<SkipListNode<K, V>> nextNodes;
public SkipListNode(K key, V value) {
this.key = key;
this.value = value;
nextNodes = new ArrayList<SkipListNode<K, V>>();
}
}
// SkipList
public static class SkipListMap<K extends Comparable<K>, V> {
public static final double PROBABILITY = 0.5; // Probability for level generation
public SkipListNode<K, V> head;
public int maxLevel; // Maximum level in the SkipList
public int size;
public SkipListMap() {
// The head is the leftmost "platform"
this.head = new SkipListNode<>(null, null);
head.nextNodes.add(null); // Level 0
this.size = 0;
this.maxLevel = 0;
}
// Add a node to the SkipList
public void put(K key, V value) {
if (key == null) {
return;
}
// Check if the key already exists in the SkipList, update the value if so
// Method: Find the rightmost node less than the key at the bottom level
SkipListNode<K, V> less = mostRightLessNodeInTree(key);
// less.nextNodes.get(0) --
SkipListNode<K, V> find = less.nextNodes.get(0);
if (find.key.compareTo(key) == 0) {
find.value = value;
} else {
// Generate a random level for the new node
int newNodeLevel = 0;
while (Math.random() < PROBABILITY) {
newNodeLevel++;
}
// If the new level exceeds the current max level, adjust the head levels and max level
while (newNodeLevel > maxLevel) {
maxLevel++;
head.nextNodes.add(null);
}
SkipListNode<K, V> newNode = new SkipListNode<>(key, value);
for (int i = 0; i < newNodeLevel; i++) {
newNode.nextNodes.add(null);
}
int level = maxLevel;
SkipListNode<K, V> pre = head;
while (level >= 0) {
// Find the predecessor node at the current level
pre = mostRightLessNodeInLevel(pre, key, level);
// Insert the new node between the predecessor and its successor
if (level <= newNodeLevel) {
newNode.nextNodes.set(level, pre.nextNodes.get(level));
pre.nextNodes.set(level, newNode);
}
level--;
}
size++;
}
}
// Remove a node from the SkipList
public void remove(K key) {
// Check if the key exists in the SkipList
if (!containsKey(key)) {
return;
}
size--;
// Start from the top level, remove the node at each level until the bottom
int level = maxLevel;
SkipListNode<K, V> pre = head;
while (level >= 0) {
// Find the predecessor node at the current level
pre = mostRightLessNodeInLevel(pre, key, level);
// Remove the node
SkipListNode<K, V> next = pre.nextNodes.get(level);
if (next != null && next.key.compareTo(key) == 0) {
pre.nextNodes.set(level, next.nextNodes.get(level));
}
// If a level has only the head node left, remove this level
if (level != 0 && pre == head && pre.nextNodes.get(level) == null) {
head.nextNodes.remove(level);
maxLevel--;
}
level--;
}
}
// Start from the top level and traverse down to find the rightmost node less than the key at level 0
public SkipListNode<K, V> mostRightLessNodeInTree(K key) {
if (key == null) {
return null;
}
int level = maxLevel;
SkipListNode<K, V> cur = head;
while (level >= 0) {
cur = mostRightLessNodeInLevel(cur, key, level);
level--;
}
return cur;
}
// At a specific level, find the rightmost node less than the key
public SkipListNode<K, V> mostRightLessNodeInLevel(SkipListNode<K, V> cur, K key, int level) {
if (key == null) {
return null;
}
SkipListNode<K, V> pre = null;
cur = cur.nextNodes.get(level);
while (cur.key.compareTo(key) < 0) {
pre = cur;
cur = cur.nextNodes.get(level);
}
return pre;
}
// Check if the SkipList contains the given key
public Boolean containsKey(K key) {
if (key == null) {
return false;
}
SkipListNode<K, V> less = mostRightLessNodeInTree(key);
SkipListNode<K, V> find = less.nextNodes.get(0);
return find != null && find.key.compareTo(key) == 0;
}
}
}
Bring your solution into Docusign. Reach over 1.6M customers.
Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)