Data Structure - Skip List

Subscribe Send me a message home page tags


#data structure  #skip list 

Related Readings

Notes

Skip list is a probabilistic data structure that is built on top of a standard linked list. It introduces multiple levels. Each level is a linked list on its own. The bottom level is the standard linked list, which contains all elements. Each time we go one level above, the number of elements stored in that level is reduced by half. This essentially transforms the data structure into a tree.

ideal_skip_list.png

Where does the probabilistic aspect come into play? The problem is that it's expensive to maintain an ideally balanced skip list where level N+1 has exactly half elements of level N. The solution to this problem is to promote a node to a higher level probabilistically. Suppose the bottom level is level 0, then the probability of promoting a node to level \(k\) is \( \frac{1}{2^k} \)

The number of levels is \(O(log \;n)\), therefore, the search time and the time complexity of other operations is \(O(log \; n)\) too. The statement is intuitively correct but requires a proof. A simple proof can be found in Skip Lists - CMSC 420. The idea is to consider the reverse of the path that finds the target element.

Another note is that the nodes are sorted and the multi-level linked list is much like a binary search tree.

----- END -----

Welcome to join reddit self-learning community.
Send me a message Subscribe to blog updates

Want some fun stuff?

/static/shopping_demo.png