how to delete current linked list node without tracking previous node

0
votes

I was wondering if it's possible to delete a node by value in a linked list in C++ without tracking both 'previous' and 'current' nodes.

What I did is copy next node's information into current node, link current node to next next node, and delete next node.

I've attempted something like below. However, this only works if the node to delete is not the last node. I'm unable to figure out how to accommodate for the last node.

struct Node
{
    int data;
    Node* next;
};

void LinkedList::deleteNode(int item)
{
    Node* tmpNode = m_head;

    while (tmpNode != nullptr)
    {
        if (tmpNode->data == item)
        {
            if (tmpNode->next != nullptr) // not last node
            {
                // this works
                Node* delNode = tmpNode->next;
                tmpNode->data = tmpNode->next->data;
                tmpNode->next = tmpNode->next->next;
                delete delNode;
            }
            else // last node
            {
                // this does not work
                delete tmpNode;
                tmpNode = nullptr;
            }
            std::cout << "deleted item " << item << '\n';
            return;
        }
        tmpNode = tmpNode->next;
    }
    std::cout << "delete failed: item " << item << " not found\n";
}
2
c++linked-list
If you delete the actual node, it will work and be more efficient. The trick, keep track of the previous node you visited in the loop. Set its next to the current node's next and delete the node. Special cases will be if it is the first or last node, but that can be handles with a couple of extra lines. - lakeweb
lakeweb is correct. The reason your code isn't quite what you want is because you're actually deleting the next node after you copied it's data into the current node. If it's the last node, then there is no next node to delete. You can't delete the current node without a reference to the previous node. - jhufford

2 Answers

1
votes

When you delete a node, you have to set the next of the previous node to nullptr. Otherwise, it will stay pointing to a deleted node.

Suggestion:

At the beginning of the function, create:

Node* previousTmpNode = nullptr;

Store the address of the previous node when you scan the linked list:

Node* previousTmpNode = tmpNode ; //call right before tmpNode = tmpNode->next;

And then call:

previousTmpNode->next = nullptr; //call right after you deleted the last element.

Or, change your nodes so they point backwards (double linked-list).

0
votes

As this is probably an exercise/home-work, I'll answer in a sudo(untested) manor. And it will just work for the last node.

Node* prev = nullptr;
for(auto track = m_head; track; track = track->next){
   if(track->data != item)
      continue;
   if(!prev){
      m_head = track->next;
      delete track;
      break;
   }
   prev->next = track->next;
   delete track;
   break;
}