Шта је листа за прескакање?

Листа за прескакање је вероватноћа структура података. Листа за прескакање се користи за чување сортиране листе елемената или података са повезаном листом. Омогућава ефикасан преглед процеса елемената или података. У једном кораку прескаче неколико елемената целе листе, због чега је позната као листа за прескакање.

Листа за прескакање је проширена верзија повезане листе. Омогућава кориснику да врло брзо претражи, уклони и убаци елемент. Састоји се од основне листе која укључује скуп елемената који одржава хијерархију веза наредних елемената.

Структура листе за прескакање

Изграђен је у два слоја: најнижи слој и горњи слој.

Најнижи слој листе за прескакање је уобичајена сортирана повезана листа, а горњи слојеви листе за прескакање су попут 'експресне линије' где се елементи прескачу.

Табела сложености листе за прескакање

Рад на Скип листи

Узмимо пример да разумемо рад листе за прескакање. У овом примеру имамо 14 чворова, тако да су ови чворови подељени у два слоја, као што је приказано на дијаграму.

Доњи слој је заједничка линија која повезује све чворове, а горњи слој је експресна линија која повезује само главне чворове, као што можете видети на дијаграму.

Претпоставимо да желите да пронађете 47 у овом примеру. Почећете претрагу од првог чвора експресне линије и наставити да трчите на експресној линији док не пронађете чвор који је једнак 47 или већи од 47.

У примеру можете видети да 47 не постоји у експресној линији, па тражите чвор мањи од 47, што је 40. Сада идете на нормалну линију уз помоћ 40 и тражите 47, као што је приказано на дијаграму.

Напомена: Једном када пронађете овакав чвор на 'експресној линији', прелазите са овог чвора на 'нормалну траку' користећи показивач, а када тражите чвор у нормалној линији.

Прескочи листу основних операција

На листи за прескакање постоје следеће врсте операција.

Операција уметања:Користи се за додавање новог чвора на одређену локацију у одређеној ситуацији.Операција брисања:Користи се за брисање чвора у одређеној ситуацији.Операција претраге:Операција претраге се користи за претрагу одређеног чвора на листи за прескакање.

Алгоритам операције уметања

 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 

Алгоритам операције брисања

 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 

Алгоритам операције претраживања

 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 

Пример 1: Направите листу за прескакање, желимо да убацимо ове следеће кључеве у празну листу за прескакање.

1. 6 са нивоом 1.
2. 29 са нивоом 1.
3. 22 са нивоом 4.
4. 9 са нивоом 3.
5. 17 са нивоом 1.
6. 4 са нивоом 2.

године:

Корак 1: Убаците 6 са нивоом 1

Корак 2: Убаците 29 са нивоом 1

Корак 3: Убаците 22 са нивоом 4

4. корак: Убаците 9 са нивоом 3

5. корак: Убаците 17 са нивоом 1

Корак 6: Убаците 4 са нивоом 2

Пример 2: Размотримо овај пример где желимо да тражимо кључ 17.

године:

Предности листе за прескакање

1. Ако желите да убаците нови чвор у листу за прескакање, онда ће он уметнути чвор веома брзо јер нема ротације у листи за прескакање.
2. Листа за прескакање је једноставна за имплементацију у поређењу са хеш табелом и бинарним стаблом претраге.
3. Веома је једноставно пронаћи чвор на листи јер чува чворове у сортираном облику.
4. Алгоритам листе за прескакање може се врло лако модификовати у специфичнијој структури, као што су листе за прескакање које се могу индексирати, стабла или приоритетни редови.
5. Листа за прескакање је робусна и поуздана листа.

Недостаци листе за прескакање

1. Захтева више меморије него балансирано дрво.
2. Обрнуто претраживање није дозвољено.
3. Листа за прескакање претражује чвор много спорије од повезане листе.

Апликације листе за прескакање

1. Користи се у дистрибуираним апликацијама и представља показиваче и систем у дистрибуираним апликацијама.
2. Користи се за имплементацију динамичког еластичног истовременог реда са малим сукобом закључавања.
3. Такође се користи са класом КМап шаблона.
4. Индексирање листе за прескакање се користи у покретању медијана проблема.
5. Листа за прескакање се користи за објављивање делта кодирања у Луцене претрази.