| SkipList | Skip list is a data structure that allows O(log n) search complexity as well as
O(log n) insertion complexity within an ordered sequence of n elements.
Thus it can get the best of array while maintaining a linked list-like structure
that allows insertion- which is not possible in an array. Fast search is made
possible by maintaining a linked hierarchy of subsequences, with each successive
subsequence skipping over fewer elements than the previous one. Searching starts
in the sparsest subsequence until two consecutive elements have been found,
one smaller and one larger than or equal to the element searched for.
|