it-swarm-pt.tech

Excluindo um nó do meio de uma única lista vinculada quando o ponteiro para o nó anterior não está disponível

É possível excluir um nó do meio na lista vinculada única quando a única informação disponível que temos é o ponteiro para o nó a ser excluído e não o ponteiro para o nó anterior? Após a exclusão, o nó anterior deve apontar para o nó próximo a nó excluído.

40
Nitin

Definitivamente, é mais um questionário do que um problema real. No entanto, se for permitido fazer alguma suposição, ela poderá ser resolvida em O(1) tempo. Para isso, as restrições que a lista aponta devem ser copiáveis. O algoritmo é o Segue:

Temos uma lista parecida com: ... -> Nó (i-1) -> Nó (i) -> Nó (i + 1) -> ... e precisamos excluir o Nó (i).

  1. Copie os dados (não ponteiro, os próprios dados) do Nó (i + 1) para o Nó (i), a lista terá a seguinte aparência: ... -> Nó (i-1) -> Nó (i + 1) -> Nó (i + 1) -> ...
  2. Copie o NEXT do segundo nó (i + 1) em uma variável temporária.
  3. Agora exclua o segundo nó (i + 1), ele não requer ponteiro para o nó anterior.

Pseudo-có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.

87
Mikhail Tatarnikov

Vamos assumir uma lista com a estrutura

A -> B -> C -> D

Se você tivesse apenas um ponteiro para B e quisesse excluí-lo, poderia fazer algo como

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

A lista ficaria assim

A -> B -> D

mas B conteria o conteúdo antigo de C, excluindo efetivamente o que estava em B. Isso não funcionará se algum outro pedaço de código estiver segurando um ponteiro em C. Também não funcionará se você estiver tentando excluir o nó D. Se você deseja fazer esse tipo de operação, precisará criar a lista com um nó de cauda fictício que não é realmente usado para garantir que nenhum nó útil tenha um ponteiro NULL seguinte. Isso também funciona melhor para listas em que a quantidade de dados armazenados em um nó é pequena. Uma estrutura como

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

seria bom, mas um onde é

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

seria um pouco pesado.

26
Ben Combee

Não é possivel.

Existem hacks para imitar a exclusão.

Mas nada disso realmente excluirá o nó para o qual o ponteiro está apontando.

A solução popular de excluir o nó a seguir e copiar seu conteúdo para o nó real a ser excluído tem efeitos colaterais se você tiver apontador ponteiros externos para nós na lista; nesse caso, um ponteiro externo apontando para o seguinte nó ficará pendente.

11
codaddict

Agradeço a engenhosidade desta solução (excluindo o próximo nó), mas ela não responde à pergunta do problema. Se esta for a solução real, a pergunta correta deve ser "excluir da lista vinculada o VALUE contido em um nó no qual o ponteiro é fornecido". Mas, é claro, a pergunta correta fornece uma dica sobre a solução. O problema, conforme formulado, pretende confundir a pessoa (o que de fato aconteceu comigo, principalmente porque o entrevistador nem sequer mencionou que o nó está no meio).

5
Alex B

Uma abordagem seria inserir um nulo para os dados. Sempre que você percorre a lista, monitora o nó anterior. Se você encontrar dados nulos, conserte a lista e vá para o próximo nó.

4
Joe Hildebrand

A melhor abordagem ainda é copiar os dados do próximo nó no nó a ser excluído, definir o próximo ponteiro do nó no próximo ponteiro do nó seguinte e excluir o próximo nó.

Os problemas de ponteiros externos que apontam para o nó a ser excluído, enquanto verdadeiros, também se mantêm no próximo nó. Considere as seguintes listas vinculadas:

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

Caso seja necessário excluir o nó C (na primeira lista vinculada), pela abordagem mencionada, você excluirá o nó D após copiar o conteúdo para o nó C. Isso resultará nas seguintes listas:

A-> B-> D-> E-> F e G-> H-> I-> ponteiro oscilante.

Caso você exclua o NODE C completamente, as listas resultantes serão:

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

No entanto, se você deseja excluir o nó D e usar a abordagem anterior, o problema de ponteiros externos ainda está lá.

4
Sandeep Mathias

A sugestão inicial foi transformar:

a -> b -> c

para:

a ->, c

Se você mantiver as informações, digamos, um mapa de endereço do nó para o endereço do próximo nó, poderá corrigir a cadeia na próxima vez para percorrer a lista. Se for necessário excluir vários itens antes da próxima travessia, você precisará acompanhar a ordem das exclusões (ou seja, uma lista de alterações).

A solução padrão é considerar outras estruturas de dados, como uma lista de pulos.

3
Allan Wind

Talvez faça uma exclusão suave? (ou seja, defina um sinalizador "excluído" no nó) Você pode limpar a lista mais tarde, se precisar.

3
perimosocordiae

Dado

A -> B -> C -> D

e um ponteiro para, digamos, o item B, você o excluiria
1. libera qualquer memória pertencente a membros de B
2. copie o conteúdo de C para B (isso inclui o ponteiro "próximo")
3. excluir o item inteiro C

Obviamente, você precisará ter cuidado com os casos do Edge, como trabalhar em listas de um item.

Agora, onde havia B, você tem C e o armazenamento que costumava ser C é liberado.

1
DarenW

Não se você deseja manter a capacidade de travessia da lista. Você precisa atualizar o nó anterior para vincular ao próximo.

Como você acabou nessa situação, afinal? O que você está tentando fazer para fazer essa pergunta?

1
Allen

Você precisará marchar a lista para encontrar o nó anterior. Isso fará a exclusão em geral O (n ** 2). Se você é o único código que faz exclusões, você pode fazer melhor na prática armazenando em cache o nó anterior e iniciando sua pesquisa lá, mas se isso ajuda depende do padrão de exclusões.

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

sim, mas você não pode desvincular. Se você não se importa com a corrupção de memória, vá em frente ;-)

0
Steven A. Lowe

O código a seguir criará um LL, n e solicitará que o usuário forneça o ponteiro para o nó a ser excluído. ele imprimirá a lista após a exclusão. Faz o mesmo que é feito, copiando o nó após o nó a ser excluído, sobre o nó a ser excluído e, em seguida, exclui o próximo nó do nó a ser excluído. isto é

a-b-c-d

copie c para be liberte c para que o resultado seja

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
Sagar Verma - The One

Sim, mas sua lista será quebrada depois que você a remover.

Nesse caso específico, percorra a lista novamente e pegue o ponteiro! Em geral, se você está fazendo esta pergunta, provavelmente existe um erro no que você está fazendo.

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 chegar ao item anterior da lista, você precisaria percorrer a lista desde o início até encontrar uma entrada com um ponteiro next que aponte para o item atual. Em seguida, você terá um ponteiro para cada um dos itens que precisará modificar para remover o item atual da lista - basta definir previous->next para current->next e exclua current.

editar: Kimbo me venceu por menos de um minuto!

0
Eltariel

Você pode fazer um atraso na ligação ao definir os nós a serem desviados da lista com um sinalizador e excluí-los no próximo percurso adequado. Os nós definidos como desvinculados precisariam ser tratados adequadamente pelo código que rastreia a lista.

Suponho que você também possa percorrer a lista novamente desde o início até encontrar o que aponta para o seu item na lista. Dificilmente ideal, mas pelo menos uma ideia muito melhor do que atrasar a ligação.

Em geral, você deve saber o ponteiro para o item de onde veio e deve passar o item por aí.

(Edit: Ick, com o tempo que levei para digitar uma resposta completa, três gazilhões de pessoas cobriram quase todos os pontos que eu ia mencionar. :()

0
DJ Capelis

A única maneira sensata de fazer isso é percorrer a lista com alguns ponteiros até que o primeiro encontre o nó a ser excluído e atualize o próximo campo usando o ponteiro à direita.

Se você deseja excluir itens aleatórios de uma lista com eficiência, ele precisa estar duplamente vinculado. Se você deseja pegar itens do cabeçalho da lista e adicioná-los no final, no entanto, não é necessário vincular duplamente a lista inteira. Vincule a lista individualmente, mas faça com que o próximo campo do último item da lista aponte para o primeiro item da lista. Em seguida, faça a lista "cabeça" apontar para o item da cauda (não a cabeça). É fácil adicionar ao final da lista ou remover da cabeça.

0
Paul

Você tem o chefe da lista, certo? Você acabou de atravessá-lo.

Digamos que sua lista seja apontada por "head" e pelo nó para excluí-la "del".

Pseudocódigo do estilo C (os pontos seriam -> em 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

Se você tiver uma lista vinculada A -> B -> C -> D e um ponteiro para o nó B. Se você precisar excluir este nó, poderá copiar o conteúdo do nó C para B, nó D para C e excluir D. Mas não podemos excluir o nó como tal no caso de uma lista vinculada individualmente, pois, se o fizermos, o nó A também será perdido. Embora possamos voltar para A em caso de lista duplamente vinculada.

Estou certo?

0
Smitha

Esse é um pedaço de código que eu montei que faz o que o OP estava pedindo e pode até excluir o último elemento da lista (não da maneira mais elegante, mas é feito). Escreveu enquanto aprendia a usar listas vinculadas. Espero que ajude.

#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