Hva er en hoppliste?
En hoppliste er en sannsynlig datastruktur. Hopp over listen brukes til å lagre en sortert liste over elementer eller data med en koblet liste. Det lar prosessen med elementene eller dataene se effektivt. I ett enkelt trinn hopper den over flere elementer av hele listen, og det er derfor den er kjent som en hoppliste.
Hopp over listen er en utvidet versjon av den koblede listen. Den lar brukeren søke, fjerne og sette inn elementet veldig raskt. Den består av en basisliste som inkluderer et sett med elementer som opprettholder koblingshierarkiet til de påfølgende elementene.
Hopp over listestruktur
Den er bygget i to lag: Det nederste laget og det øverste laget.
Det laveste laget av hopplisten er en vanlig sortert lenket liste, og de øverste lagene i hopplisten er som en 'ekspresslinje' der elementene hoppes over.
Kompleksitetstabell for Hopp over listen
| Ja Nei | Kompleksitet | Gjennomsnittlig tilfelle | I verste fall |
|---|---|---|---|
| 1. | Tilgang kompleksitet | O(logn) | På) |
| 2. | Søkekompleksitet | O(logn) | På) |
| 3. | Slett kompleksitet | O(logn) | På) |
| 4. | Sett inn kompleksitet | O(logn) | På) |
| 5. | Romkompleksitet | - | O(nlogn) |
Arbeidet med hopplisten
La oss ta et eksempel for å forstå hvordan hoppelisten fungerer. I dette eksemplet har vi 14 noder, slik at disse nodene er delt inn i to lag, som vist i diagrammet.
Det nederste laget er en felles linje som kobler sammen alle noder, og det øverste laget er en ekspresslinje som bare kobler sammen hovednodene, som du kan se i diagrammet.
Anta at du vil finne 47 i dette eksemplet. Du vil starte søket fra den første noden på ekspresslinjen og fortsette å kjøre på ekspresslinjen til du finner en node som er lik 47 eller mer enn 47.
Du kan se i eksemplet at 47 ikke eksisterer i ekspresslinjen, så du søker etter en node på mindre enn 47, som er 40. Nå går du til normallinjen ved hjelp av 40, og søker på 47, som vist i diagrammet.
Merk: Når du finner en node som dette på 'ekspresslinjen', går du fra denne noden til en 'normal bane' ved hjelp av en peker, og når du søker etter noden på normallinjen.
Hopp over liste Grunnleggende operasjoner
Det er følgende typer operasjoner i hopplisten.
Algoritme for innsettingsoperasjonen
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
Algoritme for slettingsoperasjon
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
Algoritme for søkeoperasjon
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
Eksempel 1: Lag en hoppliste, vi ønsker å sette inn disse følgende tastene i den tomme hopplisten.
- 6 med nivå 1.
- 29 med nivå 1.
- 22 med nivå 4.
- 9 med nivå 3.
- 17 med nivå 1.
- 4 med nivå 2.
År:
Trinn 1: Sett inn 6 med nivå 1
Steg 2: Sett inn 29 med nivå 1
Trinn 3: Sett inn 22 med nivå 4
Trinn 4: Sett inn 9 med nivå 3
Trinn 5: Sett inn 17 med nivå 1
Trinn 6: Sett inn 4 med nivå 2
Eksempel 2: Tenk på dette eksemplet hvor vi vil søke etter nøkkel 17.
År:
Fordeler med Skip-listen
- Hvis du vil sette inn en ny node i hopplisten, vil den sette inn noden veldig raskt fordi det ikke er noen rotasjoner i hopplisten.
- Hopp over listen er enkel å implementere sammenlignet med hashtabellen og det binære søketreet.
- Det er veldig enkelt å finne en node i listen fordi den lagrer nodene i sortert form.
- Algoritmen for hoppe over listen kan endres veldig enkelt i en mer spesifikk struktur, for eksempel indekserbare hoppelister, trær eller prioriterte køer.
- Hopplisten er en robust og pålitelig liste.
Ulemper med Hopp over listen
- Det krever mer minne enn det balanserte treet.
- Omvendt søk er ikke tillatt.
- Hopplisten søker i noden mye langsommere enn den koblede listen.
Søknader fra Hopp over listen
- Den brukes i distribuerte applikasjoner, og den representerer pekerne og systemet i de distribuerte applikasjonene.
- Den brukes til å implementere en dynamisk elastisk samtidig kø med lav låsekonflikt.
- Den brukes også med malklassen QMap.
- Indekseringen av hoppelisten brukes til å kjøre medianproblemer.
- Hopp over listen brukes for delta-kodingsposteringen i Lucene-søket.