'''Список с пропусками''' (англ. ''skip list'') — поисковая структура данных, реализующая интерфейс упорядоченного множества, позволяет производить позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции поискадобавления, добавления удаления и удаления элемента в списке за достаточно малое времяпоиска элементов.
Поиск элемента Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в списке производится за отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть <tex>O(\log(n))-</tex>; добавление и удаление элемета происходит за то же время, что на третьем и поисктак далее, однако эти операции могут замедлить поиск в структуре. Такая производительность достигается за счёт добавления новых уровней. При но при этом нижним уровнем является исходный списокизвестно, а каждый следующий уровень что если элемент расположен на <tex>i</tex>- списоком уровне, содержащий часть элементов предыдущего уровня со ссылками то он также расположен на эти элементы<tex>(i-1)</tex>-ом, <tex>(i-2)</tex>-ом и более низких уровнях.
==Построение==
