123: Skip Lists (Intro)
July 25, 2017
Posted by on
A skip list is a data structure similar to a linked list which stores an ordered sequence of elements and is built specifically for fast search within the sequence. The way it’s commonly implemented is as a hierarchy of linked lists, with the first list containing all the elements of the skip list, and each successive linked list containing a sparser subset of the elements in the previous one.
To search for an element within the skip list one then starts with the sparsest linked list, getting as ‘close’ to the desired element as possible, then moves directly down to that same position in the next linked list and continues searching until the item is found (or not).
This animation depicts the insertion of the element 80 into a skip list of positive integers (insertion being equivalent to searching):
Credit: Artyom Kalinin
In the average case, the skip list uses space and takes just time for searching operations.