एक skip list एक क्रमबद्ध लिंक्ड लिस्ट हो जसलाई बहु "express lane" स्तरहरूसँग बढाइएको छ। उच्च स्तरहरूले धेरै नोडहरू छोड्छन्, त्यसैले खोज ओरलो र दायाँतिर सर्छ, O(log n) अपेक्षित समय हासिल गर्छ — सन्तुलित रूखको सम्भाव्यात, सरल विकल्प जस्तै।
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)
प्रत्येक नोडलाई उच्च स्तरहरूमा सम्भावना p को साथ बढाइन्छ (प्राय: 0.5), त्यसैले औसतमा प्रत्येक स्तरमा तलको आधा नोडहरू हुन्छन्।
search(25): start top-left, move RIGHT while next <= target,
else drop DOWN a level. Repeat to level 0.
import random
def random_level(p=0.5, max_level=16):
lvl = 1
while random.random() < p and lvl < max_level:
lvl += 1 # coin flips decide a node's height
return lvl
| अपरेशन | अपेक्षित | स्पेस |
|---|---|---|
| खोज | O(log n) | O(n) |
| प्रविष्ट / हटाउनुहोस् | O(log n) | — |
ConcurrentSkipListMap मा प्रयोग गरिन्छ)।स्किप लिस्टहरूले रूख जस्तो O(log n) क्रमबद्ध अपरेशनहरू धेरै कम कोड र सजिलै lock-free समवर्तिताको साथ प्रदान गर्छन्, त्यसैले Redis जस्तो वास्तविक प्रणालीहरू तिनलाई छनौट गर्छन्।
तिनीहरू randomization प्रयोग गरेर जटिल नियतात्मक सन्तुलन तर्क को बदली गर्ने उत्कृष्ट उदाहरण हुन्।