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