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
| Sim não | Complexidade | Caso médio | Pior caso |
|---|---|---|---|
| 1. | Complexidade de acesso | O(logn) | Sobre) |
| 2. | Complexidade da pesquisa | O(logn) | Sobre) |
| 3. | Excluir complexidade | O(logn) | Sobre) |
| 4. | Inserir complexidade | O(logn) | Sobre) |
| 5. | Complexidade espacial | - | O(nlogn) |
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.
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.
- 6 com nível 1.
- 29 com nível 1.
- 22 com nível 4.
- 9 com nível 3.
- 17 com nível 1.
- 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
- 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.
- A lista de pulos é simples de implementar em comparação com a tabela hash e a árvore de pesquisa binária.
- É muito simples encontrar um nó na lista porque ela armazena os nós de forma ordenada.
- 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.
- A lista de pulos é uma lista robusta e confiável.
Desvantagens da lista de pulos
- Requer mais memória do que a árvore balanceada.
- A pesquisa reversa não é permitida.
- A lista ignorada pesquisa o nó muito mais lentamente do que a lista vinculada.
Aplicações da lista de pulos
- É usado em aplicativos distribuídos e representa os ponteiros e o sistema nos aplicativos distribuídos.
- É usado para implementar uma fila simultânea elástica dinâmica com baixa contenção de bloqueio.
- Também é usado com a classe de modelo QMap.
- A indexação da lista de pulos é usada na execução de problemas medianos.
- A lista de pulos é usada para postagem de codificação delta na pesquisa Lucene.