¿Es posible eliminar un nodo intermedio en la lista enlazada solo cuando la única información disponible que tenemos es el puntero al nodo que desea eliminar y no el puntero al nodo anterior? Después de la eliminación, el nodo anterior debe apuntar al nodo al lado del nodo eliminado.Eliminación de un nodo intermedio de una sola lista enlazada al puntero al nodo anterior no está disponible
Sí, pero no puede desvincularlo. Si no se preocupan por la memoria corrupta, adelante ;-)
No si desea mantener la traversability de la lista. Necesita actualizar el nodo anterior para vincularlo al siguiente.
¿Cómo terminaste en esta situación, de todos modos? ¿Qué estás tratando de hacer que te hace esta pregunta?
Sí, pero su lista se romperá después de eliminarla.
En este caso específico, recorrer la lista de nuevo y conseguir que el puntero! En general, si hace esta pregunta, probablemente exista un error en lo que está haciendo.
Alguien me hizo esta pregunta en una entrevista. – Nitin
La sugerencia inicial era transformar:
a -> b -> c
a:
a ->, c
Si se mantiene la información en torno a, digamos, un mapa de la dirección del nodo a la dirección del siguiente nodo, luego puede arreglar la cadena la próxima vez para recorrer la lista. Si necesita eliminar varios elementos antes del siguiente 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 salto.
Tendrá que desplazarse hacia abajo para encontrar el nodo anterior. Eso hará que borrar en general O (n ** 2). Si es el único código que realiza eliminaciones, puede hacerlo mejor en la práctica almacenando en caché el nodo anterior y comenzando su búsqueda allí, pero si esto ayuda depende del patrón de eliminaciones.
Al desplazarse hacia abajo en la lista todavía se muestra O (n) para eliminar un elemento. –
De hecho. Me refería a eliminar toda la lista (al azar). – Kimbo
Para ir al elemento de la lista anterior, deberá recorrer la lista desde el principio hasta que encuentre una entrada con un puntero next que apunta a su elemento actual. Luego, tendría un puntero a cada uno de los elementos que tendría que modificar para eliminar el elemento actual de la lista: simplemente configure previous->next en current->next y luego elimine current.
edición: Kimbo se me adelantó en menos de un minuto!
Quizás haga una eliminación suave? (es decir, establezca un indicador "eliminado" en el nodo) Puede limpiar la lista más adelante si lo necesita.
Un problema, sin embargo, es que mantener esa bandera aumentará la memoria de cada elemento. – Arafangion
Un enfoque sería insertar un nulo para los datos. Cada vez que recorre la lista, realiza un seguimiento del nodo anterior. Si encuentra datos nulos, arregle la lista y vaya al siguiente nodo.
Usted podría hacer desconexión retardada donde se configuran los nodos a ser desvinculado de la lista con una bandera y eliminarlos en el siguiente recorrido adecuado. Los nodos configurados para desvincularse deben ser manejados correctamente por el código que rastrea la lista.
supongo que también podría simplemente recorrer la lista de nuevo desde el principio hasta que encuentre lo que apunta a su elemento de la lista. Difícilmente óptimo, pero al menos una idea mucho mejor que la desvinculación retrasada.
En general, usted debe saber el puntero sobre el objeto que acaba de llegar y que debe estar pasando esa situación.
(Edit:. Ick, con el tiempo que me llevó a escribir a máquina una respuesta fullish tres personas tropecientos cubiertos casi todos los puntos que iba a mencionar :()
La única manera sensata de hacer esto es para recorrer la lista con un par de punteros hasta que el líder encuentre el nodo que se eliminará, luego actualice el siguiente campo usando el puntero final.
Si desea eliminar elementos aleatorios de una lista de manera eficiente, debe ser doblemente enlazada. Si usted quiere tomar los objetos de la cabeza de la lista y añadirlos a la cola, sin embargo, no es necesario para enlazar doblemente toda la lista. Individualmente vincular la lista, pero hacen que el siguiente campo del último elemento de la lista punto a el primer elemento en la lista. Luego, haga que la lista "cabeza" apunte al artículo de cola (no a la cabeza). Luego es fácil agregarlo a la cola de la lista o quitarlo de la cabeza.
Vamos a suponer una lista con la estructura
A -> B -> C -> D
Si sólo tuviera un puntero a B y quería eliminarlo, usted podría hacer algo como
tempList = B->next;
*B = *tempList;
free(tempList);
La lista sería parecido a
A -> B -> D
B, pero mantendría los contenidos previos C, eliminando efectivamente lo fue en B. Esto no funcionará si alguna otra pieza de código es la celebración de un puntero a C. También no funcionará si estuviera tratando de eliminar el nodo D Si desea realizar este tipo de operación, deberá compilar la lista con un nodo ficticio de cola que no se utiliza realmente, por lo que se garantiza que ningún nodo útil tendrá un próximo NULL puntero. 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 onerosa.
+1: no solo aparentemente ganaste a Mikhail con esta respuesta, sino que también has explicado algunos de los peligros ... extraño, tienes el 10% de los votos de su respuesta ... –
Usted tiene la cabeza de la lista, ¿verdad? Usted acaba de atravesarlo.
Digamos que su lista es apuntado por "cabeza" y el nodo para eliminarlo "del".
estilo pseudo-código C (puntos sería -> en C):
prev = head
next = prev.link
while(next != null)
{
if(next == del)
{
prev.link = next.link;
free(del);
del = null;
return 0;
}
prev = next;
next = next.link;
}
return 1;
Es definitivamente más una prueba más que un problema real. Sin embargo, si se nos permite hacer alguna suposición, se puede resolver en O (1) vez. Para hacerlo, las restricciones a las que apunta la lista deben ser copiables. El algoritmo es el siguiente:
Tenemos una lista parecida a: ... -> Nodo (i-1) -> Nodo (i) -> Nodo (i + 1) -> ... y nosotros necesidad de eliminar el nodo (i).
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;
}
Mike.
¡Agradable! Nunca pensé en eso. –
¿Qué sucede si desea eliminar el último nodo en la lista de enlaces? –
@Aman la pregunta dice específicamente que es un nodo * medio *. –
Dada
A -> B -> C -> D
y un puntero a, por ejemplo, punto B, que sería borrarlo vía
1. libre de cualquier memoria que pertenece a los miembros de B
2. copia el contenido de C en B (esto incluye su puntero "siguiente")
3. eliminar todo el elemento C
Por supuesto, usted tiene que tener cuidado con casos extremos, tales como trabajar en listas de un artículo.
Ahora donde había B, tiene C y el almacenamiento que solía ser C se libera.
El siguiente código creará un LL, n luego le pedirá al usuario que dé el puntero al nodo que se eliminará. imprimirá la lista después de la eliminación Hace lo mismo que se hace copiando el nodo después del nodo a eliminar, sobre el nodo a eliminar y luego elimina el siguiente nodo del nodo que se eliminará. es decir
ABCD
copia C a B y C libre para que resultado es
ACD
struct node
{
int data;
struct node *link;
};
void populate(struct node **,int);
void delete(struct node **);
void printlist(struct node **);
void populate(struct node **n,int num)
{
struct node *temp,*t;
if(*n==NULL)
{
t=*n;
t=malloc(sizeof(struct node));
t->data=num;
t->link=NULL;
*n=t;
}
else
{
t=*n;
temp=malloc(sizeof(struct node));
while(t->link!=NULL)
t=t->link;
temp->data=num;
temp->link=NULL;
t->link=temp;
}
}
void printlist(struct node **n)
{
struct node *t;
t=*n;
if(t==NULL)
printf("\nEmpty list");
while(t!=NULL)
{
printf("\n%d",t->data);
printf("\t%u address=",t);
t=t->link;
}
}
void delete(struct node **n)
{
struct node *temp,*t;
temp=*n;
temp->data=temp->link->data;
t=temp->link;
temp->link=temp->link->link;
free(t);
}
int main()
{
struct node *ty,*todelete;
ty=NULL;
populate(&ty,1);
populate(&ty,2);
populate(&ty,13);
populate(&ty,14);
populate(&ty,12);
populate(&ty,19);
printf("\nlist b4 delete\n");
printlist(&ty);
printf("\nEnter node pointer to delete the node====");
scanf("%u",&todelete);
delete(&todelete);
printf("\nlist after delete\n");
printlist(&ty);
return 0;
}
Sangra tu código con cuatro espacios para que se formatee correctamente. –
void delself(list *list)
{
/*if we got a pointer to itself how to remove it...*/
int n;
printf("Enter the num:");
scanf("%d",&n);
while(list->next!=NULL)
{
if(list->number==n) /*now pointer in node itself*/
{
list->number=list->next->number;
/*copy all(name,rollnum,mark..) data of next to current, disconect its next*/
list->next=list->next->next;
}
list=list->next;
}
}
void delself(list *list)
{
/*if we got a pointer to itself how to remove it...*/
int n;
printf("Enter the num:");
scanf("%d",&n);
while(list->next!=NULL)
{
if(list->number==n) /*now pointer in node itself*/
{
list->number=list->next->number; /*copy all(name,rollnum,mark..)
data of next to current, disconnect its next*/
list->next=list->next->next;
}
list=list->next;
}
}
Si usted tiene una lista enlazada A -> B -> C -> D y un puntero al nodo B. Si tiene que eliminar este nodo, puede copiar el contenido del nodo C en B, nodo D en C y eliminar D. Pero no podemos eliminar el nodo como tal en el caso de una lista vinculada individualmente, ya que si lo hacemos, el nodo A también se perderá. Aunque podemos retroceder a A en caso de una lista doblemente vinculada.
¿Estoy en lo cierto?
Yo diría Copiar la siguiente parte de NODE B en temp. Luego copie todo el contenido de NODE C en NODO B. Borre NODE C usando la dirección en temp temporal. – codingfreak
No es posible.
Hay hacks para imitar la eliminación.
Pero nada de eso eliminará realmente el nodo al que apunta el puntero.
a eliminar la solución popular de la supresión de la siguiente nodo y copiar su contenido al nodo realtiene efectos secundarios si tiene punteros externos que apuntan a los nodos de la lista, en cuyo caso una externa el puntero que apunta al siguiente nodo se pondrá colgando.
Aprecio el ingenio de esta solución (eliminar 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 vinculada el VALOR contenido en un nodo en el que se asigna el puntero". Pero, por supuesto, la pregunta correcta te da una pista sobre la solución. El problema tal como está formulado tiene la intención de confundir a la persona (lo que de hecho me ha sucedido, especialmente porque el entrevistador ni siquiera mencionó que el nodo está en el medio).
Si me preguntas, un nodo en una lista vinculada se identifica por sus datos y su posición en la lista y no por su ubicación en la memoria, así que creo que las 2 respuestas mejor votadas son una solución perfecta – Neowizard
El mejor enfoque es copiar los datos del siguiente nodo en el nodo que se va a eliminar, establecer el siguiente puntero del nodo al siguiente puntero del siguiente nodo y eliminar el siguiente nodo.
Los problemas de los punteros externos que apuntan al nodo que se eliminará, aunque son verdaderos, también se mantendrán para el siguiente nodo. Tenga en cuenta las siguientes listas enlazadas:
A-> B-> C-> D> E> F y G> H> I> D> E> F
En caso de que tiene 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 suprimir 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í.
Void deleteMidddle(Node* head)
{
Node* slow_ptr = head;
Node* fast_ptr = head;
Node* tmp = head;
while(slow_ptr->next != NULL && fast_ptr->next != NULL)
{
tmp = slow_ptr;
slow_ptr = slow_ptr->next;
fast_ptr = fast_ptr->next->next;
}
tmp->next = slow_ptr->next;
free(slow_ptr);
enter code here
}
solución totalmente diferente. Pidió eliminar un número en el medio, no necesariamente el elemento medio. :-) – Trying
Esta es una pieza de código que puse juntos que hace lo que el PO estaba pidiendo, e incluso puede eliminar el último elemento de la lista (no de la manera más elegante, pero se las trae). Lo escribió mientras aprendía a usar listas enlazadas. Espero eso ayude.
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <string>
using namespace std;
struct node
{
int nodeID;
node *next;
};
void printList(node* p_nodeList, int removeID);
void removeNode(node* p_nodeList, int nodeID);
void removeLastNode(node* p_nodeList, int nodeID ,node* p_lastNode);
node* addNewNode(node* p_nodeList, int id)
{
node* p_node = new node;
p_node->nodeID = id;
p_node->next = p_nodeList;
return p_node;
}
int main()
{
node* p_nodeList = NULL;
int nodeID = 1;
int removeID;
int listLength;
cout << "Pick a list length: ";
cin >> listLength;
for (int i = 0; i < listLength; i++)
{
p_nodeList = addNewNode(p_nodeList, nodeID);
nodeID++;
}
cout << "Pick a node from 1 to " << listLength << " to remove: ";
cin >> removeID;
while (removeID <= 0 || removeID > listLength)
{
if (removeID == 0)
{
return 0;
}
cout << "Please pick a number from 1 to " << listLength << ": ";
cin >> removeID;
}
removeNode(p_nodeList, removeID);
printList(p_nodeList, removeID);
}
void printList(node* p_nodeList, int removeID)
{
node* p_currentNode = p_nodeList;
if (p_currentNode != NULL)
{
p_currentNode = p_currentNode->next;
printList(p_currentNode, removeID);
if (removeID != 1)
{
if (p_nodeList->nodeID != 1)
{
cout << ", ";
}
cout << p_nodeList->nodeID;
}
else
{
if (p_nodeList->nodeID !=2)
{
cout << ", ";
}
cout << p_nodeList->nodeID;
}
}
}
void removeNode(node* p_nodeList, int nodeID)
{
node* p_currentNode = p_nodeList;
if (p_currentNode->nodeID == nodeID)
{
if(p_currentNode->next != NULL)
{
p_currentNode->nodeID = p_currentNode->next->nodeID;
node* p_temp = p_currentNode->next->next;
delete(p_currentNode->next);
p_currentNode->next = p_temp;
}
else
{
delete(p_currentNode);
}
}
else if(p_currentNode->next->next == NULL)
{
removeLastNode(p_currentNode->next, nodeID, p_currentNode);
}
else
{
removeNode(p_currentNode->next, nodeID);
}
}
void removeLastNode(node* p_nodeList, int nodeID ,node* p_lastNode)
{
node* p_currentNode = p_nodeList;
p_lastNode->next = NULL;
delete (p_currentNode);
}
básicamente está asignando un nodo hasta el final. –
¿Qué es eso? Me parece una buena pregunta. –
Esta es una pregunta de entrevista clásica. – Motti
Una respuesta muy clara [aquí] (https://stackoverflow.com/a/13739444/465053) en un hilo relacionado. – RBT