==Операции над структурой==
===Поиск элемента===
Допустим, что в нашем списке с пропусками существуют <tex>k</tex> уровней, при этом первым уровнем (<tex>L_1</tex>) будет исходный список.
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
# Начинаем поиск элемента в верхнем списке (<tex>L_k</tex>), рассмотрим первый элемент
# Переходить к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу
# Переместиться на один уровень вниз и перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне <tex>- </tex> выйти из поиска
Пример поиска числа <tex>8</tex> в списке из описания:
[[Файл:SkipListSearch.png]]
В Если в качестве примера рассмотрим список с двумя уровнями случайного источника использовать честную монету, то тогда если в списке будет <tex>L_1n</tex> и <tex>L_2</tex>. Поскольку элементы по уровням распределяются равномерноэлементов, то количество уровней в среднем количество элементов между двумя соседними элементами уровня <tex>L_2</tex> будет составлять равно <tex>\dfraclog{n}{\vert L_2 \vert}</tex>. Оценим среднее время доступа к элементу. Мы пройдём Тогда на последнем уровне будет не более <tex>\vert L_2 \vert</tex> двух элементов , а на каждом следующем будет почти в два раза больше. Тогда на втором каждом уровне, однако, мы проверим не более двух элементов (если бы на каком-нибудь шаге мы спустимся на нижней уровеньуровне проверили три элемента, то пройдём в среднем не более <tex>\dfrac{n}{\vert L_2 \vert}</tex> элементов (в противном случае это значило, что мы могли бы пройти ещё на верхнем уровне на один элемент на втором уровнебольше). Минимизируем величину Уровней всего <tex>\vert L_2 \vert + \dfraclog{n}{\vert L_2 \vert}</tex>. Очевидно, что при <tex> \vert L_2 \vert = \sqrt{n}</tex> сумма достигает минимального значения. Таким образом, время откуда вытекает оценка времени поиска элемента составляет в среднем <tex>O(\sqrt{n})</tex>, отсюда выходит, что удаление и добавления элемента также происходит за <tex>O(\sqrt{n})</tex>, а для того, чтобы эффективнее использовать такой список, нам нужно генератор равновероятных чисел с вероятностью <tex>\dfrac{1}{\sqrt{n}}</tex>. Допустим, что у нас имеется не два, а <tex>k</tex> уровней. Тогда оптимально на каждом из <tex>k</tex> уровней проходить не более <tex>\sqrt[k]{n}</tex> элементов, отсюда выходить оценка для поиска, добавления и удаления элементов равная <tex>O(\sqrt[k]log{n})</tex>.
===Вставка элемента===
