algorithm - ultimo - listas ligadas

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

Question

Soy un 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.

¿Me estoy perdiendo algo?

Answer 1

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

Hay una forma de hacerlo, si puedes hacer lo que quieras con los nodos:

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

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

Traté de encontrar una manera de insinuarlo sin revelarlo, pero es un poco complicado ...

Sin embargo, confía en que este no sea el último nodo de la lista.

Answer 2

No se consideró eliminar un nodo exactamente, pero puede copiar los datos del siguiente nodo a la actual y eliminar el siguiente nodo:

// 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 estructuras básicas en la memoria, puede copiar el contenido del nodo "siguiente" en la ubicación de memoria del nodo eliminado y desasignar la memoria donde solía estar el "siguiente" nodo.

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

mover los datos, no el enlace. mira este otro hilo: Eliminar un nodo intermedio de una sola lista vinculada cuando el puntero al nodo anterior no está disponible