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
| Igen nem | Bonyolultság | Átlagos eset | Legrosszabb esetben |
|---|---|---|---|
| 1. | A hozzáférés bonyolultsága | O(bejelentkezés) | Tovább) |
| 2. | Keresés bonyolultsága | O(bejelentkezés) | Tovább) |
| 3. | Törölje a komplexitást | O(bejelentkezés) | Tovább) |
| 4. | Bonyolultság beszúrása | O(bejelentkezés) | Tovább) |
| 5. | A tér összetettsége | - | O(nlogn) |
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.
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.
- 6 1-es szinttel.
- 29 1. szinttel.
- 22 4-es szinttel.
- 9 3. szinttel.
- 17 1. szinttel.
- 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
- 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.
- A kihagyási lista a hash táblához és a bináris keresőfához képest egyszerűen megvalósítható.
- Nagyon egyszerű egy csomópontot megtalálni a listában, mert az a csomópontokat rendezett formában tárolja.
- 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.
- A kihagyási lista egy robusztus és megbízható lista.
A Skip lista hátrányai
- Több memóriát igényel, mint a kiegyensúlyozott fa.
- A fordított keresés nem megengedett.
- A kihagyási lista sokkal lassabban keresi a csomópontot, mint a hivatkozott lista.
A Skip lista alkalmazásai
- Elosztott alkalmazásokban használatos, és az elosztott alkalmazásokban található mutatókat és rendszert képviseli.
- Dinamikus, rugalmas egyidejű sor megvalósítására szolgál alacsony zárolási versengés mellett.
- A QMap sablonosztállyal is használatos.
- A kihagyási lista indexelését a medián problémák futtatásához használják.
- A kihagyási lista a delta-kódolású feladáshoz használatos a Lucene keresésben.