Список с пропусками (Skip List) – структура данных, состоящая из нескольких связных списков (их принято называть слоями).
Основной список (его называют нижним слоем) – это обычный отсортированный связный список. Каждый элемент предыдущего слоя с некоторой фиксированной вероятностью присутствует в следующем слое. Таким образом, количество элементов уменьшается от слоя к слою и для перебора элементов следующего слоя требуется меньше времени по сравнению с предыдущим слоем.
Данная структура позволяет существенно ускорить поиск элемента в списке. Вместо последовательного перебора элементов основного списка (нижнего слоя) используется следующий алгоритм.
Поиск начинается с верхнего слоя.
Элементы слоя перебираются до тех пор, пока не будет найден элемент больший или равный целевому.
Если элемент списка равен целевому, поиск оканчивается (успех).
В противном случае осуществляется возврат к предыдущему элементу и переход к списку более низкого уровня, затем процедура повторяется.
Если текущий уровень – нижний, поиск оканчивается (неудача).
Списки с пропусками реализованы на многих современных языках программирования (Java, C++, C#, Python и т.д.).
Источники: