Based on this article from the creator of the Skip List, William Pugh, I came up with the following implementation in C (c99).
1. Create the data structures:
node
/**
* Definição da estrutura de dados dos nós.
*/
typedef struct node {
/* Valor do nó.
*/
char word[WORD_SIZE];
/* Nível do nó.
*/
int level;
/* Arranjo de ponteiros para os nós que vem à frente deste.
*/
struct node** forward;
}__node__;
skip
/**
* Definição da estrutura de dados da skip list.
*/
typedef struct skip {
/* Nó-cabeçalho da skip list.
*/
struct node* header;
/* Nível do cabeçalho da skip list.
*/
int level;
}__skip__;
2. Function to generate the levels of each new node, numbers that are random due to the probabilistic nature of skip lists.
/**
* Gerar números aletórios entre 0 e 1.
*/
float randomize(){
float _result = 0.0;
_result = ((float)rand()) / (float)(RAND_MAX);
return _result;
}
/**
* Criar uma novo nível aleatório.
*/
int random_level(){
int _result = 1;
while(randomize() < P && _result < MAX_LEVEL){
_result++;
}
return _result;
}
3. Function to create node instances for each new node that will be entered in the skip list.
/**
* Criar uma nova instância de node.
*/
struct node* criar_node(int level, char* word){
struct node* _result = 0;
/* Alocando memória para armazenar uma instância de node.
*/
_result = malloc(sizeof(struct node));
/* Atribuindo ao novo nó o seu level.
*/
_result->level = level;
/* Alocando memória para o arranjo forward.
*/
_result->forward = malloc( (level + 1) * sizeof(struct node*));
/* Configurar todas as posições do arranjo forward com 0 (null).
*/
int _index = 0;
while(_index < (_result->level + 1)){
_result->forward[_index] = 0;
_index++;
}
/* Atribuindo o valor do novo nó.
*/
strcpy(_result->word, word);
return _result;
}
4. Function to create a skip instance, which is the skip list representation.
/**
* Criar uma nova skip list.
*/
struct skip* criar_skip(){
struct skip* _result = 0;
/* Alocando memória para a instância de skip.
*/
_result = malloc(sizeof(struct skip));
/* Criando o nó header, sendo seu nível o valor máximo.
*/
_result->header = criar_node(MAX_LEVEL, NULL_STRING);
/* Configurando level da skip list como sendo zero.
*/
_result->level = 0;
return _result;
}
5. Function to search for a value in the skip list.
/**
* Procurar na skip list por toSearch e retornar o nó onde esse valor está.
*/
struct node* procurar(struct skip* sl, char* toSearch){
/* x incialmente aponta para o header da skip list.
*/
struct node* x = sl->header;
/* Nível inicial.
*/
int _level = x->level;
/* Iniciar pelo topo, descendo até o nível mais baixo.
*/
for(int i = _level; i >= 0; i--){
/* Enquando forward[i] não for null E forward[i]->word menor que toSearch
*/
while(x->forward[i] != 0 && strcmp(x->forward[i]->word, toSearch) < 0){
/* Andar para frente.
*/
x = x->forward[i];
}
}
/* Nesse ponto existem 3 possibilidades para o valor de x, são elas:
* - x está apontando para o valor que estava sendo procurado;
* - x está apontando para um valor maior que o procurado;
* - x está null.
*/
x = x->forward[0];
/* Retornar o valor de x.
*/
return (struct node*)x;
}
Since the
procurar function can return an instance of
node , then it is interesting to create a function that checks for the existence of a certain value in the skip list and returns only
true (!=0) or
false (==0) .
/**
* Verificar se um determinado valor existe na skip list.
* 0 = o valor não existe na skipt
* qualquer valor diferente de 0, o valor existe na skip list.
*/
int existe(struct skip* sl, char* toSearch){
int _result = 0;
struct node* _encontrado = procurar(sl, toSearch);
if(_encontrado != 0){
if(strcmp(_encontrado->word, toSearch) == 0){
/* Existe.
*/
_result = 1;
}
}
return _result;
}
6. Function to enter values in the skip list.
/**
* Inserir word na skip list.
*/
void inserir(struct skip* sl, char* word){
/* Alocando memória para o arranjo que armazena
* os nós que deverão ser atualizados.
*/
struct node** update = malloc( (MAX_LEVEL + 1) * sizeof(struct node*) );
/* x aponta para o cabeçalho da skip list.
*/
struct node* x = sl->header;
/* Nível inicial.
*/
int _level = x->level;
/* Iniciar pelo topo, descendo até o nível mais baixo.
*/
for(int i = _level; i >= 0; i--){
/* Enquando forward[i] não for null E forward[i]->word menor que toSearch
*/
while(x->forward[i] != 0 && strcmp(x->forward[i]->word, word) < 0){
/* Andar para frente.
*/
x = x->forward[i];
}
/* Guardar em update o nó que será atualizado.
*/
update[i] = x;
}
/* Nesse ponto existem 3 possibilidades para o valor de x, são elas:
* - x está apontando para o valor que estava sendo procurado;
* - x está apontando para um valor maior que o procurado;
* - x está null.
*/
x = x->forward[0];
/* Caso x seja null ou x->word não seja igual à word
*/
if(x == 0 || strcmp(x->word, word) != 0){
/* Obter o nível do nó novo.
*/
int _newLevel = random_level();
/* Caso o nível do nó novo seja maior que o nível da skip list
*/
if(_newLevel > _level){
/* Atualizar o arranjo updade para que aponte para o header da skip list
* em todas as posições entre seu nível e o nível do nó novo.
*/
for(int _index = _level + 1; _index <= _newLevel; _index++){
update[_index] = sl->header;
}
/* Atualizar o nível da skip list.
*/
sl->level = _newLevel;
}
/* Criar a instância do nó novo para.
*/
x = criar_node(_newLevel, word);
/* Inserindo o nó novo na skip list.
*/
for(int _index = 0; _index <= _newLevel; _index++){
x->forward[_index] = update[_index]->forward[_index];
update[_index]->forward[_index] = x;
}
}
}
Finally, check out the full code, working and testing on ideone .
It is also published in the gist source code.
