Eliminación de un nodo medio de una sola lista vinculada cuando el puntero al nodo anterior no está disponible

5 minutos de lectura

avatar de usuario
nitina

¿Es posible eliminar un nodo intermedio en la lista enlazada única cuando la única información disponible es el puntero al nodo que se eliminará y no el puntero al nodo anterior? Después de la eliminación, el nodo anterior debe apuntar al nodo al lado nodo eliminado.

  • ¿Sobre qué trata? Me parece una pregunta bastante justa.

    – 1800 INFORMACIÓN

    16 de septiembre de 2008 a las 3:51

  • Esta es una pregunta de entrevista clásica.

    – Motti

    16 de junio de 2009 a las 11:21

  • Una respuesta muy limpia aquí en un hilo relacionado.

    – RBT

    3 de marzo de 2018 a las 0:20


Definitivamente es más una prueba que un problema real. Sin embargo, si se nos permite hacer alguna suposición, se puede resolver en tiempo O(1). Para hacerlo, las restricciones a las que apunta la lista deben ser copiables. El algoritmo es el siguiente:

Tenemos una lista que se parece a: … -> Node(i-1) -> Node(i) -> Node(i+1) -> … y necesitamos eliminar Node(i).

  1. Copie los datos (no el puntero, los datos en sí) del Nodo (i+1) al Nodo (i), la lista se verá así: … -> Nodo (i-1) -> Nodo (i+1) -> Nodo(i+1) -> …
  2. Copie el SIGUIENTE del segundo Nodo (i+1) en una variable temporal.
  3. Ahora elimine el segundo nodo (i + 1), no requiere un puntero al nodo anterior.

Pseudocódigo:

void delete_node(Node* pNode)
{
    pNode->Data = pNode->Next->Data;  // Assume that SData::operator=(SData&) exists.
    Node* pTemp = pNode->Next->Next;
    delete(pNode->Next);
    pNode->Next = pTemp;
}

Miguel.

  • ¡Agradable! Nunca pensé en eso.

    –Charles Graham

    16 de septiembre de 2008 a las 4:23

  • ¿Qué sucede si desea eliminar el último nodo en la lista de enlaces?

    – Aman Jain

    22 de septiembre de 2010 a las 14:30

  • @Aman, la pregunta dice específicamente que es un medio nodo.

    – Vivin Paliat

    18 de enero de 2011 a las 16:42

  • La pregunta de @Aman es válida … Por lo tanto, esta función no funcionará en la eliminación del ÚLTIMO NODO. ¿Alguien tiene respuestas?

    – kumar

    23 de junio de 2012 a las 15:47

  • Buena solución, incorporada en mi blog – k2code.blogspot.in/2010/10/…. Gracias de nuevo.

    – Kinshuk4

    8 mayo 2014 a las 22:48


Supongamos una lista con la estructura

A -> B -> C -> D

Si solo tuviera un puntero a B y quisiera eliminarlo, podría hacer algo como

tempList = B->next;
*B = *tempList;
free(tempList);

La lista entonces se vería como

A -> B -> D

pero B mantendría el contenido anterior de C, eliminando efectivamente lo que había en B. Esto no funcionará si alguna otra pieza de código tiene un puntero a C. Tampoco funcionará si intenta eliminar el nodo D. Si desea realizar este tipo de operación, deberá crear la lista con un nodo de cola ficticio que no se use realmente para garantizar que ningún nodo útil tendrá un puntero siguiente NULL. Esto también funciona mejor para listas donde la cantidad de datos almacenados en un nodo es pequeña. Una estructura como

struct List { struct List *next; MyData *data; };

estaría bien, pero uno donde es

struct HeavyList { struct HeavyList *next; char data[8192]; };

sería un poco pesado.

  • +1: aparentemente no solo venciste a Mikhail en esta respuesta, sino que explicaste algunos de los peligros… raro, tienes el 10% de los votos de su respuesta…

    – Tony Delroy

    22 de marzo de 2011 a las 5:15

Imposible.

Hay trucos para imitar la eliminación.

Pero ninguno de ellos eliminará el nodo al que apunta el puntero.

La popular solución de borrar el siguiente nodo y copiando su contenido al real el nodo a eliminar tiene efectos secundarios si tiene punteros externos apuntando a los nodos en la lista, en cuyo caso un puntero externo que apunta al siguiente nodo quedará colgando.

Agradezco el ingenio de esta solución (borrar el siguiente nodo), pero no responde la pregunta del problema. Si esta es la solución real, la pregunta correcta debería ser “eliminar de la lista enlazada el VALOR contenido en un nodo en el que se da el puntero”. Pero, por supuesto, la pregunta correcta le da una pista sobre la solución. El problema tal como está formulado, pretende confundir a la persona (que de hecho me ha pasado a mí, sobre todo porque el entrevistador ni siquiera mencionó que el nudo está en el medio).

Un enfoque sería insertar un valor nulo para los datos. Cada vez que recorre la lista, realiza un seguimiento del nodo anterior. Si encuentra datos nulos, arregla la lista y pasa al siguiente nodo.

avatar de usuario
Sandeep Mathias

El mejor enfoque sigue siendo copiar los datos del siguiente nodo en el nodo que se eliminará, establecer el siguiente puntero del nodo en el siguiente puntero del siguiente nodo y eliminar el siguiente nodo.

Los problemas de los punteros externos que apuntan al nodo que se eliminará, si bien son ciertos, también se mantendrían para el siguiente nodo. Considere las siguientes listas enlazadas:

A->B->C->D->E->F y G->H->I->D->E->F

En caso de que tenga que eliminar el nodo C (en la primera lista vinculada), mediante el enfoque mencionado, eliminará el nodo D después de copiar el contenido al nodo C. Esto dará como resultado las siguientes listas:

A->B->D->E->F y G->H->I->puntero colgante.

En caso de que borre el NODO C por completo, las listas resultantes serán:

A->B->D->E->F y G->H->I->D->E->F.

Sin embargo, si va a eliminar el nodo D y utiliza el enfoque anterior, el problema de los punteros externos sigue ahí.

avatar de usuario
allan viento

La sugerencia inicial fue transformar:

a -> b -> c

para:

una ->, c

Si mantiene la información alrededor, digamos, un mapa desde la dirección del nodo hasta la dirección del siguiente nodo, entonces puede arreglar la cadena la próxima vez que recorra la lista. Si necesita eliminar varios elementos antes del próximo recorrido, debe realizar un seguimiento del orden de las eliminaciones (es decir, una lista de cambios).

La solución estándar es considerar otras estructuras de datos como una lista de omisión.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad