La lista doblemente enlazada es 3 ↔ 9 ↔ 1 ↔ 6:
cabeza señala el nodo del 3 y ultimo el del 6. A
desenlazar(x) se le pasa un puntero que ya está en la mano, así
que no hay nada que buscar.
1. Desenlazar el nodo del 1
¿Cuántas escrituras de puntero ejecuta?
cadena desde cabeza:
2. Línea por línea
La primera fila es lo que se alcanza siguiendo
siguiente desde cabeza; la segunda, lo que se
alcanza siguiendo anterior desde ultimo. El nodo
sale de una antes que de la otra.
3. El mismo código sobre la cabeza
Ahora x es el nodo del 3, el primero de
la cadena.
¿Cuántas escrituras de puntero ejecuta?
cadena desde cabeza:
¿Cuál de las dos escrituras cambia respecto al
caso del 1?
4. Lo mismo sin el campo anterior
La misma lista, ahora enlazada simple:
3 → 9 → 1 → 6. Se tiene en la mano el puntero al nodo del 1 y
hay que borrarlo. ¿Cuántos nodos hay que visitar desde la cabeza?
Lo que quedó
El campo anterior convierte el desenlace en
dos escrituras que no dependen del tamaño: Θ(1). Los dos if
son los extremos, donde del otro lado hay NULL y la escritura
cae sobre cabeza o sobre ultimo. En la simple el
empalme también son dos escrituras, pero antes hay que caminar hasta el
nodo anterior: Θ(n).