Suchaufwand
Suchen in perfekten Skip-Listen ist O(log n).
Problem: Einfügen und Löschen führt zu erheblichem Mehraufwand, wenn Skip-Listen perfekt bleiben sollen.
Deshalb: randomisierte SLs: Man sorgt dafür, daß die Anzahl der vorkommenden Höhen stimmt (d.h. Hälfte Niveau 1 Zeiger, Viertel Niveau 2 Zeiger etc.).
Neues Element erhält Höhe i mit Wahrscheinlichkeit 1 / 2i+1,
Beim Einfügen (und Entfernen) müssen Zeiger entsprechend der zufälligen Höhe des Elements umgesetzt werden.