Skipplista

Från Wikipedia
Hoppa till: navigering, sök

En skipplista är en länkad lista där vissa element har pekare som går flera steg framåt (framåtpekare). En vanlig konfiguration är att låta antalet steg framåt vara en tvåpotens, som nedan

|------------------------------>|   |
|-------------->|-------------->|   |
|------>|------>|------>|------>|   |
|-->|-->|-->|-->|-->|-->|-->|-->|-->|
0   1   2   3   4   5   6   7   8   9

en sådan skipplista kallas för en perfekt balanserad skipplista. Notera att listan utnyttjar sina pekare optimalt om antalet element är en tvåpotens.

Noderna i listan kan kallas efter antalet framåtpekare de har. Noden med värde 2 har i detta fall 2 framåtpekare och kallas därför för en nivå-2-nod.

När man stoppar in eller tar bort noder ur listan kommer listans balans att ändras (till exempel kommer inte var fjärde nod längre att ha en framåtpekare som pekar 4 steg framåt). Det skulle såklart gå att ordna om listan för att få den perfekt balanserad men detta är inte praktiskt användbart. Istället är det vanligt att man nöjer sig med en mindre strikt balans som bygger på sannolikhet. Eftersom en perfekt balanserad skipplista innehåller 50% nivå nivå-1-noder, 25% nivå-2-noder, osv. så kan detta användas för att slumpa antalet framåtpekare i en nyinstoppad nod. I en sådan här sannolikhetsbalanserad skipplista pekar en nods i:te pekare på nästa nod som är en nivå-i-nod eller högre, dvs. inte nödvändigtvis på den nod som är 2^{i-1} steg framåt.

Listans nivå är lika med antalet pekare i header-noden. I exemplet ovan är listans nivå 4.