Изменения

Используя монетку с распределением отличным от <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex>, можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл») математическое ожидание количества элементов на уровне <tex>k</tex> равно <tex dpi=150>n q\cdot p^k</tex>, на каждом следующем уровне будет в среднем в <tex>q</tex> раз больше элементов. Таким образом, время поиска будет равно <tex>O\left(\dfrac{k}{q} + nq^k\right)</tex>. Соответственно при честной монетке и <tex>\log(n)</tex> уровней получаем оценку, полученную ранее.

insert(skip_list.head, key, data)

 Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ.* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)* Базы данныхПроще реализовать, чем сбалансированные деревья или хеш-таблицы* Распределённые вычисления и p2pСледующий элемент достаётся за <tex>O(1)</tex>* Масштабируемые параллельные приоритетные очереди и словариЛегко модифицировать под различные задачиВ вычислительной геометрии широко применяются структуры на основе списка с пропусками.

Структуры на основе списка с пропусками:*[[Skip quadtree: определение, время работы|Skip quadtree]]*[http://en.wikipedia.org/wiki/Skip_graph Википедия — Skip graph(En)]— структура данных, основанная на списке с пропусками

*[http://habrahabr.ru/post/111913/ Хабрахабр — Списки с пропусками]*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D1%81_%D0%BF%D1%80%D0%BE%D0%BF%D1%83%D1%81%D0%BA%D0%B0%D0%BC%D0%B8 Википедия — списки с пропусками(Ru)]*[http://en.wikipedia.org/wiki/Skip_list Википедия Wikipedia — списки с пропусками(En)]*[http://bit.ly/LiNe8M Курс kiev-clrs — Списки с пропускамиskip list]