A maneira correta de remover um item de uma lista vinculada

Nesta entrevista ao Slashdot, Linus Torvalds é citado como tendo dito:

Eu já vi muitas pessoas que excluem uma entrada de lista vinculada individualmente acompanhando a entrada "anterior" e, em seguida, para excluir a entrada, fazendo algo como

se (anterior) anterior-
  > próxima = entrada-> próxima;
else
  list_head = entry-> next;

e sempre que vejo código assim, simplesmente digo "Essa pessoa não entende ponteiros". E, infelizmente, é bastante comum.

As pessoas que entendem ponteiros simplesmente usam um "ponteiro para o ponteiro de entrada" e inicializam isso com o endereço do list_head. E então, ao percorrer a lista, eles podem remover a entrada sem usar condicionais, apenas executando "* pp = entry-> next".

Como desenvolvedor de PHP, não toquei em indicadores desde a introdução ao C na universidade há uma década. No entanto, sinto que este é um tipo de situação com a qual devo pelo menos estar familiarizado. Sobre o que Linus está falando? Para ser sincero, se me pedissem para implementar uma lista vinculada e remover um item, a maneira 'errada' acima é a maneira que eu faria. O que preciso saber para codificar como Linus diz melhor?

Estou perguntando aqui, e não no Stack Overflow, pois não estou tendo um problema com isso no código de produção.

Usando minhas habilidades no L331 MS Paint:

A solução original é apontar para Nós via curr. Nesse caso, você verifica se o próximo nó depois currtem o valor de exclusão e, se sim, redefine o ponteiro do currnó next. O problema é que não há um nó que aponte para o início da lista. Isso significa que deve haver um caso especial para verificar isso.

O que Linus (provavelmente) propõe, em vez disso, não é salvar o ponteiro no nó examinado atual, mas o ponteiro no ponteiro no nó atual (rotulado pp). A operação é a mesma - se o ppponteiro apontar para um nó com o valor correto, você redefine o ppponteiro.

A diferença vem no começo da lista. Embora não haja Nó que aponte para o início da lista, na verdade, existe um ponteiro para o início da lista. E é da mesma forma um ponteiro para um nó, assim como outro nextponteiro de nós . Portanto, não há necessidade de uma cláusula especial para o início da lista.

Exemplo de código

// ------------------------------------------------------------------
// Start by pointing to the head pointer.
// ------------------------------------------------------------------
//    (next_ptr)
//         |
//         v
// [head]----->[..]----->[..]----->[..]----->[to_remove]----->[....]
Node** next_ptr = &list->head;

// ------------------------------------------------------------------
// Search the list for the matching entry.
// After searching:
// ------------------------------------------------------------------
//                                  (next_ptr)
//                                       |
//                                       v
// [head]----->[..]----->[..]----->[..]----->[to_remove]----->[next]
while (*next_ptr != to_remove) // or (*next_ptr)->val != to_remove->val
{
    Node* next_node = *next_ptr
    next_ptr = &next_node->next;
}

// ------------------------------------------------------------------
// Dereference the next pointer and set it to the next node's next
// pointer.
// ------------------------------------------------------------------
//                                           (next_ptr)
//                                                |
//                                                v
// [head]----->[..]----->[..]----->[..]---------------------->[next]
*next_ptr = to_remove->next;

Se precisarmos de alguma lógica para destruir o nó, basta adicionar uma linha de código no final:

// Deallocate the node which is now stranded from the list.
free(to_remove);