infinite linked list

[uTil]

Hi, I made a post like this in the Beginner section and wondered if the content was appropriate. So regardless this is regarding an object I've created to store a list of strings using linked lists. The basic idea is put into code below:

// strset.h
struct linkedList {
	std::string value;
	linkedList * node;
};

class strSet
{
private:
    linkedList* head;			// This is initially empty (when constructed)		
    bool isSorted () const;

public:
    strSet (); 			  	// Create empty set
    strSet (std::string s); 	 	// Create singleton set
    strSet (const strSet& rtSide);	// Copy constructor
    ~strSet ();			 	// Destructor
...
    strSet  operator +  (const strSet& rtSide);  // Union
    strSet  operator *  (const strSet& rtSide);  // Intersection
    strSet  operator -  (const strSet& rtSide);  // Set subtraction
    strSet& operator =  (const strSet& rtSide);  // Assignment

};

 // strset.cpp

...
strSet strSet::operator + (const strSet& rtSide) {
	int comparedValue;
	string thisString, rtString;
	linkedList *thisList = head;
	linkedList *rtList   = rtSide.head;
	linkedList *tempDelete;

	strSet *tempList = new strSet();
	if( (thisList != NULL) || (rtList != NULL) ) tempList->head = new linkedList;
	linkedList *newList = tempList->head;

	if( newList == NULL )  cout << "You got NULL TEMP HEAD!" << endl;

	while( (thisList != NULL) || (rtList !=NULL) ) { 

		if(thisList != NULL) thisString = thisList->value;
		if(rtList   != NULL) rtString   = rtList->value;
		if(head     != NULL) comparedValue = thisString.compare(rtString);


		if(thisList == NULL) comparedValue = 1;
		if(rtList   == NULL) comparedValue = -1;

		if( comparedValue == 0 ) {

			newList->value = thisString;
			newList->node = new linkedList;
			newList  = newList->node;			

			thisList = thisList->node;
			rtList   = rtList->node;

} else if( comparedValue > 0 ) { 
... 
	tempDelete = tempList->head;
	cout << "TempDelete head address: " << tempList->head << endl;

	while(tempDelete != NULL) {
		cout << "tempDelete address: " << tempDelete << endl;
		cout << "tempDelete node   : " << tempDelete->node << endl;
		tempDelete = tempDelete->node;
	}

	return *tempList;
}

...
strSet& strSet::operator = (const strSet& rtSide) { 
	nullify();
	linkedList *newList, *rtList = rtSide.head;
	int count = 0;
	if( rtSide.head == NULL ) { 
	        head = NULL; 
		return *this;
	}
	cout << "rtList head address: " << rtSide.head << endl;
	head = new linkedList;
	newList = head;
	do { 
		newList->node = new linkedList;
		newList->value = rtList->value;

		rtList         = rtList->node;
		cout << "rtList address: " << rtList << endl;
		cout << "rtList value : " << rtList->value << endl;
		if(rtList == NULL) cout << "RT LIST HAS A NULL HEAD!" << endl;
		newList        = newList->node;
		count ++;
	}while( rtList != NULL  && count < 10);

	delete newList;
	newList = NULL;
	return *this;
}

 // main.cpp
...
	tempSet = (tempSet + tempSet2);
...

This is the output from the main code (particularly adding the two sets together)
The first set is null, and the second set just has one string.
strSet tempSet;
strSet tempSet2("a") <--- a string "a"
tempSet = tempSet + tempSet2; :

TempDelete head address: 0xda00b0
tempDelete address: 0xda00b0
tempDelete node   : 0xda00d0
tempDelete address: 0xda00d0
tempDelete node   : 0
rtList head address: 0xda00f0
rtList head address: 0xda00f0
rtList address: 0xda0110
rtList value : 
rtList address: 0xda0130
rtList value : a
rtList address: 0xda0150
rtList value : 
rtList address: 0xda0170
rtList value : a
rtList address: 0xda0190
rtList value : 
rtList address: 0xda01b0
rtList value : a
rtList address: 0xda01d0
rtList value : 
rtList address: 0xda01f0
rtList value : a
rtList address: 0xda0210
rtList value : 
rtList address: 0xda0230
rtList value : a

My main question is, why does the object that I am returning have a finite linkedList, yet the same one I pass through the = operator as a parameter, has an infinite linkedList?

[naraku9333]

Its your while condition in operator=

[uTil]

Hey I appreciate your help, but I don't see what's entirely wrong with my while condition.

rtList initially stores the head of the linkedList from rtSide. This linkedList should eventually hit a NULL address shouldn't it?

[naraku9333]

I did jump the gun abit, sorry. I assumed "RT LIST HAS A NULL HEAD!" wasnt in your output that you had an issue with the condition (or rtList)
Have you stepped through it with a debugger?

[uTil]

Yeah i tried running it with the debugger but it didn't give much insight as to where my main problem lies. I mean in all honesty, I have ran tests on (*tempSet) - > dereferenced object that I am returning from the operator+ and it is fine. So I think the operator + is okay, it comes down to my assignment operator.

At what point did my finite list just instantly keep pointing to itself looping forever?

[kbw]

You have serious memory issues. Consider strSet operator+(const strSet& rtSide);.

It returns a strSet, you'd expect to construct a temporary one and return that. Instead, you make a new one on the heap and copy that for the return. What do you think happens to the object you created on the heap? Further to that, without seeing the copy constructor, it's impossible to say what actually happens.

[uTil]

Thanks kbw, I realize I should delete the object I create on the heap. Can I do that before returning it or should I avoid allocating to heap in general?

Also this is the code for the copy constructor:

strSet::strSet(const strSet& copy) {
       	linkedList *thisList, *copyList;
	copyList = copy.head;	
	if( copy.head == NULL ) { 
		head = NULL;
	} else {
		thisList = new linkedList;
		head = thisList;

		while(copyList != NULL) {
			thisList->node  = new linkedList;
			thisList->value = copyList->value;

			thisList = thisList->node;
			copyList = copyList->node;
		}
		delete thisList;
		thisList = NULL;
	}
}

Thanks again for you help. I think that my problem might be related to the mess of memory allocations I make. I just don't think I can access private members without making a pointer (also we aren't allowed to make additional functions).

[kbw]

The copy constructor's not pretty, but it's almost correct. You should ask yourself what lines 17 and 18 do. And when does the node's next pointer get set to null?

HINT: linkedList should have it's own constructor that initialises value and node to known values.

Can I do that before returning it or should I avoid allocating to heap in general?

You should not create a strSet of the heap to begin with. Create one locally (on the stack) and return that, it'll be copied to the return value.

[uTil]

Hi kbw, thanks again for the help and advice.

The idea behind lines 17 and 18 came from a bad copy algorithm I made. I realized that after I exit the while loop, (thisList) is a new linkedList when copyList is actually NULL. So I just fix this by deleting thisList (deallocating space I made) and resetting it to NULL. Is this what is causing my list to loop?

I can try making a constructor, I think that will simplify things a lot (in actuality, I didnt' know structures had constructors).

I will try this again without heap memory. But this doesn't illustrate to me how my copied strSet loops- should I instead put an if statement in my while loop:

 
if(copyList-> node == NULL)  thisList->node = NULL; 

?

[kbw]

Your linked list is made up of nodes allocated on the heap. But that doesn't apply to strSet.

The copy constructor is correct except for:
1. lines 17 and 18 should be removed
2. you don't set the value of node in linkedList

Method strSet& strSet::operator = (const strSet& rtSide) should:
1. check for assignment to self before doing the copy
2. delete the old list
3. copy in a new one--this is identical to what the copy constructor does

Method strSet strSet::operator + (const strSet& rtSide) should:
1. create a local instance of strSet, do your Union thing on that
2. return the local instance, the copy constructor will be used to pass it out