Recorrido narrado
La lista doble
En una lista simple, borrar el último nodo obliga a recorrer: para mover la cola hay que encontrar el penúltimo, y nada apunta hacia atrás.
Una lista doble guarda en cada nodo dos enlaces: siguiente y anterior. Con eso:
- borrar el último es O(1): la cola nueva es
cola.anterior; - borrar un nodo que ya tienes es O(1): sus vecinos se enlazan entre sí;
- recorrer hacia atrás es posible.
El precio: cada nodo gasta un enlace más, y cada operación tiene que mantener los dos sentidos.
función quitar(lista, n): # lista doble con centinela n.anterior.siguiente ← n.siguiente n.siguiente.anterior ← n.anteriorEn la figura, quitar aplicado al último nodo de una lista doble con centinela, en dos pasos.
Con un centinela que cierra el círculo (su anterior es el último y su siguiente es el primero), quitar no tiene ningún caso especial.
Su fila en la tabla de costos
La cola cambia la columna de insertar al final, y la lista doble cambia la de borrar al final:
| Representación | leer(i) |
insertar o borrar al inicio | insertar al final | borrar al final | insertar o borrar en i |
|---|---|---|---|---|---|
| lista simple con cabeza y cola | O(i) | O(1) | O(1) | O(n) | O(i) para llegar, O(1) para enlazar |
| lista doble con centinela | O(min(i, n − i)), desde el extremo más cercano | O(1) | O(1) | O(1) | llegar, más O(1) |
Lee el recorrido de esta página. Al pasar al siguiente momento, este cuenta como leído.