Skipplista

Den här artikeln eller det här avsnittet anses vara onödigt fackspråklig. (2017-08) Hjälp gärna Wikipedia med att förtydliga texten och göra den mer lättläst. Se eventuellt diskussionssidan för mer information. Om artikeln inte åtgärdats inom tre år från dess att den märkts upp kan den komma att raderas.

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2017-08) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

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 ${\displaystyle 2^{i-1}}$ steg framåt.

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