La forma correcta de eliminar un elemento de una lista vinculada

En esta entrevista de Slashdot, se cita a Linus Torvalds diciendo:

He visto a demasiadas personas que eliminan una entrada de la lista enlazada individualmente haciendo un seguimiento de la entrada "anterior", y luego eliminan la entrada, haciendo algo como

if (anterior) anterior-
  > siguiente = entrada-> siguiente;
else
  list_head = entry-> next;

y cada vez que veo un código así, solo digo "Esta persona no entiende los punteros". Y lamentablemente es bastante común.

Las personas que entienden los punteros simplemente usan un "puntero al puntero de entrada" e inicializan eso con la dirección de list_head. Y luego, a medida que atraviesan la lista, pueden eliminar la entrada sin usar ninguna condición, simplemente haciendo un "* pp = entrada-> siguiente".

Como desarrollador de PHP, no he tocado punteros desde Introducción a C en la universidad hace una década. Sin embargo, siento que este es un tipo de situación con la que al menos debería estar familiarizado. ¿De qué está hablando Linus? Para ser honesto, si me pidieran implementar una lista vinculada y eliminar un elemento, la forma "incorrecta" anterior es la forma en que lo haría. ¿Qué necesito saber para codificar como Linus dice mejor?

Estoy preguntando aquí en lugar de sobre Stack Overflow, ya que en realidad no tengo problemas con esto en el código de producción.

Usando mis habilidades de pintura L331 MS:

La solución original es apuntar a los nodos vía curr. En ese caso, verifica si el siguiente nodo currtiene el valor de eliminación y, de ser así, restablece el puntero del currnodo next. El problema es que no hay ningún nodo que apunte al encabezado de la lista. Eso significa que tiene que haber un caso especial para verificarlo.

Lo que propone Linus (probablemente) en su lugar no es guardar el puntero en el nodo examinado actual, sino más bien el puntero al puntero en el nodo actual (etiquetado pp). La operación es la misma: si el pppuntero apunta a un nodo con el valor correcto, reinicia el pppuntero.

La diferencia viene al comienzo de la lista. Si bien no hay ningún nodo que apunte al encabezado de la lista, de hecho, hay un puntero al encabezado de la lista. Y es lo mismo un puntero a un nodo, tal como otro nextpuntero de nodos . Por lo tanto, no hay necesidad de una cláusula especial para el comienzo de la lista.

Ejemplo 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;

Si necesitamos algo de lógica para destruir el nodo, entonces podemos agregar una línea de código al final:

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