O método complicado (e rápido!) de deletar itens de uma lista simples de Linus Torvalds

Eis uma implementação interessante. Considere que temos uma lista de encadeamento simples (sem os “batentes”) e queremos apagar um dos nós. A idéia é passar o ponteiro do primeiro item da lista e uma chave e, ao deletar o item, retornar o ponteiro dele para o chamador ou NULL, se o item não for encontrado. A estrutura do nó não poderia ser mais simples:

typedef struct node_s {
  int key;
  struct node_s *next;
} node_t;

De cara em pensaria em implementar algo assim:

node_t *delete_node(node_t **head, int key)
{
  node_t *p = *head;
  node_t *q;

  /* Caso especial: Se p == head... */
  if (p && p->key == key)
  {
    /* ... faz head apontar para o próximo item. */
    *head = p->next;
    return p;    
  }
  
  /* Se não apagarmos o primeiro nó, percorre a
     lista guardando o ponteiro para o nó 
     anterior. */
  q = p; p = p->next;
  while (p && p->key != key)
    { q = p; p = p->next; }

  /* Não achou? Sai com NULL. */
  if (!p) return NULL;

  /* Reajusta o ponteiros do nó
     anterior. */
  q->next = p->next;

  return p;
}

Supondo que o nó desejado seja o segundo da lista, a rotina funciona mais ou menos como descrita nos gráficos abaixo:

method1

Poderíamos setar o ponteiro next do nó apontado por p para “desatachá-lo” da lista, mas para quê nos preocuparmos com isso? Repare que a rotina tem um caso especial: Quando o ponteiro p aponta para o mesmo lugar que head e este é o nó que queremos, temos que fazer head apontar para o próximo nó e retornarmos seu antigo valor.

A verificação desse caso especial torna a rotina mais lenta do que se não tivéssemos um caso especial, certo? Acontece que, se prestarmos bastante atenção, head é semanticamente semelhante ao ponteiro next de cada um dos nós, só que ele aponta para o primeiro nó! E, ainda, podemos usar um pouquinho da mágica dos ponteiros…

O que é um ponteiro? É uma variável, como qualquer outra, cujo conteúdo é o endereço de memória de alguma coisa. A forma que usamos para obter essa “alguma coisa”, de posse de uma variável do tipo ponteiro, é usarmos o operador de indireção ‘*’. Assim, que tal usarmos um ponteiro que aponta para um outro ponteiro? Poderíamos fazer um ponteiro desse tipo apontar para head e, conforme formos andando em direção ao final da lista, fazê-lo apontar para os membros next de cada nó! Isso tem a vantagem de que, em qualquer momento, estaríamos apontando para o ponteiro next do nó imediatamente anterior ao que queremos…

A rotina de Torvalds fica assim:

node_t *delete_node(note_t **head, int key)
{
  node_t **p = head;
  node_t *q;

  while (*p && (*p)->key != key)
    p = &(*p)->next;
    /* Quando achar a chave, p apontará
       para o ponteiro head ou para o
       ponteiro next do nó anterior. */

  /* Se não encontrou, sai com NULL. */
  if (!*p) return NULL;

  /* Ajusta os links. */
  q = *p;
  *p = q->next;
  
  return q;
}

A rotina acima funciona como descrito no gráfico abaixo, supondo que o nosso nó seja o segundo, como no exemplo anterior:

method2

O resultado é exatamente o mesmo sem o caso especial. O uso da indireção ‘*p’ refere-se ao ponteiro head no primeiro teste do loop, mas se este não for o nó desejado (se (*p)->key != key) então p será atualizado para o endereço do membro next do nó corrente. Dessa forma podemos usar este ponteiro para atualizar a referência para o próximo nó, mesmo que o nó seja o mesmo apontado por head.

Lindo, não?

Anúncios