Skip list

Common card · No. 234206

In computer science, a skip list (or skiplist) is a probabilistic data structure that allows O ( log ⁡ n ) {\displaystyle {\mathcal {O}}(\log n)} average complexity for search as well as O ( log ⁡ n ) {\displaystyle {\mathcal {O}}(\log n)} average complexity for insertion within an ordered sequence of n {\displaystyle n} elements. Thus it can get the best features of a sorted array (for searching) while maintaining a linked list-like structure that allows insertion, which is not possible with a static 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 (see the picture below...

Read on Wikipedia