Vad är en överhoppningslista?

En överhoppningslista är en probabilistisk datastruktur. Överhoppningslistan används för att lagra en sorterad lista med element eller data med en länkad lista. Det gör att processen för elementen eller data kan ses effektivt. I ett enda steg hoppar den över flera delar av hela listan, vilket är anledningen till att den är känd som en överhoppningslista.

Överhoppningslistan är en utökad version av den länkade listan. Det låter användaren söka, ta bort och infoga elementet mycket snabbt. Den består av en baslista som innehåller en uppsättning element som upprätthåller länkhierarkin för de efterföljande elementen.

Hoppa över liststruktur

Den är byggd i två lager: det lägsta lagret och det övre lagret.

Det lägsta lagret i överhoppningslistan är en vanlig sorterad länkad lista, och de översta lagren i överhoppningslistan är som en 'expresslinje' där elementen hoppas över.

Komplexitetstabell för Hoppa över listan

Arbete med Skip-listan

Låt oss ta ett exempel för att förstå hur överhoppningslistan fungerar. I det här exemplet har vi 14 noder, så att dessa noder är uppdelade i två lager, som visas i diagrammet.

Det undre lagret är en gemensam linje som länkar alla noder, och det översta lagret är en expresslinje som länkar endast huvudnoderna, som du kan se i diagrammet.

Anta att du vill hitta 47 i det här exemplet. Du kommer att starta sökningen från den första noden på expresslinjen och fortsätta köra på expresslinjen tills du hittar en nod som är lika med 47 eller mer än 47.

Du kan se i exemplet att 47 inte finns i expresslinjen, så du söker efter en nod som är mindre än 47, vilket är 40. Nu går du till den normala raden med hjälp av 40 och söker på 47, som visas i diagrammet.

Notera: När du väl hittar en nod som denna på 'expresslinjen', går du från denna nod till en 'normal körfält' med hjälp av en pekare, och när du söker efter noden på den normala linjen.

Hoppa över lista Grundläggande funktioner

Det finns följande typer av operationer i överhoppningslistan.

Insättningsoperation:Den används för att lägga till en ny nod till en viss plats i en specifik situation.Raderingsåtgärd:Den används för att ta bort en nod i en specifik situation.Sökoperation:Sökoperationen används för att söka efter en viss nod i en överhoppningslista.

Algoritm för insättningsoperationen

 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 

Algoritm för raderingsoperation

 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 

Algoritm för sökoperation

 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 

Exempel 1: Skapa en överhoppningslista, vi vill infoga dessa följande nycklar i den tomma överhoppningslistan.

1. 6 med nivå 1.
2. 29 med nivå 1.
3. 22 med nivå 4.
4. 9 med nivå 3.
5. 17 med nivå 1.
6. 4 med nivå 2.

År:

Steg 1: Sätt 6 med nivå 1

Steg 2: Sätt 29 med nivå 1

Steg 3: Insats 22 med nivå 4

Steg 4: Sätt i 9 med nivå 3

Steg 5: Insats 17 med nivå 1

Steg 6: Sätt 4 med nivå 2

Exempel 2: Betrakta det här exemplet där vi vill söka efter nyckel 17.

År:

Fördelar med Skip-listan

1. Om du vill infoga en ny nod i överhoppningslistan, kommer den att infoga noden mycket snabbt eftersom det inte finns några rotationer i överhoppningslistan.
2. Överhoppningslistan är enkel att implementera jämfört med hashtabellen och det binära sökträdet.
3. Det är väldigt enkelt att hitta en nod i listan eftersom den lagrar noderna i sorterad form.
4. Överhoppningslistans algoritm kan modifieras mycket enkelt i en mer specifik struktur, såsom indexerbara överhoppningslistor, träd eller prioritetsköer.
5. Överhoppningslistan är en robust och pålitlig lista.

Nackdelar med Skip-listan

1. Det kräver mer minne än det balanserade trädet.
2. Omvänd sökning är inte tillåten.
3. Överhoppningslistan söker noden mycket långsammare än den länkade listan.

Tillämpningar av Hoppa över listan

1. Det används i distribuerade applikationer, och det representerar pekarna och systemet i de distribuerade applikationerna.
2. Den används för att implementera en dynamisk elastisk samtidig kö med låg låskonflikt.
3. Den används också med mallklassen QMap.
4. Indexeringen av överhoppningslistan används för att köra medianproblem.
5. Överhoppningslistan används för delta-kodningsposteringen i Lucene-sökningen.