ایک skip list ایک ترتیب شدہ linked list ہے جو متعدد "express lane" levels سے بہتر بنائی گئی ہے۔ اعلیٰ levels بہت سے nodes کو skip کرتے ہیں، اس لیے search descend اور دائیں جانب move کرتے ہوئے O(log n) متوقع وقت حاصل کرتا ہے — یہ balanced tree کا ایک احتمالی، سادہ متبادل ہے۔
ڈھانچہ
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)
