Skip lists are a fascinating data structure: very simple, and yet have the same asymptotic efficiency as much more complicated AVL trees and red-black trees.
Java Implementation
http://en.literateprograms.org/Skip_list_(Java)#chunk use:SkipSet.java
http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html
Instead of ensuring that the level-2 list skips every other node, a skip list is designed in a way that the level-2 list skips one node on average. In some places, it may skip two nodes, and in other places, it may not skip any nodes. But overall, the structure of a skip list is very similar to the structure of a sorted multi-level list.
It allows simple O(log N) insertions and deletions.
Java Implementation
http://en.literateprograms.org/Skip_list_(Java)#chunk use:SkipSet.java
http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html
skip list can be directly used to implement some operations that are not efficient on a typical sorted set:
- Find the element in the set that is closest to some given value, in O(log N) time.
- Find the k-th largest element in the set, in O(log N) time. Requires a simple augmentation of the the skip list with partial counts.
- Count the number of elements in the set whose values fall into a given range, in O(log N) time. Also requires a simple augmentation of the skip list.
Instead of ensuring that the level-2 list skips every other node, a skip list is designed in a way that the level-2 list skips one node on average. In some places, it may skip two nodes, and in other places, it may not skip any nodes. But overall, the structure of a skip list is very similar to the structure of a sorted multi-level list.
It allows simple O(log N) insertions and deletions.
- Insertion: decide how many lists will this node be a part of. With a probability of 1/2, make the node a part of the lowest-level list only. With 1/4 probability, the node will be a part of the lowest two lists. With 1/8 probability, the node will be a part of three lists. And so forth. Insert the node at the appropriate position in the lists that it is a part of.
public void Insert(int value) { // Determine the level of the new node. Generate a random number R. The number of // 1-bits before we encounter the first 0-bit is the level of the node. Since R is // 32-bit, the level can be at most 32. int level = 0; for (int R = _rand.Next(); (R & 1) == 1; R >>= 1) { level++; if (level == _levels) { _levels++; break; } } // Insert this node into the skip list Node newNode = new Node(value, level + 1); Node cur = _head; for (int i = _levels - 1; i >= 0; i--) { for (; cur.Next[i] != null; cur = cur.Next[i]) { if (cur.Next[i].Value > value) break; } if (i <= level) { newNode.Next[i] = cur.Next[i]; cur.Next[i] = newNode; } } }
- Deletion: remove the node from all sorted lists that it is a part of.
public bool Remove(int value) { Node cur = _head; bool found = false; for (int i = _levels - 1; i >= 0; i--) { for (; cur.Next[i] != null; cur = cur.Next[i]) { if (cur.Next[i].Value == value) { found = true; cur.Next[i] = cur.Next[i].Next[i]; break; } if (cur.Next[i].Value > value) break; } } return found; }
Read full article from Skip lists are fascinating!public bool Contains(int value) { Node cur = _head; for (int i = _levels - 1; i >= 0; i--) { for (; cur.Next[i] != null; cur = cur.Next[i]) { if (cur.Next[i].Value > value) break; if (cur.Next[i].Value == value) return true; } } return false; }