¿Por qué la complejidad de tiempo de eliminación de nodos en listas doblemente enlazadas (O (1)) es más rápida que la eliminación de nodos en listas unidas (O (n))?Complejidad temporal de la eliminación de nodos en listas simples y dobles
Tiene que ver con la complejidad de arreglar el siguiente puntero en el nodo anterior al que está eliminando.
Debido a que no se puede mirar hacia atrás ...
El problema supone que el nodo que ha de suprimirse conocido y un puntero a ese nodo está disponible.
Para eliminar un nodo y conectar el anterior y el siguiente nodo juntos, necesita conocer sus punteros. En una lista doblemente enlazada, ambos punteros están disponibles en el nodo que se eliminará. La complejidad de tiempo es constante en este caso, es decir, O (1).
Mientras que en una lista enlazada individualmente, el puntero al nodo anterior es desconocido y solo se puede encontrar al pasar la lista desde el encabezado hasta que llega al nodo que tiene un próximo nodo al nodo que se va a eliminar . La complejidad de tiempo en este caso es O (n).
En los casos en que el nodo que se va a eliminar se conoce solo por valor, la lista debe buscarse y la complejidad del tiempo se vuelve O (n) en las listas de enlace doble y simple.
Esto es incorrecto en lo que respecta a eliminar un nodo de una lista vinculada individualmente que requiere complejidad O (n) - vea mi respuesta a continuación. Hay un truco en el que copia el valor del siguiente nodo del que se está eliminando y luego lo omite para apuntar al nodo después, eliminando así la necesidad de atravesar la lista. – Ben
La inserción y eliminación en una posición conocida es O (1). Sin embargo, encontrar esa posición es O (n), a menos que sea la cabeza o la cola de la lista.
Cuando hablamos de complejidad de inserción y eliminación, generalmente asumimos que ya sabemos dónde va a ocurrir eso.
A menos que el elemento que se va a eliminar sea el nodo principal (o el primero), debemos atravesar el nodo antes de eliminarlo. Por lo tanto, en el peor de los casos, es decir, cuando necesitamos eliminar el último nodo, el puntero debe ir hasta el segundo último nodo atravesando (n-1) posiciones, lo que nos da una complejidad temporal de O (n) .
En realidad, la eliminación en listas unidas individualmente también se puede implementar en O (1).
Dada una lista enlazada con el siguiente estado:
SinglyLinkedList:
Node 1 -> Node 2
Node 2 -> Node 3
Node 3 -> None
Head = Node 3
Podemos implementar delete Note 2 de tal manera:
Node 2 Value <- Node 3 Value
Node 2 -> None
Aquí sustituimos el valor de Node 2 con el valor de su próxima nodo (Node 3) y establecer su próximo puntero de valor al siguiente puntero de valor de Node 3 (None) omitiendo el ahora "duplicado" Node 3. Por lo tanto, no es necesario cruzar.
¿Tarea? Escriba el código para eliminar un nodo de una lista vinculada individualmente, y entonces será obvio. –
Creo que no debería haber abreviaturas como dll en el título, pero no puedo pensar en una mejor. –