O skip list este o listă legată ordonată îmbogățită cu mai multe niveluri "express lane". Nivelurile superioare sar peste mulți noduri, deci căutarea coboară și se mișcă la dreapta, realizând O(log n) timp așteptat — ca o alternativă probabilistică mai simplă la un copac echilibrat.
Structură
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)
