import java.util.Random;
public class SkipList {
// My question is how the skip list make the whole structure balanced? Maybe it create index levels randomly, with
// good chance the index keys are chosen randomly and equal distributed.
public static void main(String[] args) {
new SkipList().test();
}
public void test() {
MySkipList<Integer, Integer> list = new MySkipList<>();
for (int i = 0; i < 10000; i++) {
list.put(i, new Random().nextInt(10000));
}
list.remove(100);
System.out.println(list.get(2).value);
System.out.println("Height: " + list.height + ", Size: " + list.size());
}
class MySkipList<K extends Comparable<K>, V> {
// With smaller INDEX_EXPANDING_PROBABILITY, it is easy to create more inner index nodes, and there are
// INDEX_EXPANDING_PROBABILITY^height probability that SkipList will generate a new level. The larger the
// INDEX_EXPANDING_PROBABILITY is, the deeper the hierarchy is.
private static final double INDEX_EXPANDING_PROBABILITY = 0.15;
private SkipListNode<K, V> head;
private SkipListNode<K, V> tail;
private int size;
private int height;
private Random random;
public MySkipList() {
head = new SkipListNode(SkipListNode.HEAD_KEY, null);
tail = new SkipListNode(SkipListNode.TAIL_KEY, null);
head.next = tail;
tail.prev = head;
size = 0;
height = 0;
random = new Random();
}
public void put(K key, V value) {
// find the proper position for insertion
SkipListNode<K, V> pos = findInsertionPoint(key);
// update it if exists
if (pos.key.equals(key)) {
pos.value = value;
return;
}
// otherwise pos.key is smaller than the give key, but the most closest one.
SkipListNode<K, V> newNode = new SkipListNode<>(key, value);
// append newNode after pos first, then consider add level
append(pos, newNode);
// Do not forget to update the counter of list size.
size++;
int currentLevel = 0;
while (random.nextDouble() < INDEX_EXPANDING_PROBABILITY) {
// generate an empty level on the top of the current level only if current level is the top level.
if (currentLevel >= height) {
generateLevel();
}
// is it possible following loop is a forever loop?
// impossible! only pos on the top level will result in pos.up == null.
// but if it is on the highest level, above adding empty level
// logic will be triggered. So it will never happen.
while (pos.up == null) {
pos = pos.prev;
}
pos = pos.up;
// idxNode serves as the index node with pos's key, but with empty value.
// All the non-bottom lists work like the lookup table.
SkipListNode<K, V> idxNode = new SkipListNode(key, null);
append(pos, idxNode);
newNode.up = idxNode;
idxNode.down = newNode;
newNode = idxNode;
// initially, the node is inserted on the bottom level, then move upwards.
currentLevel++;
}
}
private void append(SkipListNode<K, V> p, SkipListNode<K, V> q) {
// append q after p
// p<->a; q
// q->a
q.next = p.next;
// p<-q
q.prev = p;
// q<->a
q.next.prev = q;
// p<->q
p.next = q;
// p<->q<->a
}
public SkipListNode<K, V> get(K key) {
// if there is node binding with given key, below function will return it.
SkipListNode<K, V> p = findInsertionPoint(key);
if (p.key.equals(key)) {
return p;
}
return null;
}
private SkipListNode<K, V> findInsertionPoint(K key) {
// find out the position at which node binding with the given the key can insert. but
// if the key is equal with the node at insertion position, it will return the node
// binding with the given key. if not equal, it will return the node of closest key
// which is <= given key.
// if there are already node
SkipListNode<K, V> p = head;
while (true) {
// if the node p.next.key >= key, do not move forward, leave it to the next level.
// otherwise move forward to next node for much closer key.
if (p.next != null && p.next.key.compareTo(key) <= 0) {
p = p.next;
continue;
}
// the lower level is more precise and with more specific ranges.
// for example, top level MIN<->MAX; sub top level MIN<->20<->40<->MAX
// p.down != null indicates current level is not the bottom level, dig down/descend to next level.
if (p.down != null) {
p = p.down;
continue;
}
// reach the bottom level and find the proper slot for insertion, then break the loop
// It can always find a proper insertion slot because even key is very large, it will can't be more
// greater than Integer.MAX_VALUE which is the tail of the list.
if (p.next != null && p.next.key.compareTo(key) > 0) {
break;
}
}
return p;
}
public V remove(K key) {
SkipListNode<K, V> p = get(key);
if (p == null) {
return null;
}
V value = p.value;
while (p != null) {
// a<->p<->b
// a<-b
p.next.prev = p.prev;
// a<->b
p.prev.next = p.next;
// remove upper index nodes which contains p.val
p = p.up;
}
size--;
return value;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void generateLevel() {
SkipListNode<K, V> p1 = new SkipListNode(SkipListNode.HEAD_KEY, null);
SkipListNode<K, V> p2 = new SkipListNode(SkipListNode.TAIL_KEY, null);
p1.next = p2;
p2.prev = p1;
p1.down = head;
head.up = p1;
p2.down = tail;
tail.up = p2;
// head.up and tail.up are always null
// head and tail are promoted to the highest level finally.
head = p1;
tail = p2;
height++;
}
}
class SkipListNode<K extends Comparable<K>, V> {
public static final int HEAD_KEY = Integer.MIN_VALUE;
public static final int TAIL_KEY = Integer.MAX_VALUE;
public K key;
public V value;
public SkipListNode<K, V> prev, next, up, down;
public SkipListNode(K key, V value) {
this.key = key;
this.value = value;
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || !(o instanceof SkipListNode)) {
return false;
}
SkipListNode<K, V> ent;
try {
ent = (SkipListNode<K, V>) o;
} catch (ClassCastException ex) {
return false;
}
return (ent.key.equals(key)) && (ent.value == value);
}
@Override
public String toString() {
return "key-value:" + key + "," + value;
}
}
}