390
правок
Изменения
→Построение
==Построение==
[[Файл:SimpleList.png|thumb|600px|Односвязный отсортированный список]]
[[Файл:SkipList.png|thumb|600px|Получившийся список с пропусками]]
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.
На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне <tex>-</tex> всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элемента, номера которых кратны четырём. Аналогично построим и последующие уровни.
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которое есть начало <tex>head</tex> и конец <tex>tail</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.
