Algoritmo para eliminar un elemento en una sola lista vinculada con O (1) complejidad

Question

Soy estudiante de informática en Alemania. Mi profesor usó la siguiente pregunta para pensar:

'Dada una referencia a un nodo en una sola lista vinculada (que no es el último nodo). Proporcione un algoritmo para eliminar este elemento de la lista que tiene una complejidad O (1) mientras mantiene la integridad '.

Pensé en esto, pero estoy bastante seguro de que no existe tal algoritmo. dado que es una lista vinculada única, debe pasar por todos los nodos de la lista hasta que llegue al nodo que debe eliminarse, porque debe modificar el puntero siguiente en el nodo anterior al borrado. Lo que llevaría a O (n) complejidad.

¿E-mail perdiendo cualquier cosa?

Answer 1

Depende de si los nodos son mutables (en valor) o no.

Hay es una manera de hacerlo, si se puede hacer lo que quiera con los nodos:

toDelete.value = toDelete.next.value 
toDelete.next = toDelete.next.next 

Toda la información de toDelete ahora se ha sobrescrito, por la información en el antiguo toDelete.next. (Dependiendo de la plataforma, puede que necesite liberar el antiguo toDelete.next, lo que significa que debe tener una referencia temporal. No es bueno si alguien más todavía tiene una referencia, por supuesto. En Java/C# simplemente lo ignoraría. .)

traté de encontrar una forma de insinuar que sin dar a la basura, pero es un poco difícil ...

no confían en que esto no es el último nodo en la lista de embargo.

Answer 2

no considerados exactamente la eliminación de un nodo, pero se puede copiar los datos del siguiente nodo de la corriente y elimine el nodo siguiente:

// pseudocode: 
this.data = next.data; 
var temp = this.next; 
this.next = next.next; 
delete temp; 

Answer 3

Sí. Mantiene como su puntero iterativo, un puntero al siguiente puntero de la lista anterior.

walk = &head; 
while (!match(*walk)) { 
    walk = &walk[0]->next; 
    if (!*walk) return ; 
} 
*walk = walk[0]->next; 

Answer 4

Si los nodos son las estructuras básicas de la memoria, puede copiar el contenido del nodo "siguiente" en la posición de memoria del nodo eliminado, y desasignar la memoria en el nodo "siguiente" solía ser.

Answer 5

Suponiendo que tiene el puntero al nodo que desea eliminar. Replica el siguiente valor en el nodo actual. Reemplace el puntero actual por el nodo al que apunta.

Answer 6

mueve los datos, no el enlace. mira a este otro hilo: Deleting a middle node from a single linked list when pointer to the previous node is not available