La lista es 5 → 2 → 7 y se ejecuta
insertar(2, 9). Como la posición no es 0, el código toma la rama
que busca el nodo anterior.
1. La cadena al terminar
desde cabeza:
2. Línea por línea
La cadena es lo que se alcanza desde cabeza:
el nodo nuevo entra en ella solo cuando anterior lo toma.
3. Las dos líneas al revés
Se cambia el orden del empalme y queda
anterior->siguiente = nuevo; primero y
nuevo->siguiente = anterior->siguiente; después. ¿Qué
lista queda?
4. Los pasos hasta el anterior
Sobre una lista de cuatro elementos, ¿cuántos pasos
da nodoEn(p - 1) dentro de insertar(p, e) para
p = 1, p = 2 y p = 3?
pasos:
¿Y con p = 0?
Lo que quedó
El empalme son dos escrituras y su orden no es libre: el
nodo nuevo toma el resto de la cadena antes de que el anterior lo tome a
él. Lo que cuesta es llegar al anterior, p - 1 pasos desde la
cabeza, y por eso insertar es Θ(p) y Θ(1) cuando p es 0.