it-swarm-es.tech

Eliminar un nodo intermedio de una única lista vinculada cuando el puntero al nodo anterior no está disponible

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

40
Nitin

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

Tenemos una lista similar a: ... -> Nodo (i-1) -> Nodo (i) -> Nodo (i + 1) -> ... y necesitamos eliminar el Nodo (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 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;
}

Micro.

87
Mikhail Tatarnikov

Asumamos 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 se vería así

A -> B -> D

pero B mantendría el contenido anterior de C, eliminando efectivamente lo que estaba en B. Esto no funcionará si alguna otra pieza de código mantiene un puntero a C. Tampoco funcionará si intentara 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 utiliza realmente, por lo que garantiza que ningún nodo útil tendrá un puntero NULL próximo. 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.

26
Ben Combee

Imposible.

Hay hacks para imitar la eliminación.

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

La solución popular de eliminar el nodo siguiente y copiar su contenido al nodo real que se 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.

11
codaddict

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 proporciona el puntero". Pero, por supuesto, la pregunta correcta le 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).

5
Alex B

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.

4
Joe Hildebrand

El mejor enfoque sigue siendo copiar los datos del siguiente nodo en el nodo que se va a 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 va a eliminar, si bien es cierto, también se mantendrían para el siguiente nodo. Considere las siguientes listas vinculadas:

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

En caso de que deba eliminar el nodo C (en la primera lista vinculada), según 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 elimine el NODE 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í.

4
Sandeep Mathias

La sugerencia inicial fue transformar:

a -> b -> c

a:

a ->, c

Si mantiene la información alrededor, digamos, un mapa de la dirección del nodo a la dirección del siguiente nodo, entonces puede arreglar la cadena la próxima vez para recorrer 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.

3
Allan Wind

Tal vez hacer una eliminación suave? (es decir, establezca un indicador de "borrado" en el nodo) Puede limpiar la lista más adelante si es necesario.

3
perimosocordiae

Dado

A -> B -> C -> D

y un puntero al, por ejemplo, el elemento B, lo eliminaría
1. liberar cualquier recuerdo perteneciente a miembros de B
2. copie el contenido de C en B (esto incluye su "siguiente" puntero)
3. eliminar todo el elemento C

Por supuesto, tendrá que tener cuidado con los casos de Edge, como trabajar en listas de un elemento.

Ahora, donde había B, tienes C y el almacenamiento que solía ser C está liberado.

1
DarenW

No si desea mantener la capacidad de navegación de la lista. Debe actualizar el nodo anterior para vincular al siguiente.

¿Cómo terminaste en esta situación, de todos modos? ¿Qué intentas hacer que te haga hacer esta pregunta?

1
Allen

Tendrás que avanzar por la lista para encontrar el nodo anterior. Eso hará que eliminar en general O (n ** 2). Si usted es el único código que realiza eliminaciones, puede hacerlo mejor en la práctica almacenando en caché el nodo anterior e iniciando su búsqueda allí, pero si esto ayuda depende del patrón de eliminaciones.

1
Kimbo
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;
   }
}
0
Aneesh

sí, pero no puedes desvincularlo. Si no te importa corromper la memoria, adelante ;-)

0
Steven A. Lowe

El siguiente código creará un LL, y 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 que se va a eliminar, sobre el nodo que se va a eliminar y luego se elimina el siguiente nodo del nodo que se va a eliminar. es decir

a B C D

copie c a b y c libre para que el resultado

a-c-d

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;
}
0

Sí, pero su lista se romperá después de eliminarla.

En este caso específico, recorra la lista nuevamente y obtenga ese puntero. En general, si hace esta pregunta, probablemente exista un error en lo que está haciendo.

0
owenmarshall
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;
   }
}
0
Aneesh

Para llegar al elemento de la lista anterior, deberá recorrer la lista desde el principio hasta que encuentre una entrada con un puntero next que apunte 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 a current->next luego elimine current.

editar: ¡Kimbo me ganó en menos de un minuto!

0
Eltariel

Podría hacer un enlace retrasado donde configura los nodos para que se eliminen de la lista con una bandera y luego eliminarlos en el siguiente recorrido correcto. Los nodos configurados para desvincularse necesitarían ser manejados adecuadamente por el código que rastrea la lista.

Supongo que también podría recorrer la lista nuevamente desde el principio hasta que encuentre lo que señala su elemento en la lista. Difícilmente óptimo, pero al menos una idea mucho mejor que la desvinculación retrasada.

En general, debe conocer el puntero al elemento del que acaba de llegar y debe pasarlo.

(Editar: Ick, con el tiempo que me llevó escribir una respuesta completa, tres millones de personas cubrieron casi todos los puntos que iba a mencionar. :()

0
DJ Capelis

La única forma sensata de hacer esto es recorrer la lista con un par de punteros hasta que el líder encuentre el nodo que se va a eliminar, luego actualice el siguiente campo utilizando el puntero final.

Si desea eliminar elementos aleatorios de una lista de manera eficiente, debe estar doblemente vinculado. Sin embargo, si desea tomar elementos del encabezado de la lista y agregarlos en la cola, no necesita vincular doblemente toda la lista. Simplemente vincule la lista pero haga que el siguiente campo del último elemento de la lista apunte al primer elemento de la lista. Luego, haga que la lista "cabeza" apunte al elemento de cola (no a la cabeza). Entonces es fácil agregar a la cola de la lista o eliminar de la cabeza.

0
Paul

Tienes el encabezado de la lista, ¿verdad? Solo lo atraviesas.

Digamos que su lista es señalada por "head" y el nodo para eliminarla "del".

Seudocódigo de estilo C (los puntos serían -> 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;
0
Charles Graham

Si tiene una lista vinculada 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, el nodo D en C y eliminar D. Pero no podemos eliminar el nodo como tal en el caso de una lista enlazada 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?

0
Smitha

Este es un fragmento de código que reuní que hace lo que pedía el OP, e incluso puede eliminar el último elemento de la lista (no de la manera más elegante, pero lo hace). Lo escribí 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);
}
0
Desyn8686