Hey!
We have to write a function that deletes nodes from a linked list. I was wondering if you could tell me if this is correct, and if not, how I could fix it?

void delNeg(node * L)
{
   node *cur = L;
   node *prev = NULL;

   while(cur != NULL)
   {
   if(cur->info < 0)
   { 
      prev = cur;
      cur = cur->link;
      delete prev;
   }
   else
  {
     prev=cur;
     cur=cur->link;
    }
    }
}

What happens when you test it? What happens when you do a paper run? There won't always be someone sitting around to tell you that your code is correct, so you need to learn how to verify such things through a methodical process.

void delNeg(node * L)
{
	node *cur = L;			// cur points to accepted pointer
	node *prev = NULL;		// prev points to NULL

	while(cur != NULL)		// while cur doesn't point to NULL
	{
		if(cur->info < 0)	// if the member (of the object on top of the current address) info is logically 'less than' 0
		{ 
			prev = cur;	// 	prev points to the address held by cur
			cur = cur->link;// 	cur points to the (next?) address held by its member cur->link
			delete prev;	// 	the object that sits on top of the address held by prev 
					// 	is destructed and the memory it held is returned to the OS
		}
		else			// if the member (of the object on top of the current address) info is logically 'greater than or equal' to 0
		{
			prev=cur;	//	prev points to the address held by cur
			cur=cur->link;	//	cur points to the (next?) address held by its member cur->link
		}
	}
}

That would be freeing memory held by the member a node had if its member has a logically less-than value.

You're halfway there. You do need a reference to the first Node of the entire list to get to other Nodes, however the way you are currently deleting will most likely pose some problems.

By literally deleting you are invalidating the Nodes. They are technically still 'referenceable' and therefore if you try to use the delNeg again you will most likely run into access violation exceptions because you may end up deleting memory again that doesn't belong to you.

If you don't want this to happen, you need to also negate the linkage between the nodes that you want to remain and the nodes that you want to continue to exist. You can do so by, making the previous node of the node you want to delete point to the next node of the node you want to delete.

In example, assume A -> B -> C is a linkedlist with 3 nodes. In order to delete B we have to find B in the list. In addition, we need to make the previous Node of B point to the next node of B so A will point to C.

A-> C // desired result

In order to do this you need to store the previous node of the node to be deleted, the node to be deleted and the next node of the node to be deleted and when the time comes, negate the linkage of A to B and B to C by making A point to C. The fact that B points to C doesn't matter - B just holds a reference to C. So long as B doesn't delete its next Link, you can safely delete the reference to the node B after you have linked A to C.

-Alex

This article has been dead for over six months. Start a new discussion instead.