Какво е списък за пропускане?

Списъкът за пропускане е вероятностна структура от данни. Списъкът за прескачане се използва за съхраняване на сортиран списък от елементи или данни със свързан списък. Той позволява процесът на елементите или данните да се разглежда ефективно. В една единствена стъпка той пропуска няколко елемента от целия списък, поради което е известен като списък за пропускане.

Списъкът за пропускане е разширена версия на свързания списък. Тя позволява на потребителя да търси, премахва и вмъква елемента много бързо. Състои се от основен списък, който включва набор от елементи, който поддържа йерархията на връзките на следващите елементи.

Структура на списъка за пропускане

Той е изграден на два слоя: най-долния слой и горния слой.

Най-долният слой на списъка за пропускане е общ сортиран свързан списък, а горните слоеве на списъка за пропускане са като „експресна линия“, където елементите се пропускат.

Таблица на сложността на списъка за пропускане

Работа на списъка за пропускане

Нека вземем пример, за да разберем работата на списъка за пропускане. В този пример имаме 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. Списъкът за пропускане е стабилен и надежден списък.

Недостатъци на Skip list

1. Изисква повече памет от балансираното дърво.
2. Обратното търсене не е разрешено.
3. Списъкът за прескачане търси възела много по-бавно от свързания списък.

Приложения на списъка за пропускане

1. Използва се в разпределени приложения и представлява указателите и системата в разпределените приложения.
2. Използва се за прилагане на динамична еластична едновременна опашка с ниско съревнование за заключване.
3. Използва се и с класа на шаблона QMap.
4. Индексирането на списъка за пропускане се използва при изпълнение на средни проблеми.
5. Списъкът за пропускане се използва за публикуване на делта кодиране в търсенето на Lucene.