Co je to seznam přeskočení?

Přeskočit seznam je pravděpodobnostní datová struktura. Seznam přeskočení se používá k uložení seřazeného seznamu prvků nebo dat s propojeným seznamem. Umožňuje efektivně zobrazit proces prvků nebo dat. V jednom jediném kroku přeskočí několik prvků celého seznamu, proto se nazývá seznam přeskočení.

Seznam přeskočení je rozšířenou verzí propojeného seznamu. Umožňuje uživateli velmi rychle vyhledávat, odebírat a vkládat prvek. Skládá se ze základního seznamu, který obsahuje sadu prvků, která udržuje hierarchii odkazů následujících prvků.

Přeskočit strukturu seznamu

Je postaven ve dvou vrstvách: nejnižší vrstva a vrchní vrstva.

Nejnižší vrstva seznamu přeskočení je běžný seřazený propojený seznam a horní vrstvy seznamu přeskočení jsou jako „výrazná čára“, kde jsou prvky přeskočeny.

Tabulka složitosti seznamu Přeskočit

Práce se seznamem přeskočení

Vezměme si příklad, abychom pochopili fungování seznamu přeskočení. V tomto příkladu máme 14 uzlů, takže tyto uzly jsou rozděleny do dvou vrstev, jak je znázorněno na obrázku.

Spodní vrstva je společná čára, která spojuje všechny uzly, a horní vrstva je expresní čára, která spojuje pouze hlavní uzly, jak můžete vidět na diagramu.

Předpokládejme, že v tomto příkladu chcete najít 47. Začnete hledat od prvního uzlu expresní linky a budete pokračovat v běhu na expresní lince, dokud nenajdete uzel, který je roven 47 nebo více než 47.

V příkladu můžete vidět, že 47 v expresní lince neexistuje, takže hledáte uzel menší než 47, což je 40. Nyní přejdete na normální řádek s pomocí 40 a prohledáte 47, jak je znázorněno na diagramu.

Poznámka: Jakmile najdete uzel jako je tento na 'expresní lince', přejdete z tohoto uzlu do 'normálního pruhu' pomocí ukazatele a když budete hledat uzel na normální lince.

Základní operace přeskočit seznam

V seznamu přeskočení jsou následující typy operací.

Operace vkládání:Používá se k přidání nového uzlu na určité místo v konkrétní situaci.Operace odstranění:Používá se k odstranění uzlu v konkrétní situaci.Vyhledávací operace:Operace vyhledávání se používá k vyhledávání konkrétního uzlu v seznamu přeskočení.

Algoritmus operace vkládání

 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 

Algoritmus operace mazání

 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 

Algoritmus vyhledávací operace

 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 

Příklad 1: Vytvořte seznam přeskočení, tyto následující klíče chceme vložit do prázdného seznamu přeskočení.

1. 6 s úrovní 1.
2. 29 s úrovní 1.
3. 22 s úrovní 4.
4. 9 s úrovní 3.
5. 17 s úrovní 1.
6. 4 s úrovní 2.

roky:

Krok 1: Vložte 6 s úrovní 1

Krok 2: Vložte 29 s úrovní 1

Krok 3: Vložte 22 s úrovní 4

Krok 4: Vložte 9 s úrovní 3

Krok 5: Vložte 17 s úrovní 1

Krok 6: Vložte 4 s úrovní 2

Příklad 2: Zvažte tento příklad, kde chceme hledat klíč 17.

roky:

Výhody seznamu přeskočení

1. Pokud chcete do seznamu přeskočení vložit nový uzel, vloží uzel velmi rychle, protože v seznamu přeskočení nejsou žádné rotace.
2. Implementace přeskočeného seznamu je ve srovnání s hashovací tabulkou a binárním vyhledávacím stromem jednoduchá.
3. Je velmi snadné najít uzel v seznamu, protože ukládá uzly v setříděné podobě.
4. Algoritmus seznamu přeskakování lze velmi snadno upravit ve specifičtější struktuře, jako jsou indexovatelné seznamy přeskakování, stromy nebo prioritní fronty.
5. Seznam přeskočení je robustní a spolehlivý seznam.

Nevýhody seznamu přeskočení

1. Vyžaduje více paměti než vyvážený strom.
2. Zpětné vyhledávání není povoleno.
3. Seznam přeskočení prohledává uzel mnohem pomaleji než propojený seznam.

Aplikace seznamu Přeskočit

1. Používá se v distribuovaných aplikacích a představuje ukazatele a systém v distribuovaných aplikacích.
2. Používá se k implementaci dynamické elastické souběžné fronty s nízkým soupeřením zámků.
3. Používá se také s třídou šablony QMap.
4. Indexování seznamu přeskočení se používá při problémech se spouštěním mediánu.
5. Seznam přeskočení se používá pro odesílání pomocí delta-kódování ve vyhledávání v Lucene.