Mikä on ohituslista?
Ohituslista on todennäköisyyspohjainen tietorakenne. Ohituslistaa käytetään lajiteltujen elementtien tai tietojen luettelon tallentamiseen linkitetyllä luettelolla. Sen avulla elementtien tai tietojen prosessia voidaan tarkastella tehokkaasti. Yhdessä vaiheessa se ohittaa useita elementtejä koko luettelosta, minkä vuoksi se tunnetaan ohituslistana.
Ohituslista on linkitetyn luettelon laajennettu versio. Sen avulla käyttäjä voi etsiä, poistaa ja lisätä elementin erittäin nopeasti. Se koostuu perusluettelosta, joka sisältää joukon elementtejä, jotka ylläpitävät seuraavien elementtien linkkihierarkiaa.
Ohita listan rakenne
Se on rakennettu kahteen kerrokseen: alin kerros ja yläkerros.
Ohitusluettelon alin kerros on yleinen lajiteltu linkitetty luettelo, ja ohituslistan ylimmät kerrokset ovat kuin 'pikaviiva', jossa elementit ohitetaan.
Ohitusluettelon monimutkaisuustaulukko
| Kyllä ei | Monimutkaisuus | Keskimääräinen tapaus | Pahimmassa tapauksessa |
|---|---|---|---|
| 1. | Käyttöoikeuden monimutkaisuus | O (kirjaudu sisään) | Päällä) |
| 2. | Haun monimutkaisuus | O(kirjaudu sisään) | Päällä) |
| 3. | Poista monimutkaisuus | O (kirjaudu sisään) | Päällä) |
| 4. | Lisää monimutkaisuus | O (kirjaudu sisään) | Päällä) |
| 5. | Avaruuden monimutkaisuus | - | O (ei kirjaudu sisään) |
Ohituslistan käyttö
Otetaan esimerkki, jotta ymmärrämme ohituslistan toiminnan. Tässä esimerkissä meillä on 14 solmua, joten nämä solmut on jaettu kahteen kerrokseen, kuten kaaviossa näkyy.
Alempi kerros on yhteinen viiva, joka yhdistää kaikki solmut, ja yläkerros on pikaviiva, joka yhdistää vain pääsolmut, kuten näet kaaviosta.
Oletetaan, että haluat löytää 47 tästä esimerkistä. Aloitat haun pikarivin ensimmäisestä solmusta ja jatkat sen suorittamista pikarivillä, kunnes löydät solmun, joka on yhtä suuri kuin 47 tai suurempi kuin 47.
Näet esimerkissä, että numeroa 47 ei ole pikarivillä, joten haet solmua, jonka arvo on pienempi kuin 47, mikä on 40. Nyt siirryt normaalille riville 40:n avulla ja etsit 47, kuten kaaviossa näkyy.
Huomautus: Kun löydät tällaisen solmun 'pikalinjalta', siirryt tästä solmusta 'normaalille kaistalle' käyttämällä osoitinta ja kun etsit solmua normaalilta riviltä.
Ohita luettelon perustoiminnot
Ohitusluettelossa on seuraavan tyyppisiä toimintoja.
Lisäystoiminnon algoritmi
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
Poistotoiminnon algoritmi
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
Hakuoperaation algoritmi
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
Esimerkki 1: Luo ohituslista, haluamme lisätä nämä seuraavat avaimet tyhjään ohituslistaan.
- 6 tasolla 1.
- 29 tasolla 1.
- 22 tasolla 4.
- 9 tasolla 3.
- 17 tasolla 1.
- 4 tasolla 2.
Vuodet:
Vaihe 1: Aseta 6 tasolle 1
Vaihe 2: Aseta 29 tasolle 1
Vaihe 3: Lisää 22 tasolle 4
Vaihe 4: Aseta 9 tasolle 3
Vaihe 5: Aseta 17 tasolle 1
Vaihe 6: Aseta 4 tasolle 2
Esimerkki 2: Harkitse tätä esimerkkiä, jossa haluamme etsiä avainta 17.
Vuodet:
Ohitusluettelon edut
- Jos haluat lisätä uuden solmun ohituslistaan, se lisää solmun erittäin nopeasti, koska ohituslistassa ei ole kiertoja.
- Ohituslista on helppo toteuttaa verrattuna hash-taulukkoon ja binäärihakupuuhun.
- Solmun löytäminen luettelosta on erittäin helppoa, koska se tallentaa solmut lajiteltuina.
- Ohituslista-algoritmia voidaan muokata erittäin helposti tarkemmassa rakenteessa, kuten indeksoitavissa ohituslistoissa, puissa tai prioriteettijonoissa.
- Ohituslista on vankka ja luotettava lista.
Ohitusluettelon haitat
- Se vaatii enemmän muistia kuin tasapainoinen puu.
- Käänteinen haku ei ole sallittu.
- Ohituslista etsii solmua paljon hitaammin kuin linkitetty luettelo.
Ohitusluettelon sovellukset
- Sitä käytetään hajautetuissa sovelluksissa, ja se edustaa osoittimia ja järjestelmää hajautetuissa sovelluksissa.
- Sitä käytetään dynaamisen elastisen samanaikaisen jonon toteuttamiseen alhaisella lukkokilpailulla.
- Sitä käytetään myös QMap-malliluokan kanssa.
- Ohitusluettelon indeksointia käytetään suoritettaessa mediaaniongelmia.
- Ohituslistaa käytetään delta-koodaukseen Lucene-haussa.