Skip list

In computer science, a skip list (or skiplist) is a probabilistic data structure that allows ... average complexity for insertion within an ordered sequence of ... 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.