O que é uma lista de pulos?

Uma lista de pulos é uma estrutura de dados probabilística. A lista de pulos é usada para armazenar uma lista ordenada de elementos ou dados com uma lista vinculada. Ele permite que o processo dos elementos ou dados seja visualizado de forma eficiente. Em uma única etapa, ele pula vários elementos de toda a lista, por isso é conhecido como skip list.

A lista de pulos é uma versão estendida da lista vinculada. Permite ao usuário pesquisar, remover e inserir o elemento muito rapidamente. Consiste em uma lista base que inclui um conjunto de elementos que mantém a hierarquia de links dos elementos subsequentes.

Estrutura da lista de pulos

É construído em duas camadas: a camada mais baixa e a camada superior.

A camada mais baixa da lista de ignorados é uma lista vinculada classificada comum, e as camadas superiores da lista de ignorados são como uma 'linha expressa' onde os elementos são ignorados.

Tabela de complexidade da lista Skip

Funcionamento da lista de saltos

Vamos dar um exemplo para entender o funcionamento da skip list. Neste exemplo, temos 14 nós, de forma que esses nós estão divididos em duas camadas, conforme mostrado no diagrama.

A camada inferior é uma linha comum que liga todos os nós, e a camada superior é uma linha expressa que liga apenas os nós principais, como você pode ver no diagrama.

Suponha que você queira encontrar 47 neste exemplo. Você iniciará a pesquisa a partir do primeiro nó da linha expressa e continuará executando na linha expressa até encontrar um nó que seja igual a 47 ou superior a 47.

Você pode ver no exemplo que 47 não existe na linha expressa, então você busca um nó menor que 47, que é 40. Agora você vai para a linha normal com a ajuda de 40, e busca o 47, conforme mostrado no diagrama.

Nota: Depois de encontrar um nó como este na 'linha expressa', você vai desse nó para uma 'pista normal' usando um ponteiro e quando procura o nó na linha normal.

Ignorar operações básicas da lista

Existem os seguintes tipos de operações na lista de ignorados.

Operação de inserção:É usado para adicionar um novo nó a um local específico em uma situação específica.Operação de exclusão:É usado para excluir um nó em uma situação específica.Operação de pesquisa:A operação de pesquisa é usada para pesquisar um nó específico em uma lista de pulos.

Algoritmo da operação de inserção

 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 de operação de exclusão

 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 de operação de busca

 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 

Exemplo 1: Crie uma lista de pulos, queremos inserir as seguintes chaves na lista de pulos vazia.

1. 6 com nível 1.
2. 29 com nível 1.
3. 22 com nível 4.
4. 9 com nível 3.
5. 17 com nível 1.
6. 4 com nível 2.

Anos:

Passo 1: Inserir 6 com nível 1

Passo 2: Inserir 29 com nível 1

Etapa 3: Insira 22 com nível 4

Passo 4: Inserir 9 com nível 3

Etapa 5: Insira 17 com nível 1

Etapa 6: Inserir 4 com nível 2

Exemplo 2: Considere este exemplo onde queremos procurar a chave 17.

Anos:

Vantagens da lista de pulos

1. Se você deseja inserir um novo nó na lista de pulos, ele inserirá o nó muito rapidamente porque não há rotações na lista de pulos.
2. A lista de pulos é simples de implementar em comparação com a tabela hash e a árvore de pesquisa binária.
3. É muito simples encontrar um nó na lista porque ela armazena os nós de forma ordenada.
4. O algoritmo da lista de pulos pode ser modificado facilmente em uma estrutura mais específica, como listas de pulos indexáveis, árvores ou filas de prioridade.
5. A lista de pulos é uma lista robusta e confiável.

Desvantagens da lista de pulos

1. Requer mais memória do que a árvore balanceada.
2. A pesquisa reversa não é permitida.
3. A lista ignorada pesquisa o nó muito mais lentamente do que a lista vinculada.

Aplicações da lista de pulos

1. É usado em aplicativos distribuídos e representa os ponteiros e o sistema nos aplicativos distribuídos.
2. É usado para implementar uma fila simultânea elástica dinâmica com baixa contenção de bloqueio.
3. Também é usado com a classe de modelo QMap.
4. A indexação da lista de pulos é usada na execução de problemas medianos.
5. A lista de pulos é usada para postagem de codificação delta na pesquisa Lucene.