Skip list — это упорядоченный связный список, дополненный несколькими уровнями "express lane". Верхние уровни пропускают множество узлов, поэтому поиск спускается и движется вправо, достигая O(log n) ожидаемого времени — как вероятностная, более простая альтернатива сбалансированному дереву.
Структура
text
L3: head ------------------------> 30 -------> NIL
L2: head ----------> 17 ---------> 30 -------> NIL
L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL
L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list)
