La lista es 2 → 5 → 1 y se ejecuta
agregar(7) con las dos implementaciones: la que solo guarda
cabeza y la que además guarda ultimo.
1. Cuántos nodos toca cada versión
Contando la cabeza y cada avance,
¿cuántos nodos de la cadena vieja toca cada versión antes de enlazar el
nodo nuevo?
Sin ultimo:
Con ultimo:
2. Borrar el último
Sobre la versión con ultimo, la lista
quedó en 2 → 5 → 1 → 7 y ahora se ejecuta
eliminar(3), que borra el 7. ¿Qué tiene que pasar con
ultimo?
3. Vaciar por el frente
Sobre 2 → 5 → 1 se ejecuta
eliminar(0) tres veces. ¿Con qué quedan cabeza y
ultimo?
Lo que quedó
Guardar dónde termina la cadena baja
agregar de Θ(n) a Θ(1), y el precio son dos casos nuevos en
eliminar: cuando se borra el último nodo y cuando la lista se
vacía. Los dos escriben ultimo, y dejarlos por fuera es lo
que produce un puntero colgante.