Mi az a kihagyási lista?

A kihagyási lista egy valószínűségi adatstruktúra. A kihagyási lista elemek vagy adatok rendezett listájának tárolására szolgál egy csatolt listával. Lehetővé teszi az elemek vagy adatok folyamatának hatékony megtekintését. Egyetlen lépésben átugorja a teljes lista több elemét, ezért nevezik átugrási listának.

A kihagyási lista a hivatkozott lista kiterjesztett változata. Lehetővé teszi a felhasználó számára az elem nagyon gyors keresését, eltávolítását és beillesztését. Ez egy alaplistából áll, amely elemkészletet tartalmaz, amely fenntartja a következő elemek hivatkozási hierarchiáját.

Kihagyás lista szerkezete

Két rétegből áll: a legalsó és a felső rétegből.

Az átugrási lista legalsó rétege egy általánosan rendezett linkelt lista, az átugrási lista felső rétegei pedig olyanok, mint egy „kifejezett sor”, ahol az elemek kihagyásra kerülnek.

A kihagyási lista összetettségi táblázata

A Skip lista működése

Vegyünk egy példát a kihagyási lista működésének megértéséhez. Ebben a példában 14 csomópont van, így ezek a csomópontok két rétegre vannak osztva, amint az az ábrán látható.

Az alsó réteg egy közös vonal, amely az összes csomópontot összekapcsolja, a felső réteg pedig egy expressz vonal, amely csak a fő csomópontokat kapcsolja össze, amint az az ábrán látható.

Tegyük fel, hogy ebben a példában a 47-et szeretné megtalálni. A keresést az expressz sor első csomópontjától kezdi, és addig fut az expressz vonalon, amíg meg nem talál egy 47-es vagy 47-nél nagyobb csomópontot.

A példában láthatja, hogy a 47 nem létezik az expressz sorban, tehát egy 47-nél kisebb csomópontot keres, ami 40. Most a 40 segítségével a normál sorba lép, és a 47-ben keres, ábrán látható módon.

Megjegyzés: Ha talál egy ilyen csomópontot az 'express line'-on, akkor ettől a csomóponttól egy 'normál sávba' lép egy mutató segítségével, és amikor a csomópontot a normál vonalban keresi.

Alapműveletek kihagyása

A következő típusú műveletek szerepelnek a kihagyási listában.

Beillesztési művelet:Új csomópont hozzáadására szolgál egy adott helyen egy adott helyzetben.Törlési művelet:Egy adott helyzetben egy csomópont törlésére szolgál.Keresési művelet:A keresési művelet egy adott csomópont keresésére szolgál egy kihagyási listában.

A beillesztési művelet algoritmusa

 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 

A törlési művelet algoritmusa

 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 

A keresési művelet algoritmusa

 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. példa: Hozzon létre egy kihagyási listát, a következő kulcsokat szeretnénk beszúrni az üres kihagyási listába.

1. 6 1-es szinttel.
2. 29 1. szinttel.
3. 22 4-es szinttel.
4. 9 3. szinttel.
5. 17 1. szinttel.
6. 4 2-es szinttel.

Évek:

1. lépés: Helyezze be a 6-ost az 1-es szinttel

2. lépés: Helyezze be a 29-et az 1-es szinttel

3. lépés: Helyezze be a 22-t a 4-es szinttel

4. lépés: Helyezze be a 9-et a 3-as szinttel

5. lépés: Szúrjon be 17-et az 1-es szinttel

6. lépés: Helyezze be a 4-et a 2-es szinttel

2. példa: Tekintsük ezt a példát, ahol a 17-es kulcsra szeretnénk keresni.

Évek:

A kihagyási lista előnyei

1. Ha új csomópontot szeretne beszúrni a kihagyási listába, akkor nagyon gyorsan beilleszti a csomópontot, mivel a kihagyási listában nincsenek elforgatások.
2. A kihagyási lista a hash táblához és a bináris keresőfához képest egyszerűen megvalósítható.
3. Nagyon egyszerű egy csomópontot megtalálni a listában, mert az a csomópontokat rendezett formában tárolja.
4. A kihagyási lista algoritmusa nagyon egyszerűen módosítható egy specifikusabb struktúrában, például indexelhető kihagyási listákban, fákban vagy prioritási sorokban.
5. A kihagyási lista egy robusztus és megbízható lista.

A Skip lista hátrányai

1. Több memóriát igényel, mint a kiegyensúlyozott fa.
2. A fordított keresés nem megengedett.
3. A kihagyási lista sokkal lassabban keresi a csomópontot, mint a hivatkozott lista.

A Skip lista alkalmazásai

1. Elosztott alkalmazásokban használatos, és az elosztott alkalmazásokban található mutatókat és rendszert képviseli.
2. Dinamikus, rugalmas egyidejű sor megvalósítására szolgál alacsony zárolási versengés mellett.
3. A QMap sablonosztállyal is használatos.
4. A kihagyási lista indexelését a medián problémák futtatásához használják.
5. A kihagyási lista a delta-kódolású feladáshoz használatos a Lucene keresésben.