Sign in to follow this  
Uther Mortigast

(C++) Linked List Node Deletion Woes -- Solved

Recommended Posts

Compiler: Dev-C++ 4.9.9.2 OS: Win XP w/service pack 3 Application: Console based Programmer: < 6 mos experience I have been perplexed by a problem for days. The jDeleteAfter member function of my linked list class should delete the node object after the node provided as an argument. I do not know if it is even doing that, but it is causing my application to close abruptly when it executes. I've narrowed the offending line of code down to "delete tlp;", but I suspect I have a logical error elsewhere that is the root of my problem. Any ideas?
#include "JawaListT.h"
#include <cstdlib>
#include <iostream>
#include <new.h>

/*DEFAULT CONSTRUCTOR*/
JawaListT::JawaListT()
{
	if((this->jHead = new (nothrow) JawaLinkT) && (this->jTail = new (nothrow) JawaLinkT))
	{
		this->jHead->jSetNext(this->jTail);
		this->jTail->jSetNext(this->jTail);
	}//end if allocated
}

/*INSERT NODE AFTER*/
void JawaListT::jInsertAfter(JawaLinkT* lp, int val)
{
	if(lp != this->jTail && lp != NULL)             //if passed not tail and not null
	{
		JawaLinkT* tlp;				//new list node
									
		if((tlp = new (nothrow) JawaLinkT) != NULL)//if dynamically allocated	
		{
			tlp->jSetNext(lp->jGetNext());  //temp.next = passed.next					
			lp->jSetNext(tlp);		//passed.next = temp
			tlp->jSetValue(val);		//temp.data = val
		}//end if allocated
	}//end if not tail
}

/*INSERT NODE BEFORE*/
void JawaListT::jInsertBefore(JawaLinkT* lp, int val)
{
	if(lp != this->jHead && lp != NULL)		//if passed not head and not null
	{
		JawaLinkT* tlp;				//new list node

		if((tlp = new (nothrow) JawaLinkT) != NULL)  //if dynamically allocated
		{
			*tlp = *lp;							//copies passed node to temp node
			lp->jSetNext(tlp);		//passed.next = temp
			lp->jSetValue(val);		//passed.data = val
			if(lp == this->jTail)		//if passed is tail
			{
				this->jTail = tlp;	//tail is temp
				this->jTail->jSetNext(this->jTail);  //tail.next = tail
			}//end if lp
		}//end if tlp
	}//end if head
}

/*REMOVE NODE AFTER*/
void JawaListT::jDeleteAfter(JawaLinkT* lp)
{
	if(lp->jGetNext() != this->jTail && lp != NULL)	//if not tail and not null
	{
		JawaLinkT* tlp;				//temp pointer to node

		tlp = lp->jGetNext();			//temp = passed.next
		lp->jSetNext(tlp->jGetNext());		//passed.next = temp.next
		delete tlp;				//delete to what temp points
	}//end if next	

		/*code that did not work any better*/
//		tlp->jSetNext((lp->jGetNext())->jGetNext());	
//		delete lp->jGetNext();
//		lp->jSetNext(tlp);

/*Also tried declaring and/or deleting tlp outside of decision structure, and
jDeleteCurrent(tlp) since that function works properly.*/	
}

/*REMOVE CURRENT NODE*/
void JawaListT::jDeleteCurrent(JawaLinkT* lp)
{
	if(lp != jHead && lp != jTail && lp != NULL)	//if not head or tail, not null
	{	
		JawaLinkT* tlp; 							//temp pointer to node

		tlp = lp->jGetNext();			//temp = passed.next
		*lp = *tlp;				//copy temp to passed
		if(tlp == jTail)			//if temp is tail
		{
			this->jSetTail(lp);		//tail = passed
			lp->jSetNext(lp);		//passed.next = passed
		delete tlp;				//delete to what temp points
		}//end if tail
	}//end if not head
}

/*LINEAR SENTINEL SEARCH*/
JawaLinkT* JawaListT::jFindItemS(int item)
{
	JawaLinkT* tlp;					//temp pointer to node
	this->jTail->jSetValue(item);			//tail.data = item

	for(tlp = jHead->jGetNext(); tlp->jGetValue() != item; tlp = tlp->jGetNext());
	/*INIT: node after head, EXIT: data found, UPDATE: increment node*/

	if(tlp == jTail)				//if sentinel found
			std::cout << item << " not in list" << std::endl;	

	return((tlp != this->jTail->jGetNext()) ? tlp : NULL);
	/*If sentinel not found, return proper node, else return null*/
}
 

edited to update status to solved [Edited by - Uther Mortigast on May 30, 2009 9:57:59 PM]

Share this post


Link to post
Share on other sites
Unsure of the solution exactly, but my suspected culprit is the insertBefore method.

It appears you are creating loops and breaking the linked list, If I am not mistaken, twice here.

*tlp = *lp; //copies passed node to temp node
lp->jSetNext(tlp); //passed.next = temp
lp->jSetValue(val); //passed.data = val
if(lp == this->jTail) //if passed is tail
{
this->jTail = tlp; //tail is temp
this->jTail->jSetNext(this->jTail); //tail.next = tail
}//end if lp

The first line is throwing away the tlp u just dynamically allocated in the if statement previous to it, and the following line creates a loop by setting the next node of lp to itself! This is invariably going to cause problems! A similar thing is going on in the setting of jTail.

Unless you have nodes keeping track of their previous node, inserting BEFORE a chosen node requires you to iterate through the list up to that node and link the previous node to the new node. Otherwise it isn't linked in. So, if your lists will be short and this iterating won't be a terrible performance hit, I would proceed that way, but if you plan to have very long lists, it would be wise to restructure your node objects to have a previous pointer, and be sure to add code that assigns this pointer correctly in your insert/delete methods.

I'm happy to help in writing all this extra code if you find yourself confused, but I usually find I learn better if I try something first :) Let me know how it goes!
-Will

Share this post


Link to post
Share on other sites
Quote:
Original post by Uther Mortigast
Compiler: Dev-C++ 4.9.9.2


incidentally Dev-c++ is an IDE that uses the Mingw compiler. It itself is not a compiler. Also Dev-c++ has been abandoned for several years, you may be interested in the free version of visual studio or WxDev-c++(a related project that is still being developed).

Share this post


Link to post
Share on other sites
Here's what I thought I was doing....

myList.jInsertBefore(myList.jFindItemS(6), 9); //from main


jInsertBefore(JawaLinkT* lp, int val)

JawaLinkT* tlp = new JawaLinkT;

H| | a|2| b|4| c|6| T|6|
|a|-> |b|-> |c|-> |T|-> |T|-
^ \ _
tlp|0|
|0|


*tlp = *lp;

H| | a|2| b|4| c|6| T|6|
|a|-> |b|-> |c|-> |T|-> |T|-
^^ / \ _
tlp|6| /
|T|/


lp->jSetNext(tlp);

H| | a|2| b|4| c|6| T|6|
|a|-> |b|-> |c|-> |t| |T|-
/l ^^ / p / \ _
v /
tlp|6| /
|T|/


lp->jSetValue(val);

H| | a|2| b|4| c|9| T|6|
|a|-> |b|-> |c|-> |t| |T|-
/l ^^ / p / \ _
v /
tlp|6| /
|T|/



Should I instead do tlp = lp to get my desired result? The tail should be self-referential, so that's good. And yes, I'm a little confused, but I am trying to learn by doing. I'm just stumped on this mystery error in jDeleteAfter. Thanks for the offer though, Will.

Share this post


Link to post
Share on other sites
Oh okay I kind of see what you're getting at, nice ASCII drawings there :) That isn't anything like what I've learned but I like the self referential Tail Pointer, that's an interesting idea for removing the danger of Null Pointer Exceptions.

Anyways, though, the *tlp = *lp line is still going to cause you looping problems that break part off parts of the list, as you're letting go of the new node you create. A pseudo-code idea of what you wanna do would be something more like:

Quote:

Node * tlp = new Node; //Make the new node to link in

tlp->setNext(lp->getNext);
tlp->setVal(lp->val); // These lines make tlp the same as lp, as u desire

lp->setVal(passed Value);
lp->setNext(tlp); // Now we overwrite the old lp with the new values
// effectively inserting before

Not sure if that quoting worked, anyone tell me how to do that proper?

The key here is to just be copying the values and not making the pointers equal to each other. After this code, you can do your Tail setting logic and everything should be gravy.

One thing that might help would be to write some test main code that runs these routines individually and write a print method that helps you see if each function is operating as you expect. That way it's easier to narrow down the problem :)

Best of luck, come back with progress report/any more questions!
-Will

Share this post


Link to post
Share on other sites
Quote:
Original post by WillBuck
Oh okay I kind of see what you're getting at, nice ASCII drawings there :) That isn't anything like what I've learned but I like the self referential Tail Pointer, that's an interesting idea for removing the danger of Null Pointer Exceptions.


There are no "null pointer exceptions" in C++. What happens when you dereference a null pointer in C++ is undefined.

Also, doing it this way may remove that danger, but it introduces the danger of unexpected infinite loops.

Also, the entire project is useless; the standard library already provides a linked list.

Share this post


Link to post
Share on other sites
Zahlman -
Quote:

There are no "null pointer exceptions" in C++. What happens when you dereference a null pointer in C++ is undefined.


Pardon my mistake, I was taught mostly in Java and default to that terminology sometimes. Point is it can cause problems, yes? ;)

Quote:

Also, doing it this way may remove that danger, but it introduces the danger of unexpected infinite loops.


It's a danger, yes, but in my experience, checking if things like node->next are NULL causes more problems than here, where checking if next = current would more likely be safer. As long as you remember to do the check, you'd avoid the looping.

Quote:

Also, the entire project is useless; the standard library already provides a linked list.


Now I'm new here and you're the moderator and I'm not, and I respect that I should show a great deal of humility. So, please pardon my objecting to the above statement, but why would learning something like this be useless? Sure, he could use the library for a linked list or hash table or whatever he needs for whatever project he's doing, and if he were on a deadline he'd be wise to do so, but how is learning to code something as crucial as data structures properly "useless"? That kind of wording seems a bit harsh and rude to me :/

Share this post


Link to post
Share on other sites

if(lp->jGetNext() != this->jTail && lp != NULL)



Without actually looking at the logic, this is most likely your culprit right here. You're checking to see if lp is not NULL *after* you dereference the pointer via ->GetNext(). If it is NULL, this will crash it. You should check if lp is NULL first, this way it will return false and not execute the second condition check.


if( lp != NULL && lp->jGetNext() != this->jTail )

Share this post


Link to post
Share on other sites
Alright, I've changed the the node shuffling so it uses the class accessors and mutators rather than indirect assignment. I was just trying to get comfortable with pointers, but it's probably safer (and clearer) to do it the way you suggested, Will. Sadly, I'm still getting the same error.

I do have test code in main for each of my functions that evaluates valid and invalid arguments, that's how I discovered this problem, I just didn't include it here. All of the methods except jDeleteAfter seem to work properly, (at least my toString method in a derived class displays what I expect to see) and that abruptly exits my application whether a valid or invalid node is passed. Judicious use of system("PAUSE") indicates that it doesn't crash until "delete tlp;" gets read.

Ookami, great idea on evaluating for != NULL first. It didn't alleviate my current problem, but I'm sure that will prevent future ones. I've adjusted all my code accordingly.

Quote:
Original post by ZahlmanAlso, the entire project is useless...


Perhaps, but the exercise in creating my own linked list was not.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this