¿Cómo ofrece un nodo centinela beneficios sobre NULL?

Creo que un pequeño ejemplo de código sería una mejor explicación que una discusión teórica.

El siguiente es el código para la eliminación de nodos en una lista doblemente vinculada de nodos donde NULL se utiliza para marcar el final de la lista y donde dos punteros first y last se utilizan para mantener la dirección del primer y último nodo:

// Using NULL and pointers for first and last
if (n->prev) n->prev->next = n->next;
        else first = n->next;
if (n->next) n->next->prev = n->prev;
        else last = n->prev;

Y este es el mismo código donde en su lugar hay un nodo ficticio especial para marcar el final de la lista y donde la dirección del primer nodo en la lista se almacena en el campo next del nodo especial y donde el último nodo de la lista se almacena en el campo prev del nodo ficticio especial:

// Using the dummy node
n->prev->next = n->next;
n->next->prev = n->prev;

El mismo tipo de simplificación también está presente para la inserción de nodos; por ejemplo, para insertar nodo n antes de nodo x (teniendo x == NULL o x == &dummy que significa inserción en la última posición) el código sería:

// Using NULL and pointers for first and last
n->next = x;
n->prev = x ? x->prev : last;
if (n->prev) n->prev->next = n;
        else first = n;
if (n->next) n->next->prev = n;
        else last = n;

Y

// Using the dummy node
n->next = x;
n->prev = x->prev;
n->next->prev = n;
n->prev->next = n;

Como puede ver el enfoque de nodo ficticio eliminado para una lista doblemente vinculada, todos los casos especiales y todos condicionales.

La siguiente imagen representa los dos enfoques para la misma lista en memoria...

La respuesta a tu pregunta (1) está en la última frase de la entrada enlazada de Wikipedia: "Como nodos que normalmente enlazarían a NULL ahora enlazarían a "nil" (incluyendo nil en sí), elimina la necesidad de una costosa operación de rama para comprobar si hay NULL."

Normalmente necesita probar un nodo para NULL antes de acceder a él. Si en cambio tiene un nodo nil válido, entonces no necesita hacer esta primera prueba, guardando una comparación y una rama condicional, que de lo contrario puede ser caro en CPU superescalar modernas cuando la rama está mal predicha.

Intentaré responder en el contexto de la biblioteca de plantillas estándar:

1) En una llamada a "next ()", NULL no indica necesariamente el final de la lista. ¿Qué pasa si se produce un error de memoria? Devolver un nodo centinela, es una forma definitiva de indicar que se había producido el final de la lista, y no algún otro resultado. En otras palabras, NULL podría indicar una variedad de cosas, no solo el final de la lista.

2) Este es solo un método posible: cuando cree su lista, cree un nodo privado que sea no compartido fuera de la clase (llamado "lastNode" por ejemplo). Al detectar que has iterado hasta el final de la lista, haz que "next()" devuelva una referencia a "lastNode". También haga que un método llamado "end()" devuelva una referencia a "lastNode". Por último, dependiendo de cómo implemente su clase, es posible que deba anular el operador de comparación para que esto funcione correctamente.

Ejemplo:

class MyNode{

};

class MyList{

public:
    MyList () : lastNode();

    MyNode * next(){

       if (isLastNode) return &lastNode;
       else return //whatever comes next
    }

    MyNode * end() {

       return &lastNode;
    }

    //comparison operator
    friend bool operator == (MyNode &n1, MyNode &n2){

        return (&n1 == &n2); //check that both operands point to same memory
    }


private:
    MyNode lastNode;
};


int main(){

  MyList list;
  MyNode * node = list.next();

  while ( node != list.end() ){ 

     //do stuff!

     node = list.next();
  }

  return 0; 
}