Recorrido narrado

Llegar a la posición i

Para leer el valor de la posición 3, no hay cuenta posible: hay que empezar en la cabeza y seguir 3 enlaces.

En la figura, los números 1, 2 y 3 cuentan los saltos hasta el nodo de la posición 3.

función leer(lista, i):    nodo ← lista.cabeza    repetir i veces:        nodo ← nodo.siguiente    devolver nodo.valor

Por eso los costos de la lista son al revés que los del array:

• insertar o borrar después de un nodo que ya tienes: O(1), cambia uno o dos enlaces;
• llegar a la posición i: O(i);
• insertar en la posición i: O(i) para llegar más O(1) para enlazar.

La condición «que ya tienes» es la que muchas veces se olvida. «Insertar en medio de una lista es O(1)» solo es cierto si alguien ya te dio el nodo.

Su fila en la tabla de costos

Esta es la fila de la lista simple con solo cabeza. Los costos de «después de un nodo que ya tienes» llevan esa condición.