Què és una llista de salts?

Una llista de salt és una estructura de dades probabilística. La llista de salt s'utilitza per emmagatzemar una llista ordenada d'elements o dades amb una llista enllaçada. Permet que el procés dels elements o dades es visualitzi de manera eficient. En un sol pas, omet diversos elements de tota la llista, per això es coneix com a llista de salts.

La llista de salts és una versió ampliada de la llista enllaçada. Permet a l'usuari cercar, eliminar i inserir l'element molt ràpidament. Consisteix en una llista base que inclou un conjunt d'elements que manté la jerarquia d'enllaços dels elements posteriors.

Estructura de la llista de salts

Està construït en dues capes: la capa més baixa i la capa superior.

La capa més baixa de la llista d'omissió és una llista enllaçada ordenada comú, i les capes superiors de la llista d'omissió són com una 'línia ràpida' on els elements es salten.

Taula de complexitat de la llista de salts

Funcionament de la llista de salts

Prenguem un exemple per entendre el funcionament de la llista de salts. En aquest exemple, tenim 14 nodes, de manera que aquests nodes es divideixen en dues capes, tal com es mostra al diagrama.

La capa inferior és una línia comuna que enllaça tots els nodes, i la capa superior és una línia ràpida que enllaça només els nodes principals, com podeu veure al diagrama.

Suposem que voleu trobar 47 en aquest exemple. Començareu la cerca des del primer node de la línia ràpida i seguireu corrent per la línia ràpida fins que trobeu un node igual a 47 o més que 47.

Podeu veure a l'exemple que 47 no existeix a la línia exprés, de manera que cerqueu un node inferior a 47, que és 40. Ara aneu a la línia normal amb l'ajuda de 40 i cerqueu el 47, tal com es mostra al diagrama.

Nota: un cop trobeu un node com aquest a la 'línia ràpida', aneu des d'aquest node a un 'carril normal' mitjançant un punter, i quan cerqueu el node a la línia normal.

Llista de salts operacions bàsiques

Hi ha els següents tipus d'operacions a la llista de salts.

Operació d'inserció:S'utilitza per afegir un nou node a una ubicació concreta en una situació específica.Operació d'eliminació:S'utilitza per eliminar un node en una situació específica.Operació de cerca:L'operació de cerca s'utilitza per cercar un node concret en una llista de salts.

Algorisme de l'operació d'inserció

 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 de l'operació d'eliminació

 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 

Algorisme de l'operació de cerca

 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 

Exemple 1: Creeu una llista de salts, volem inserir aquestes claus següents a la llista de salts buida.

1. 6 amb nivell 1.
2. 29 amb nivell 1.
3. 22 amb nivell 4.
4. 9 amb nivell 3.
5. 17 amb nivell 1.
6. 4 amb nivell 2.

Anys:

Pas 1: Insereix 6 amb el nivell 1

Pas 2: Insereix 29 amb el nivell 1

Pas 3: Insereix 22 amb el nivell 4

Pas 4: Insereix 9 amb el nivell 3

Pas 5: Insereix 17 amb el nivell 1

Pas 6: Insereix 4 amb el nivell 2

Exemple 2: Considereu aquest exemple on volem cercar la clau 17.

Anys:

Avantatges de la llista Skip

1. Si voleu inserir un nou node a la llista d'omissió, llavors inserirà el node molt ràpidament perquè no hi ha rotacions a la llista d'omissió.
2. La llista de salts és senzill d'implementar en comparació amb la taula hash i l'arbre de cerca binari.
3. És molt senzill trobar un node a la llista perquè emmagatzema els nodes en forma ordenada.
4. L'algorisme de la llista de salts es pot modificar molt fàcilment en una estructura més específica, com ara llistes de salts indexables, arbres o cues de prioritat.
5. La llista de salts és una llista robusta i fiable.

Inconvenients de la llista de salts

1. Requereix més memòria que l'arbre equilibrat.
2. No es permet la cerca inversa.
3. La llista de salts cerca el node molt més lentament que la llista enllaçada.

Aplicacions de la llista de salts

1. S'utilitza en aplicacions distribuïdes i representa els punters i el sistema a les aplicacions distribuïdes.
2. S'utilitza per implementar una cua concurrent elàstica dinàmica amb una contenció de bloqueig baixa.
3. També s'utilitza amb la classe de plantilla QMap.
4. La indexació de la llista de salt s'utilitza per executar problemes de mitjana.
5. La llista de salt s'utilitza per a la publicació de codificació delta a la cerca Lucene.