Što je lista za preskakanje?

Popis za preskakanje vjerojatnosna je struktura podataka. Popis za preskakanje koristi se za pohranu sortiranog popisa elemenata ili podataka s povezanim popisom. Omogućuje učinkovito pregledavanje procesa elemenata ili podataka. U jednom koraku preskače nekoliko elemenata cijelog popisa, zbog čega je poznat kao popis za preskakanje.

Popis za preskakanje je proširena verzija povezanog popisa. Omogućuje korisniku vrlo brzo pretraživanje, uklanjanje i umetanje elementa. Sastoji se od osnovnog popisa koji uključuje skup elemenata koji održavaju hijerarhiju veza sljedećih elemenata.

Struktura popisa za preskakanje

Izgrađen je u dva sloja: najniži sloj i gornji sloj.

Najniži sloj popisa za preskakanje je uobičajeni sortirani povezani popis, a gornji slojevi popisa za preskakanje su poput 'brze linije' gdje se elementi preskaču.

Tablica složenosti Skip liste

Rad Skip liste

Uzmimo primjer da bismo razumjeli rad popisa za preskakanje. U ovom primjeru imamo 14 čvorova, tako da su ti čvorovi podijeljeni u dva sloja, kao što je prikazano na dijagramu.

Donji sloj je zajednička linija koja povezuje sve čvorove, a gornji sloj je ekspresna linija koja povezuje samo glavne čvorove, kao što možete vidjeti na dijagramu.

Pretpostavimo da želite pronaći 47 u ovom primjeru. Pretraživanje ćete započeti od prvog čvora ekspresne linije i nastaviti trčati na ekspresnoj liniji dok ne pronađete čvor koji je jednak 47 ili više od 47.

Možete vidjeti u primjeru da 47 ne postoji u ekspresnoj liniji, pa tražite čvor manji od 47, što je 40. Sada idete na normalnu liniju uz pomoć 40 i tražite 47, kako je prikazano na dijagramu.

Napomena: Kada pronađete čvor kao što je ovaj na 'brzoj liniji', prelazite s ovog čvora na 'normalnu traku' pomoću pokazivača, a kada tražite čvor na normalnoj liniji.

Skip List Basic Operations

Na popisu za preskakanje postoje sljedeće vrste operacija.

Operacija umetanja:Koristi se za dodavanje novog čvora na određeno mjesto u specifičnoj situaciji.Operacija brisanja:Koristi se za brisanje čvora u određenoj situaciji.Operacija pretraživanja:Operacija pretraživanja koristi se za pretraživanje određenog čvora na popisu za preskakanje.

Algoritam operacije umetanja

 Insertion (L, Key) local update [0...Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] lvl = random_Level() if lvl > L → level then for i = L → level + 1 to lvl do update[i] = L → header L → level = lvl a = makeNode(lvl, Key, value) for i = 0 to level do a → forward[i] = update[i] → forward[i] update[i] → forward[i] = a 

Algoritam operacije brisanja

 Deletion (L, Key) local update [0... Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] if a → key = Key then for i = 0 to L → level do if update[i] → forward[i] ? a then break update[i] → forward[i] = a → forward[i] free(a) while L → level > 0 and L → header → forward[L → level] = NIL do L → level = L → level - 1 

Algoritam operacije pretraživanja

 Searching (L, SKey) a = L → header loop invariant: a → key level down to 0 do. while a → forward[i] → key forward[i] a = a → forward[0] if a → key = SKey then return a → value else return failure 

Primjer 1: Napravite popis za preskakanje, želimo umetnuti sljedeće ključeve u prazan popis za preskakanje.

1. 6 s razinom 1.
2. 29 s razinom 1.
3. 22 s razinom 4.
4. 9 s razinom 3.
5. 17 s razinom 1.
6. 4 s razinom 2.

Godine:

Korak 1: Umetnite 6 s razinom 1

Korak 2: Umetnite 29 s razinom 1

Korak 3: Umetnite 22 s razinom 4

Korak 4: Umetnite 9 s razinom 3

Korak 5: Umetnite 17 s razinom 1

Korak 6: Umetnite 4 s razinom 2

Primjer 2: Razmotrite ovaj primjer gdje želimo tražiti ključ 17.

Godine:

Prednosti Skip liste

1. Ako želite umetnuti novi čvor u popis za preskakanje, tada će čvor umetnuti vrlo brzo jer nema rotacija u popisu za preskakanje.
2. Popis za preskakanje je jednostavan za implementaciju u usporedbi s hash tablicom i stablom binarnog pretraživanja.
3. Vrlo je jednostavno pronaći čvor na popisu jer čvorove pohranjuje u sortiranom obliku.
4. Algoritam popisa preskakanja može se vrlo lako modificirati u specifičnijoj strukturi, kao što su popisi preskakanja koji se mogu indeksirati, stabla ili redovi prioriteta.
5. Popis za preskakanje robustan je i pouzdan popis.

Nedostaci Skip liste

1. Zahtijeva više memorije od uravnoteženog stabla.
2. Obrnuto pretraživanje nije dopušteno.
3. Popis za preskakanje pretražuje čvor puno sporije od povezanog popisa.

Primjene Skip liste

1. Koristi se u distribuiranim aplikacijama, a predstavlja pokazivače i sustav u distribuiranim aplikacijama.
2. Koristi se za implementaciju dinamičkog elastičnog istovremenog reda čekanja s malim sukobom zaključavanja.
3. Također se koristi s klasom predloška QMap.
4. Indeksiranje popisa za preskakanje koristi se u pokretanju srednjih problema.
5. Popis za preskakanje koristi se za objavljivanje delta kodiranja u Lucene pretraživanju.