Em uma entrevista TED de 2016 (14h10), Linus Torvalds fala sobre um bom estilo de codificação. Como exemplo, ele dá duas opções para remover elementos de listas unidas individualmente (veja abaixo). A primeira opção tem um caso especial, enquanto a outra não. Linus prefere o último.



Seu comentário:

[...] Não há necessidade de pensar sobre por que não há nenhuma declaração if aqui. É importante olhar para o problema de uma perspectiva diferente e reescrevê-lo para que o caso especial desapareça e se torne um caso normal, e esse é um bom código . - L. Torvalds

Linus mostra um pseudocódigo de estilo C bastante simples como exemplo. Mas não fornece uma explicação conceitual. Portanto, não está imediatamente claro como um ponteiro indireto funciona.



Vamos examinar mais de perto essa solução e suas vantagens. Como bônus, não só é mostrado o apagamento, mas também a inserção de um elemento via endereçamento indireto.

O código

A estrutura de dados básica para uma lista unida de inteiros é mostrada na Fig. 1.





Fig. 1. Uma lista unida de inteiros



Números são valores inteiros selecionados aleatoriamente, e as setas correspondem a ponteiros: head



 - este é um ponteiro de tipo IntListItem*



, todos os blocos são instâncias de uma estrutura IntListItem



, cada um com sua própria variável ( next



no código) do tipo IntListItem*



, que aponta para o próximo elemento.



Implementação da estrutura de dados em C:

struct IntListItem {
    int value;
    struct IntListItem* next;
};
typedef struct IntListItem IntListItem;

struct IntList {
    IntListItem* head;
};
typedef struct IntList IntList;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Também a API (mínima):

/* The textbook version */
void remove_cs101(IntList* l, IntListItem* target);
/* A more elegant solution */
void remove_elegant(IntList* l, IntListItem* target);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Agora vamos dar uma olhada nas implementações remove_cs101()



e remove_elegant()



. O código dos exemplos não contradiz o pseudocódigo do exemplo de Linus, mas ele compila e executa.

Versão básica

Figura: 2. Modelo conceitual da estrutura de dados da lista no algoritmo básico

void remove_cs101(IntList *l, IntListItem *target)
{
    IntListItem *cur = l->head, *prev = NULL;
    while (cur != target) {
        prev = cur;
        cur = cur->next;
    }
    if (prev) {
        prev->next = cur->next;
    } else {
        l->head = cur->next;
    }
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Na abordagem padrão, há dois ponteiros de percurso cur



e prev



, que marcam a posição de percurso atual e anterior na lista, respectivamente. cur



começa no topo da lista head



e avança até que o alvo seja encontrado. Por sua vez, ele prev



começa com NULL



e é subsequentemente atualizado para o valor anterior cur



cada vez que avança. Quando o alvo é encontrado, o algoritmo verifica se ele não é prev



zero. Nesse caso, ele cur



aponta para o primeiro item da lista; nesse caso, excluir significa mover o cabeçalho da lista para frente.

Uma solução mais elegante

A versão mais elegante tem menos código e não requer um branch separado para remover o primeiro item da lista.

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) != target) {
        p = &(*p)->next;
    }
    *p = target->next;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

O código usa um ponteiro indireto p



que contém o endereço do ponteiro para o item da lista, começando no endereço head



. A cada iteração, este ponteiro é expandido para incluir o endereço do ponteiro para o próximo item da lista, ou seja, o endereço do item next



na lista atual IntListItem



. Quando o ponteiro para o item da lista (*p)



é igual target



, saímos do ciclo de pesquisa e removemos o item da lista.

Como funciona?

Um ponteiro indireto tem p



duas vantagens conceituais:

1. Permite interpretar uma lista encadeada de forma que o ponteiro head
   
   
   
   se torne parte integrante da estrutura de dados. Isso elimina a necessidade de um estojo especial para remover o primeiro item.
   
   
2. Também permite que você avalie o estado do loop while
   
   
   
   sem ter que liberar o ponteiro que aponta para target
   
   
   
   . Isso permite que você altere o ponteiro para target
   
   
   
   e contorne com um único iterador, ao contrário de prev
   
   
   
   e cur
   
   
   
   .

Vamos dar uma olhada em cada item por vez.

Integração do ponteiro de cabeça

O modelo padrão interpreta uma lista vinculada como uma sequência de instâncias IntListItem



. O início da sequência pode ser obtido por meio de um ponteiro head



. Isso leva ao modelo conceitual mostrado na Fig. 2. O ponteiro é head



simplesmente tratado como um identificador para acessar o início da lista. prev



e cur



são ponteiros de tipo IntListItem*



e sempre apontam para ou NULL



.



A implementação elegante usa um esquema de endereçamento indireto, que oferece uma visão diferente da estrutura de dados:





Fig. 3. Modelo conceitual da estrutura de dados da lista em uma solução mais elegante



Aqui p



representa o tipoIntListItem**



e contém o endereço do ponteiro para o item da lista atual. Quando o ponteiro se move para frente, seu endereço muda para o próximo elemento.



No código, parece p = &(*p)->next



:

1. (*p)
   
   
   
   : remove a referência do endereço do ponteiro para o item da lista atual.
   
   
2. ->next
   
   
   
   : desreferencie este ponteiro novamente e selecione o campo com o endereço do próximo elemento.
   
   
3. &
   
   
   
   : obtém o endereço deste campo (ou seja, obtém um ponteiro para ele).

Isso segue a interpretação de uma estrutura de dados, onde uma lista é uma sequência de ponteiros para os elementos IntListItem



(Figura 3).

Toque final

Um benefício adicional dessa interpretação em particular é que ela permite que o ponteiro seja editado next



para o predecessor do elemento atual durante a travessia .



Se p



contiver o endereço de um ponteiro para um elemento da lista, a comparação no loop de pesquisa será:

while ((*p) != target) {
    ...
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

O ciclo de busca terminará se (*p)



for igual target



, e assim que isso acontecer, ainda podemos mudar (*p)



, já que mantemos seu endereço p



. Assim, mesmo que o loop itere até o fim, um descritor (endereço de campo next



ou ponteiro head



) é armazenado e pode ser usado para alterar diretamente o ponteiro para um elemento.



É por isso que podemos alterar a entrada para o ponteiro do elemento para apontar para um local diferente, usando *p = target->next



e, portanto, não precisamos ignorar ponteiros prev



e cur



remover o item.

Nova aplicação

Acontece que a mesma ideia pode ser aplicada a uma implementação extremamente lacônica de outra função em listas vinculadas :, insert_before()



ou seja, inserir esse elemento antes de outro.

Inserção antes do elemento existente

Primeiro, vamos adicionar a seguinte declaração a list.h



:

void insert_before(IntList *l, IntListItem *before, IntListItem *item);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

A função pegará um ponteiro para a lista l, um ponteiro antes de um elemento nesta lista e um ponteiro para um novo elemento da lista que a função irá inserir antes dele.

Refatoração rápida

Antes de prosseguir, vamos transformar o loop de pesquisa em uma função separada:

static inline IntListItem **find_indirect(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) && (*p) != target) {
        p = &(*p)->next;
    }
    return p;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

e usá-lo em remove_elegant()



:

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = find_indirect(l, target);
    *p = target->next;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Implementação de Insert_before ()

Usá- find_indirect()



lo é fácil de implementar insert_before()



:

void insert_before(IntList *l, IntListItem *before, IntListItem *item)
{
    IntListItem **p = find_indirect(l, before);
    *p = item;
    item->next = before;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Particularmente agradáveis ​​são as semânticas sólidas para casos extremos: se before



apontar para o topo da lista, um novo elemento será inserido no início, se before



for nulo ou inválido (ou seja, não existir em l



), um novo elemento será adicionado no final.

Conclusão

O pré-requisito para uma solução mais elegante para excluir elementos é uma mudança simples: um ponteiro indireto IntListItem**



para iterar sobre os ponteiros para listar elementos. Tudo o resto segue daí: não há necessidade de casos ou ramos especiais. Um iterador é suficiente para localizar e remover o elemento de destino. E verifica-se que a mesma abordagem fornece uma solução elegante para a inserção em geral e a inserção na frente de um elemento existente em particular.



Então, voltando à observação inicial de Linus, isso é um indicador de bom gosto? Difícil de dizer. Mas há claramente uma solução criativa e muito elegante para um problema conhecido.