Cos'è una lista da saltare?

Una skip list è una struttura dati probabilistica. La skip list viene utilizzata per memorizzare un elenco ordinato di elementi o dati con un elenco collegato. Consente di visualizzare in modo efficiente il processo degli elementi o dei dati. In un unico passaggio vengono saltati diversi elementi dell'intero elenco, motivo per cui è noto come skip list.

L'elenco da saltare è una versione estesa dell'elenco collegato. Consente all'utente di cercare, rimuovere e inserire l'elemento molto rapidamente. Consiste in un elenco di base che include un insieme di elementi che mantiene la gerarchia di collegamento degli elementi successivi.

Struttura dell'elenco di salto

È costruito in due strati: lo strato più basso e lo strato superiore.

Il livello più basso della skip list è un comune elenco collegato ordinato, mentre i livelli superiori della skip list sono come una 'linea espressa' in cui gli elementi vengono saltati.

Tabella di complessità dell'elenco Skip

Funzionamento della Skip list

Facciamo un esempio per comprendere il funzionamento della skip list. In questo esempio, abbiamo 14 nodi, in modo tale che questi nodi siano divisi in due strati, come mostrato nel diagramma.

Lo strato inferiore è una linea comune che collega tutti i nodi, mentre lo strato superiore è una linea espressa che collega solo i nodi principali, come puoi vedere nel diagramma.

Supponiamo di voler trovare 47 in questo esempio. Inizierai la ricerca dal primo nodo della linea espressa e continuerai a correre sulla linea espressa fino a trovare un nodo uguale a 47 o superiore a 47.

Puoi vedere nell'esempio che 47 non esiste nella linea espressa, quindi cerchi un nodo inferiore a 47, che è 40. Ora vai alla linea normale con l'aiuto di 40 e cerca 47, come mostrato nel diagramma.

Nota: una volta trovato un nodo come questo sulla 'linea espressa', vai da questo nodo a una 'corsia normale' utilizzando un puntatore e quando cerchi il nodo nella linea normale.

Salta elenco Operazioni di base

Nell'elenco da saltare sono presenti i seguenti tipi di operazioni.

Operazione di inserimento:Viene utilizzato per aggiungere un nuovo nodo a una posizione particolare in una situazione specifica.Operazione di cancellazione:Viene utilizzato per eliminare un nodo in una situazione specifica.Operazione di ricerca:L'operazione di ricerca viene utilizzata per cercare un particolare nodo in una skip list.

Algoritmo dell'operazione di inserimento

 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 

Algoritmo dell'operazione di cancellazione

 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 

Algoritmo dell'operazione di ricerca

 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 

Esempio 1: Crea una skip list, vogliamo inserire le seguenti chiavi nella skip list vuota.

1. 6 con livello 1.
2. 29 con livello 1.
3. 22 con livello 4.
4. 9 con livello 3.
5. 17 con livello 1.
6. 4 con livello 2.

Anni:

Passo 1: Inserire 6 con livello 1

Passo 2: Inserire 29 con livello 1

Passaggio 3: Inserire 22 con livello 4

Passaggio 4: Inserire 9 con livello 3

Passaggio 5: Inserire 17 con livello 1

Passaggio 6: Inserire 4 con livello 2

Esempio 2: Considera questo esempio in cui vogliamo cercare la chiave 17.

Anni:

Vantaggi della Skiplist

1. Se desideri inserire un nuovo nodo nella skip list, il nodo verrà inserito molto velocemente perché non ci sono rotazioni nella skip list.
2. La skip list è semplice da implementare rispetto alla tabella hash e all'albero di ricerca binaria.
3. È molto semplice trovare un nodo nell'elenco perché memorizza i nodi in forma ordinata.
4. L'algoritmo della skip list può essere modificato molto facilmente in una struttura più specifica, come liste di skip indicizzabili, alberi o code di priorità.
5. L'elenco da saltare è un elenco robusto e affidabile.

Svantaggi della Skip list

1. Richiede più memoria dell'albero in equilibrio.
2. Non è consentita la ricerca inversa.
3. L'elenco da saltare ricerca il nodo molto più lentamente dell'elenco collegato.

Applicazioni della Skip list

1. Viene utilizzato nelle applicazioni distribuite e rappresenta i puntatori e il sistema nelle applicazioni distribuite.
2. Viene utilizzato per implementare una coda simultanea elastica dinamica con basso conflitto di blocchi.
3. Viene utilizzato anche con la classe template QMap.
4. L'indicizzazione della skip list viene utilizzata nell'esecuzione di problemi mediani.
5. L'elenco da saltare viene utilizzato per la pubblicazione della codifica delta nella ricerca Lucene.