Skiplists. Good? Yes

Okay skip lists are fun, yeah honestly. First they are so simple to understand and the insertion, deletion and search algorithms are simple to implement. Actualy, they become simpler once you understand how linked lists work.

Skip lists can be used in place of balanced trees (AVL and Red-black trees). They use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

Skip lists borrow certain similarities from a singly linked list. The only difference is that skip lists comprise express lanes on top of the linked list at the base.

The nodes in the express lanes contain sparse items in the skiplist while the base lane contains all the items in a linked list manner.

A skiplist has levels from 1 (when the list is empty i.e it only has the head node and a sentinel tail node) to n (which is the current highest active level in the list).

To search for an item in the list, traversal starts from the list’s current highest active level. Then at each level, move forward while the next node’s key is less than the target key. When traversal can nolonger proceed in the current list level, we drop down a level while staying at the same node. The same node iteration is done for the remaining levels in the list upto level 0. This algorithm provides an O(log n) expected time complexity because the traversal skips unnecessary node comparison at each level.

Suppose the express lane at level i has nodes [10, 40, 60], and we are searching for 50;

Traversal within that level will stop and 40, because the forward/next node's key (60) is greater than the target node.

Just like linked lists have next pointer whose address is the next value in the list, skip lists have a forward pointer whose address is the next element in the list at that level.

To insert an element in a list, the same search algorithm is used, with the only addition being that an update array is populated with the immediate predecessor of the target node at each level. If the target item is found, its value is updated to the new value. Otherwise we have to populate a new node to be inserted into the list at the appropriate position.

Before inserting a new node, we determine how many levels the node will occupy. We do this using a randomized level generator with a promotion probability, typically 0.5 or 0.25. The node starts at level 0 and is repeatedly promoted to the next level while the random condition succeeds, up to the skiplist’s maximum level. This produces fewer nodes at higher levels and creates the sparse “express lanes” that give the skiplist its logarithmic search performance. I won’t discuss the details about the random number generator here.

If the new level exceeds the list’s current highest active level, we have to do 2 things. First, we iterate from the list’s current level to the new level, initializing the corresponding entries in the update array to point to the list header. We then update the list’s current highest active level to the new level.

We then perform a final iteration from level 0 to the list current level. For each iteration, we update the new node’s forward pointer point to the predecessor’s forward pointer. We then update the predecessor’s forward pointer to point to the newly created node.

To put it in simple terms, I’d conclude that a basic skiplist design is essentially one ordered linked list at level 0, and higher levels are probabilistically constructed shortcuts over that list.

References

Skip Lists: A Probabilistic Alternative to Balanced Trees - William Pugh’s 1985 paper