A 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)