En skip list er en ordnet lenket liste utvidet med flere "express lane" nivåer. Høyere nivåer hopper over mange noder, så søk stiger og beveger seg til høyre, og oppnår O(log n) forventet tid — som et sannsynlighetsbasert, enklere alternativ til et balansert tre.
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)
Hver node fremmes til høyere nivåer med sannsynlighet p (ofte 0.5), så i gjennomsnitt har hvert nivå halvparten så mange noder som det under.
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
| Operasjon | Forventet | Plass |
|---|---|---|
| søk | O(log n) | O(n) |
| sett inn / slett | O(log n) | — |
ConcurrentSkipListMap).Skip lists leverer tre-lignende O(log n) ordnede operasjoner med langt mindre kode og enkel lock-free samtidighet, noe som er grunnen til at systemer som Redis velger dem.
De er et flott eksempel på bruk av randomization til å erstatte kompleks deterministisk balanseringslogikk.
Et bibliotek av IT-intervjuspørsmål med detaljerte svar — fra Junior til Senior.
Doner