Skip list to posortowana linked list rozszerzona o wiele "express lane" poziomów. Wyższe poziomy omijają wiele węzłów, więc wyszukiwanie schorza i przesuwa się w prawo, osiągając O(log n) oczekiwany czas — jak probabilistyczne, prostsze alternatyw dla drzewa zrównoważonego.
Struktura
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)
