Reinventarlo

El nodo centinela

El código de antes tiene dos ramas: una para la lista vacía y otra para el resto. Cada rama es un sitio donde olvidar algo.

Un centinela es un nodo falso que siempre está al principio y nunca guarda un valor. La lista vacía es solo el centinela.

¿Qué ventaja da un nodo centinela al agregar al final?Borrar el último nodo pasa a ser O(1) sin lista doble, porque el centinela guarda al penúltimo nodoLa cola nunca es nada: siempre hay un nodo tras el cual enlazar, y desaparece el caso de la lista vacíaAgregar es O(1) sin guardar la cola, porque el centinela siempre apunta al último nodo de la listaAhorra memoria: el centinela reemplaza a la cabeza y a la cola con un único campo compartido por las dos