CODEWITHSUNDEEP
c++list
dean
dean

Reputation: 255

linked list debugging (delete C++ keyword is mysterious)?

I am trying to solve a problem: Delete a node from a singly linked list give only a pointer to that node. My approach is to overwrite the data of the next element in the list onto the current element of the list.

In the code below, I have two versions of the deleting code: deleteNode and deleteNode2.

void deleteNode(Node * x) {

while(x->next != NULL){
    x->data = x->next->data;
    x = x->next;
}

delete x;
x=NULL;

}

void deleteNode2(Node * x) {

while(x->next->next != NULL){
     x->data = x->next->data;
    x = x->next;
 }

 x->data = x->next->data;
delete x->next;
x->next=NULL;

}

I initialized the list with: 1,2,3,4,5 and tried to delete node 3. For deleteNode the output is: 1,2,4,5,0 while for deleteNode2: 1,2,4,5

Also when I remove the "x->next=NULL" line from deleteNode2 it has the same output with 1. My question is, how does the delete statement work in C++? Does it set all bits in the pointed to by the address to 0?

For deleteNode(..), the x pointer has been deleted but it is not appropriately been set to NULL because it prints 0 instead of skipping it. For deleteNode2, the statement "x->next=NULL" is equivalent to "x=NULL" in deleteNode since both pointers conceptually point to the same address, but they don't have the same effect?

The rest of the code is shown below: 

#include<iostream>
#include<stdlib.h>

using namespace std;

class Node {
public:
 int data;
Node * next;

Node ( int a ) { 
   data = a ; 
      next = NULL; 
    }

};

bool appendToTail ( Node * ptr, int a ){

  while (ptr->next != NULL)
  ptr = ptr->next;

  if (ptr==NULL) {
      return false; 
  }
 else {
    ptr->next = new Node(a);
 }

}

void printList (Node * head) {

 while (head!=NULL){

     cout<<head->data<<endl;
     head = head->next;

}

}

int main(void) {

Node * head;
head = new Node(1);
appendToTail(head,2);
 appendToTail(head,3);
appendToTail(head,4);
appendToTail(head,5);

Node * i = head->next->next;

printList(head);
cout<<"removed:"<<endl;

deleteNode2(i);

printList(head);    

return 0;

}

Upvotes: 0

Views: 366

Answers (2)

Vlad from Moscow
Vlad from Moscow

Reputation: 311078

The both functions are invalid.

In the first function you omitted statements that set correctly data member next of the current node.

That is the function has to look as

void deleteNode( Node *x ) 
{
    if ( x )
    {
        while ( x->next != NULL )
        {
            x->data = x->next->data;
            Node *tmp = x->next;
            x->next = x->next->next;
            x = tmp;
        }

        delete x;
    }
}

Nevertheless this function does not allow to remove the head of the list if it is the only element of the list.

The second function at least has undefined behaviour because x->next can be equal to NULL and as the result the condition in loop

while(x->next->next != NULL){

is invalid.

Upvotes: 0

PaulMcKenzie
PaulMcKenzie

Reputation: 35454

Your answer as to why x doesn't change can be demonstrated with a simpler program:

#include <iostream>

void foo(int x)
{
   x = 10;  // change it to 10
}

int main()
{
   int num = 4;
   foo(num);
   std::cout << num; // num is still 4!  Why?
}

So why is num still 4? Why didn't the value change to 10? Look up "pass-by-value", because that is what you're doing in your pointer code.

You should be either passing the pointer by reference, or a pointer to the pointer (if you need further explanation, fix the example above to make num equal to 10 on return to foo).

Upvotes: 2

Related Questions