Listas e “pula pula”…

Estou assumindo aqui que você tenha alguma familiaridade, pelo menos conceitual, sobre listas encadeadas. São aquelas listas onde cada nó tem um link para o próximo item ou tem outro link para o item anterior (duplamente encadeadas). Com toda certeza você já reparou como é chato manter esse tipo de lista ordenado e ainda mais enfadonho é como procurar por um item específico dela… Para procurar um item você tem que percorrer toda a lista até achá-lo. Mas, e se tiver outro jeito?

Antes de mostrar essa “nova” maneira (“inventada” em 1989), deixe-me mostrar como uma lista simplesmente encadeada deve ser implementada… O quê? Você acha isso trivial? Veremos…

Para o iniciado é óbvio que um nó desse tipo de lista deve usar a estrutura abaixo (retirando a parte que contém a informação associada à chave – e estou usando uma “chave” inteira para facilitar):

struct lnode_s {
  int key;
  struct lnode_s *next;
};

O estudante geralmente aprende que a lista é montada desse jeito:

slist1

Não tarda muito para o programador perceber que essa configuração é ineficiente… Como é configurada uma lista vazia? Se quisermos apagar o item 4 teremos que verificar se este está no final da lista e atualizar o item 3 de acordo… Se tivessemos apenas o item 1 o que seria “atualizado de acordo”? A solução é simples: Usar nós “batentes”. Um nó head (cabeça) e um nó tail (rabo), com uma característica especial para o “rabo”: Ele aponta para si mesmo!

slist2

Uma lista vazia, agora, tem o ponteiro next do nó head apontando para o nó tail. Esses dois nós jamais serão apagados da estrutura e, assim, ao apagar qualquer item dentro da lista só precisamos apontar o nó anterior para o próximo nó. Temos a mesma vantagem ao inserir nós… E se tentarmos apagar um dos “batentes”, tudo o que precisamos fazer é checar se o nó queremos apagar é head ou tail e não dealocá-lo!

#include <stdlib.h>

struct lnode_s {
  int key;
  struct lnode_s *next;
};

struct list_s {
  struct lnode_s *head, *tail;
};

void list_create(struct list_s *plist)
{
  plist->head = (struct lnode_s *)malloc(sizeof(struct lnode_s));
  plist->tail = (struct lnode_s *)malloc(sizeof(struct lnode_s));
  plist->head->next = plist->tail;
  plist->tail->next = plist->tail;
}

/* Limpa uma lista, deletando todos os nós
   exceto head e tail. */
void list_clear(struct list_s *plist)
{
  struct lnode_s *n, *parent;

  parent = plist->head;
  n = parent->next;

  parent->next = n->next;
  while (n != n->next)
  {
    free(n);
    n = parent->next;
  }
}

/* Limpa e destrói head e tail. */
void list_destroy(struct list_s *plist)
{
  list_clear(plist);

  /* Livra-se de head e tail. */
  free(plist->head); plist->head = NULL;
  free(plist->tail); plist->tail = NULL;
}

/* Tenta inserir uma chave numa lista ordenada. */
struct lnode_s *list_insert(struct list_s *plist, int key)
{
  struct lnode_s *n, *parent, *new_node;

  parent = plist->head;

  /* Procura pela posição onde inserir a
     nova chave. */
  n = parent->next;
  while (n->next != n)
  {
    if (n->key > key)
      break;
    n = n->next;
    parent = parent->next;
  }

  new_node = (struct lnode_s *)malloc(sizeof(struct lnode_s));
  new_node->key = key;
  new_node->next = parent->next;
  parent->next = new_node;

  return new_node;
}

/* Tenta deletar uma chave. */
void list_delete(struct list_s *plist, int key)
{
  struct lnode_s *d, *parent;
  parent = plist->head;

  /* Procura pela chave a ser deletada. */
  d = parent->next;
  while (d != d->next)
  {
    if (d->key == key)
      break;
    d = d->next;
    parent = parent->next;
  }

  /* Apaga a chave! */
  parent->next = d->next;

  /* Só dealoca 'd' se não for o próprio tail. */
  if (d != d->next)
    free(d);
}

Se olhando para esses códigos você ainda não concordar comigo que usar nós batentes não é uma boa ideia, experimente implementar essas rotinas assumindo que o último nó é marcado com um ponteiro NULL… Você será obrigado a colocar alguns testes no seu código… TENTE!

Um dos problemas da lista encadeada:

É claro que você percebeu que para achar uma chave nesse tipo de lista temos que percorrê-la nó por nó. Mas podemos “pular” nós se adotarmos uma estrutura para um nó que contenha mais de um link! Suponha que, em um nó, tenhamos um link que aponte para o próximo nó, da maneira tradicional, e outro link que aponte para dois nós à frente (pula o próximo nó e aponta para o seguinte):

skplist1

A vantagem desse tipo de estrutura é óbvio: Se começarmos a pesquisar a lista à partir dos links “mais altos”, o faremos de dois em dois nós… Se estivermos tentando achar o nó 3 o acharemos em duas iterações ao invés de 3… Mas, se estivermos procurando o nó 4, chegaremos ao fim da lista sem termos encontrado, bastando retornar ao último nó (3) e continuarmos a pesquisa à partir do link “mais abaixo” e voilà!

Esse tipo de lista é chamada de skip list (daí minha piadinha sem graça com “pula pula”).

Na medida em que novos itens vão sendo inseridos na lista podemos aumentar a quantidade de links por nó (3 links pulam de 4 em 4 nós, 4 links pulam de 8 em 8… n links pularão 2^{n-1} nós). É claro que temos que solucionar o problema de quando devemos aumentar a quantidade de links, mas isso eu deixo pra vocês pesquisarem… ;)

Anúncios