Datová struktura skip list

Skip list je datová struktura dosahující s vysokou pravděpodobností logaritmické časové složitosti pro běžné operace (přidání prvku, odebrání, nalezení podle klíče). Indexovaný skip list je jeho rozšířením, které navíc umožňuje i přístup k prvkům pomocí indexů v logaritmickém čase.

Ilustrace rozvržení spojů ve skip listu

Ilustrace rozvržení spojů ve skip listu

Je zajímavou alternativou vyvážených vyhledávacích stromů pro některé druhy aplikací (lze například dobře rozšířit pro užití ve vícevláknových aplikacích), navíc se oproti nim díky své eleganci poměrně snadno naprogramuje.
Předmětem mé zápočtové práce na předmět Algoritmy a datové struktury II byla právě implementace základní verze této struktury.