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

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

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