Список с пропусками (skip list)

Коротко: Список с пропусками — отсортированный связный список с дополнительными «скоростными полосами», так что элементы находятся в среднем за O(log n).

Подробнее: Нижний уровень содержит все элементы. Каждый более высокий уровень содержит, выбранные случайно, примерно половину элементов нижележащего уровня. Поиск начинается сверху, делает большие прыжки и спускается, когда прыжок оказался бы слишком большим.