Head not linked correctly in linked list

Question

When i display after removing a element from linked list, 0 is displayed in place of removed element. I am having trouble updating the nodes.Can anyone Please explain what is happening? Why 0 is displayed?

#include<iostream>
#include<stdlib.h>
using namespace std;

    class node {

    public:
      int data;
      node *link;

    };

    class linkedlist {

        node *head;

    public:

        linkedlist() {
            head=NULL;
        }

        int add(int data1) {

            node *insertnode=new node;
            insertnode->data=data1;
            insertnode->link=NULL;

            node *temp=head;

            if(temp!=NULL)
            {
                while(temp->link!=NULL)
                {
                    temp=temp->link;
                }
                temp->link=insertnode;

            }
            else{head=insertnode;}

        }

        void disp()
        {
            node *temp1=head;
            cout<<endl;
            if(temp1==NULL)
            {
                cout<<"Empty"<<endl;
            }

            if(temp1->link==NULL)
            {
                cout<<temp1->data<<endl;

            }
            else {

                do {
                    cout<<temp1->data<<endl;
                    temp1=temp1->link;
                } while(temp1!=NULL);

            }

        }

        int remove(int removedata)
        {
            node *previous;
            node *temp2=head;
            if(temp2==NULL)
                {exit(0);}

            if(temp2->link==NULL)
            {
                delete temp2;
                head=NULL;
            }

            else
            {

                while(temp2!=NULL)
                {

                    if(temp2->data==removedata)
                    {
                        previous=temp2;
                        delete temp2;
                    }

                    temp2=temp2->link;

                }

            }

        }

    };

    int main()
    {

        linkedlist list;
        list.add(10);
        list.add(100);
        list.add(200);
        list.remove(10);
        list.disp();

    }

The output displayed is:

0
100
200

Answer 1

You have deleted the head node, but nothing in your code ever reassigns the head node if this happens.

So what you have here is undefined behaviour.

You also do this:

if(temp2->data==removedata)
{
    previous=temp2;
    delete temp2;
}
temp2=temp2->link;

In other words, you delete something, then dereference it. I'm not sure what previous is supposed to do here, but it also now contains a pointer to something that has been deleted. Fortunately it seems to be the only place it is ever reference (what was the intention here?)

And your function doesn't seem to return anything, but it is declared as returning an int.

So I think the logic is all wrong here.

What you need to do is:

• If your node is the head node, point the head node at your to-be-deleted node's next node.
• Otherwise, find the previous node (the node where the to-be-deleted node is next), and update that node to point at your to-be-deleted node's next node.
• Delete the node, now that nothing references it.

Something like this (untested):

if(head == NULL) return; // List is empty.

node *prev = head;
if(prev->data == removedata)
{
    head = prev->link;
    delete prev;
    return; // removed the head node
}
while(prev->link)
{
    if(prev->link->data == removedata)
    {
        node *t = prev->link;
        prev->link = t->link;
        delete t;
        return; // removed a non-head node
    }
    prev = prev->link;
}
// data is not in the list

Or if you want to try to be clever and eliminate special cases:

node **prevptr = &head;
node *cur = head;
while(cur)
{
    if(cur->data == removedata)
    {
        *prevptr = cur->link;
        delete cur;
        break;
    }
    prevptr = &cur->link;
    cur = cur->link;
}

Answer 2

Might I suggest my code?

int removeData(int target)
{
  //Let's return -1 if we can't find the target element.
  node *p,*q;
  for(q=head;q!=NULL && q->data!=target;p=q,q=q->link)
     ;
  if(q==NULL)
  {
    //Either the list was empty or the target element was not on the list
    return -1;
  }
  else
  {
    //We found the element, let's delete it.
    int ret=q->data;
    if(q==head)//If target node is the first node in list
      head=q->link;
    else
      p->link=q->link;
    delete q;//We delete the node pointed to by q here, which is our target node
    return ret;  
  }  
}  

Let me explain the above code.First we have two temporary pointers, that will point to the previous node(p), and the current node(q) while we are traversing the linked list.We will traverse the list as long as the list is not over or as long as the current node is not our target node. When we exit the for loop, we could have exited on two reasons. Either q had become NULL, which could have two meanings, either our list was empty, or our list din't have the target node.So we return -1, reporting the problem. Or q->data was equal to target, which means we have found our target node, let's delete it.We store the current value and delete the node.It is customary to return the deleted node's data.Hope this helps.

Answer 3

This is closely related to this answer to your previous question.

Let's format this function and take a closer look.

int remove(int removedata)
{
    node* previous;     // Why is this unintialised?
    node* temp2 = head; // Can you think of a more meaningful name for this
                        // variable? Perhaps "current"?
    if (temp2 == NULL)
    {
        exit(0); // Do you really want to exit the program if you try to
                 // remove an item from an empty list? Is there a better way
                 // to handle this?
    }

    if(temp2->link == NULL) // What is so special about a linked list with one element?
    {
        delete temp2; // You've not checked to see if this element is
                      // `removedata`
        head = NULL;  // So calling this function for any list with one element
                      // results in an empty list. This is probably
                      // undesirable
    }
    else
    {
        while (temp2 != NULL) // Consider using a for-loop for iteration. It
                              // couples the increment(s) with the
                              // terminating condition.
        {
            if (temp2->data == removedata) // At this point we have found
                                           // our candidate for removal
            {
                previous = temp2; // This is not the "previous" node, but
                                  // the "current" one. And this variable is
                                  // never used. You do need to know where
                                  // the previous node is and whether it is
                                  // 'head' to update either the 'link' or
                                  // 'head'

                delete temp2;     // This does remove the correct node but
                                  // leaves the previous 'link' pointer
                                  // dangling and any subsequent nodes are
                                  // orphaned.
            }
            temp2 = temp2->link; // See comment above about for-loops.
        }
    }
} // This function is declared `int` but has no return statement.

An alternative implementation may look something like this (untested):

void remove(int removedata)
{
    for (node* current = head, * previous = NULL;
        current;
        previous = current, current = current->link)
    {
        if (current->data == removedata)
        {
            if (previous)
            {
                previous->link = current->link;
            }
            else
            {
                head = current->link;
            }
            delete current;
            break;
        }
    }
}