Lista z przeskokami () – probabilistyczna struktura danych przeznaczona do przechowywania danych uporządkowanych (np. posortowanych rosnąco liczb), będąca rozwinięciem listy jednokierunkowej, a stanowiąca alternatywę dla drzew zbalansowanych (wyważonych), takich jak drzewa AVL czy czerwono-czarne.
Została opracowana przez Williama Pugha w 1989 roku. Oczekiwana złożoność operacji wyszukiwania, wstawiania nowego elementu do listy oraz usunięcia elementu wynosi
Implementacja W zwykłej liście każdy element posiada połączenie (ze względu na prostotę implementacji najczęściej realizowane poprzez wskaźnik) wyłącznie do elementu następnego. W liście z przeskokami takich połączeń jest więcej: oprócz bezpośredniego następnika, wskazują także elementy znajdujące się dalej. Liczba połączeń powiązana z elementem określa jego stopień (ang. degree, lub wysokość [height]), przy czym -te połączenie wskazuje na kolejny element stopnia co najmniej Stopnie węzłów są wybierane losowo, ale z rozkładem geometrycznym (prawdopodobieństwa dane wzorem gdzie ); np. dla liczba elementów stopnia 1 powinna stanowić 50% całości, stopnia 2 – 25%, stopnia 3 – 12% itd.
Dzięki temu rozwiązaniu można szybciej przechodzić całą listę, a ponadto dzięki informacji o jej uporządkowaniu pomijać („przeskakiwać”) nieistotne fragmenty listy.
frame|center|Przykładowa lista z węzłami o maksymalnym stopniu 4Wyszukiwanie elementu polega na przeszukiwaniu listy od najwyższego stopnia, aż napotkany element ma wartość wyższą lub równą. Wtedy stopień wyszukiwań na obecnym węźle zmniejsza się o 1 i kontynuowane jest sprawdzanie kolejnych elementów wzdłuż wskaźników z niższego poziomu. Gdy nie można już zredukować stopnia, to następny element będzie tym który jest wyszukiwany albo nie znajduje się on na liście.
Dla uproszczenia poniższych pseudokodów zakłada się, że węzły NIL mają klucz uosabiającym nieskończoności (). Search(list, searchKey) x := list→header for i := list→level downto 1 do while x→forward[i]→key < searchKey do x := x→forward[i] x := x→forward if x→key = searchKey then return x→value else return failure Oczekiwana liczba operacji na każdym poziomie wynosi . Wówczas oczekiwana złożoność operacji wyszukiwania to , co daje Poprzez wybór wartości parametru można zmniejszać ilość operacji kosztem pamięci.
Wstawienie i usuwanie elementu polega na użyciu powyższego algorytmu wyszukiwania, aby określić miejsce, w którym powinien znajdować się nowy/usuwany element, wylosowaniu stopnia (przy wstawianiu) oraz odpowiednim przestawieniu wskaźników. Do odpowiedniego ustawienia wskaźników wykorzystuje się zmienną pomocniczą (np. update), która zawiera wskaźniki do ostatnich mniejszych elementów na i-tym poziomie od nowego/usuwanego elementu. Jeśli nowy węzeł jest stopnia wyższego niż lista, to aktualizujemy jej maksymalny stopień. Po usunięciu elementu sprawdzane jest czy nie usunięto elementu o najwyższym stopniu, wówczas zmniejsza się stopień całej listy. Insert(list, searchKey, newValue) local update[1..MaxLevel] x := list→header for i := list→level downto 1 do while x→forward[i]→key < searchKey do x := x→forward[i] update[i] := x x := x→forward if x→key = searchKey then x→value := newValue else newLevel := randomLevel() if newLevel > list→level then for i := list→level + 1 to newLevel do update[i] := list→header list→level := newLevel x := makeNode(newLevel , searchKey, newValue) for i := 1 to newLevel do x→forward[i] := update[i]→forward[i] update[i]→forward[i] := x
Delete(list, searchKey) local update[1..MaxLevel] x := list→header for i := list→level downto 1 do while x→forward[i]→key < searchKey do x := x→forward[i] update[i] := x x := x→forward if x→key = searchKey then for i := 1 to list→level do if update[i]→forward[i] ≠ x then break update[i]→forward[i] := x→forward[i] free(x) while list→level > 1 and list→header→forward[list→level] = NIL do list→level := list→level – 1
Zobacz też lista struktura danych
Literatura dodatkowa William Pugh, A Skip List Cookbook, 1989. William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM 33, 1990.
Kategoria:Struktury danych