Skip list
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.