[doothedew]

I am trying to do copy constructors and I can get them to work if I don't try to delete anything. When I run this code it works unless I initialize an empty linked list and try to use the copy constructor. How do I get the if condition to recognize that it doesn't need to delete a Node that doesn't exist?

//!  deep copy, Copy constructor.  Makes a complete copy of its argument
LinkedList::LinkedList(const LinkedList & other)
{
	Clear();
	first=NULL;
	last=NULL;
	if(!other.IsEmpty())
	{
		LLNode* otherPointer = other.first;
		while(otherPointer!=NULL)
		{
			Insert(otherPointer->value ,GetLast());
			otherPointer=otherPointer->GetNext();
		}
	}
}
//!  Removes all values from the list
void LinkedList::Clear()
{
	if(first!=NULL)
		deleteAll(first);
	size=0;
}

void LinkedList::deleteAll(LLNode* node)
{
	if (node->next!=NULL)
		deleteAll(node->next);
	delete node;
}

It keeps seg faulting at the (if node->next!=NULL) because for some reason the condition for if(first!=NULL) doesn't work for this empty list. Why? Any tips or suggestions on how to clean this up so that my conditions work would be aprreciated

Oh, PS this post was called fixing up memory leaks because if I don't call delete node; it works just fine.

[NickDMax]

using recursion in linked lists is actually a bad idea. works great if your compiler will optimize for tail recursion and you properly setup your recursion to use tail recursion; but otherwise it results in eating up mass amounts of stack space.

since in this case there is no logical (i.e. make the code easier to follow) reason to use recursion why not just use iteration:

	void LinkedList::deleteAll(LLNode* node)
	{
	    LLNode* temp;
	    while(node!=NULL) 
	    {
	        temp = node->next;
	        delete node;
	        node = temp;
	    }
	}

[doothedew]

NickDMax, on 09 July 2011 - 01:00 PM, said:

using recursion in linked lists is actually a bad idea. works great if your compiler will optimize for tail recursion and you properly setup your recursion to use tail recursion; but otherwise it results in eating up mass amounts of stack space.

since in this case there is no logical (i.e. make the code easier to follow) reason to use recursion why not just use iteration:

	void LinkedList::deleteAll(LLNode* node)
	{
	    LLNode* temp;
	    while(node!=NULL) 
	    {
	        temp = node->next;
	        delete node;
	        node = temp;
	    }
	}

I appreciate the tip but this doesn't work either, in fact this makes my simple test cause worse. Here is the test case, I still don't understand why this will not work??

LinkedList* t2 = new LinkedList(*newList);
cout<<"T2 Size: "<<t2->GetSize()<<endl;
t2->Clear();
cout<<"t2 clear"<<endl;
LinkedList* t3 = new LinkedList(*t2);
cout<<"T3 Size: "<<t3->GetSize()<<endl;

It just doesn't make sense to me...It doesn't reach the last cout.

[ishkabible]

what doesn't work about it? have you used a debugger yet?

[doothedew]

what doesn't work is when I get to this condition:

while(node!=NULL)
	    {
        temp = node->next;

even though "node" is NULL it ignores the conditional and then segfaults when it trys to assign node->next to temp. It works fine when there is something to delete but when the list is empty it blows up in a giant fire-ball of death.

[doothedew]

here is the error that shows up:
*** glibc detected *** /home/doolsk/workspace/LinkedList/Debug/LinkedList: free(): invalid pointer: 0x082a60f4 ***
======= Backtrace: =========
/lib/i386-linux-gnu/libc.so.6(+0x6b961)[0x17b961]
/lib/i386-linux-gnu/libc.so.6(+0x6d28b)[0x17d28b]
/lib/i386-linux-gnu/libc.so.6(cfree+0x6d)[0x18041d]
/usr/lib/i386-linux-gnu/libstdc++.so.6(_ZdlPv+0x21)[0xc224d1]
/usr/lib/i386-linux-gnu/libstdc++.so.6(_ZNSs4_Rep10_M_destroyERKSaIcE+0x1d)[0xc04bad]
/usr/lib/i386-linux-gnu/libstdc++.so.6(_ZNSsD1Ev+0x4c)[0xc04c6c]
/home/doolsk/workspace/LinkedList/Debug/LinkedList[0x8048fb3]
/home/doolsk/workspace/LinkedList/Debug/LinkedList[0x8048b73]
/home/doolsk/workspace/LinkedList/Debug/LinkedList[0x8048b33]
/home/doolsk/workspace/LinkedList/Debug/LinkedList[0x8048a07]
/home/doolsk/workspace/LinkedList/Debug/LinkedList[0x8049492]
/lib/i386-linux-gnu/libc.so.6(__libc_start_main+0xe7)[0x126e37]
/home/doolsk/workspace/LinkedList/Debug/LinkedList[0x8048941]
======= Memory map: ========
00110000-0026a000 r-xp 00000000 08:01 1099 /lib/i386-linux-gnu/libc-2.13.so
0026a000-0026b000 ---p 0015a000 08:01 1099 /lib/i386-linux-gnu/libc-2.13.so
0026b000-0026d000 r--p 0015a000 08:01 1099 /lib/i386-linux-gnu/libc-2.13.so
0026d000-0026e000 rw-p 0015c000 08:01 1099 /lib/i386-linux-gnu/libc-2.13.so
0026e000-00271000 rw-p 00000000 00:00 0
007db000-007f5000 r-xp 00000000 08:01 1127 /lib/i386-linux-gnu/libgcc_s.so.1
007f5000-007f6000 r--p 00019000 08:01 1127 /lib/i386-linux-gnu/libgcc_s.so.1
007f6000-007f7000 rw-p 0001a000 08:01 1127 /lib/i386-linux-gnu/libgcc_s.so.1
00b78000-00c57000 r-xp 00000000 08:01 268183 /usr/lib/i386-linux-gnu/libstdc++.so.6.0.14
00c57000-00c5b000 r--p 000de000 08:01 268183 /usr/lib/i386-linux-gnu/libstdc++.so.6.0.14
00c5b000-00c5c000 rw-p 000e2000 08:01 268183 /usr/lib/i386-linux-gnu/libstdc++.so.6.0.14
00c5c000-00c63000 rw-p 00000000 00:00 0
00c9d000-00c9e000 r-xp 00000000 00:00 0 [vdso]
00d0f000-00d33000 r-xp 00000000 08:01 1136 /lib/i386-linux-gnu/libm-2.13.so
00d33000-00d34000 r--p 00023000 08:01 1136 /lib/i386-linux-gnu/libm-2.13.so
00d34000-00d35000 rw-p 00024000 08:01 1136 /lib/i386-linux-gnu/libm-2.13.so
00da9000-00dc5000 r-xp 00000000 08:01 1086 /lib/i386-linux-gnu/ld-2.13.so
00dc5000-00dc6000 r--p 0001b000 08:01 1086 /lib/i386-linux-gnu/ld-2.13.so
00dc6000-00dc7000 rw-p 0001c000 08:01 1086 /lib/i386-linux-gnu/ld-2.13.so
08048000-0804a000 r-xp 00000000 08:01 195832 /home/doolsk/workspace/LinkedList/Debug/LinkedList
0804a000-0804b000 r--p 00001000 08:01 195832 /home/doolsk/workspace/LinkedList/Debug/LinkedList
0804b000-0804c000 rw-p 00002000 08:01 195832 /home/doolsk/workspace/LinkedList/Debug/LinkedList
082a6000-082c7000 rw-p 00000000 00:00 0 [heap]
b7700000-b7721000 rw-p 00000000 00:00 0
b7721000-b7800000 ---p 00000000 00:00 0
b7807000-b780a000 rw-p 00000000 00:00 0
b7817000-b781a000 rw-p 00000000 00:00 0
bffa6000-bffc7000 rw-p 00000000 00:00 0 [stack]

[KYA]

Can you post your class and the entire driver?

In the meantime, shameless plug.

[baavgai]

The delete code offered is valid... as long as the nodes are valid. If the nodes are initialized with crap, you will seg fault.

[Bench]

doothedew, on 09 July 2011 - 10:55 PM, said:

what doesn't work is when I get to this condition:

while(node!=NULL)
	    {
        temp = node->next;

even though "node" is NULL it ignores the conditional and then segfaults when it trys to assign node->next to temp. It works fine when there is something to delete but when the list is empty it blows up in a giant fire-ball of death.

If your program reaches temp=node->next; then it means 'node' has a non-null value, and is probably a "dangling" pointer which was either never initialised, or an object it used to point to had been prematurely deleted.

as KYA suggested, you'll need to post your complete code because the problem doesn't appear to be with your cleanup - something else must have silently gone wrong some time before you reached this point.

One thing you could do is to ensure that your node::next is always initialised to something half-sensible as soon as the object is created (leaving 'next' uninitialised will certainly cause problems like this)

struct LLNode
{
   SomeDataType data;
   LLNode* next;
   LLNode(LLNode* n = NULL) : next(n)
   {}
}; 

doing this ensures that creating an LLNode will give you a value of NULL for the LLNode::next pointer unless you pass it something else when you create it.

[NickDMax]

One thing I noted is that in your Clear() method you need to make sure that you set first and last to NULL. This is important to do here.

[doothedew]

My Linked List IMPL

/*
 * LinkedList.cpp
 *
 *  Created on: Jun 30, 2011
 *      Author: doolsk
 */

#include "LinkedList.h"
#include <iostream>
using namespace std;


//!  No-arg constructor.  Initializes an empty linked list
LinkedList::LinkedList()
{
	size=0;
	first=NULL;
	last=NULL;
}
//!  deep copy, Copy constructor.  Makes a complete copy of its argument
LinkedList::LinkedList(const LinkedList & other)
{
	Clear();
	first=NULL;
	last=NULL;
	if(!other.IsEmpty())
	{
		LLNode* otherPointer = other.first;
		while(otherPointer!=NULL)
		{
			Insert(otherPointer->value ,GetLast());
			otherPointer=otherPointer->GetNext();
		}
	}
}
//!  Destructor
LinkedList::~LinkedList()
{
	Clear();
}
//! Assignment operator.  Makes a complete copy of its argument
//! @return A reference to oneself
LinkedList& LinkedList::operator =(const LinkedList & other)
{
	if(this!=&other)
	{
		Clear();
		if(!other.IsEmpty())
		{

			LLNode* otherPointer = other.first;
			while(otherPointer!=NULL)
			{
				Insert(otherPointer->value ,GetLast());
				otherPointer=otherPointer->GetNext();
			}
		}}
	return *this;
}
//!  @return true if the list is empty, or false if the list is not empty
bool LinkedList::IsEmpty() const
{
	return size<=0;
}
//!  Removes all values from the list
void LinkedList::Clear()
{
	if(first!=NULL)
		deleteAll(first);
	size=0;
	first=NULL;
	last=NULL;
}

void LinkedList::deleteAll(LLNode* node)
{
	LLNode* temp;
	while(node!=NULL)
	{
		temp = node->next;
		delete node;
		node = temp;
	}
}
//!  @return the number of values in the list
int LinkedList::GetSize() const
{
	return size;
}
//!  @return a pointer to the first node in the list, or NULL if the list is empty
LLNode * LinkedList::GetFirst()const
{
	return first;
}
//!  @returns a pointer to the last node in the list, or NULL if the list is empty
LLNode * LinkedList::GetLast()const
{
	return last;
}
//!  Inserts value v into the list after node n
//!
//!  @param v The new value being inserted
//!  @param n A node that is already in the list after which the new node should
//!      be inserted.
//!      If n is NULL, the new node should be inserted at the beginning of the list.
//!
//!  @return a pointer to the newly inserted node
LLNode * LinkedList::Insert(const std::string & v, LLNode * n)
{
	LLNode* newNode = new LLNode(v,NULL, NULL);
	if(first==NULL)
	{
		first =newNode;
		last=newNode;
	}
	else if (n==NULL)
	{
		first->prev=newNode;
		newNode->next=first;
		first= newNode;
	}
	else
	{
		newNode->prev=n;
		if(n->GetNext()==NULL)
		{
			n->next=newNode;
			last=newNode;
		}
		else
		{
			newNode->next=n->next;
			n->next=newNode;
			newNode->next->prev=newNode;
		}
	}
	size++;
	return newNode;
}
//! Searches for the first occurrence of value v that appears in the list
//!   after node n
//!
//!  @param v The value being searched for
//!  @param n The node in the list after which the search should begin.
//!      If n is NULL, the list should be searched from the beginning.
//!
//!  @return a pointer to the node containing v, or NULL if v is not found
LLNode * LinkedList::Find(const std::string & v, LLNode * n) const
{
	LLNode* tempNode = first;
	int i=0;
	if(n!=NULL)
	{
		while(tempNode!=n)
		{
			tempNode=tempNode->GetNext();
			i++;
			if(i>size)
			{
				return NULL;
			}
		}
		if(tempNode==n)
		{
			tempNode=tempNode->GetNext();
			i++;
		}
	}
	for(int j=i;j<size;j++)
	{
		if(tempNode->GetValue()==v)
		{
			return tempNode;
		}
		else
		{
			tempNode=tempNode->GetNext();
		}
	}
	return NULL;
}
//!  Removes node n from the list
//!
//!  @param n The node being removed from the list
void LinkedList::Remove(LLNode * n)
{
	if(n==first && n==last)
	{
		first=NULL;
		last=NULL;
		n=NULL;
		size--;
	}
	else if(n==first)
	{
		first =n->next;
		n->next->prev=NULL;
		n=NULL;
		size--;
	}
	else if (n==last)
	{
		last = n->prev;
		n->prev->next=NULL;
		n=NULL;
		size--;
	}
	else
	{
		LLNode* tempNode=first;
		while(tempNode!=n)
		{
			tempNode=tempNode->next;
			if(tempNode==NULL)
			{
				break;
			}
		}
		if(tempNode!=NULL)
		{
			LLNode* lSide;
			LLNode* rSide;
			lSide =tempNode->prev;
			rSide =tempNode->next;
			lSide->next=rSide;
			rSide->prev=lSide;
			tempNode=NULL;
			n=NULL;
			size--;
		}
	}
}

My TestCode

/*
 * main.cpp
 *
 *  Created on: Jul 6, 2011
 *      Author: doolsk
 */

#include "LinkedList.h"
#include <string>
#include <iostream>
using namespace std;

int main(int argc, char*argv[])
{
	string one("1");
	string two("2");
	string three("3");
	string four("4");

	LinkedList* newList = new LinkedList();

	newList->Insert(one,NULL);
	newList->Insert(two,newList->GetLast());
	newList->Insert(three,newList->GetLast());
	newList->Insert(four,newList->GetLast());

	LinkedList* tList = new LinkedList();

	tList->Insert(two,tList->GetLast());
	tList->Insert(three,tList->GetLast());
	tList->Insert(one,tList->GetLast());

	LLNode* tempNode=newList->GetFirst();
	for(int i =0; i<newList->GetSize();i++)
	{
		cout<<"\t"<<tempNode->GetValue()<<endl;
		tempNode=tempNode->GetNext();
	}

	newList=tList;
	cout<<"after assignment"<<endl;
	tempNode=newList->GetFirst();
	for(int i =0; i<newList->GetSize();i++)
	{
		cout<<"\t"<<tempNode->GetValue()<<endl;
		tempNode=tempNode->GetNext();
	}
	if (tempNode!=NULL)
	{
		cout<<"ERROR!"<<endl;
	}
	else
	{
		cout<<"Test Copy Constructor"<<endl;
	}
	cout<<newList->GetSize()<<endl;
	LinkedList* t2 = new LinkedList(*newList);
	cout<<"T2 Size: "<<t2->GetSize()<<endl;
	t2->Clear();
	cout<<"t2 clear"<<endl;
	LinkedList* t3 = new LinkedList(*t2);
	cout<<"T3 Size: "<<t3->GetSize()<<endl;
	LinkedList* t4=new LinkedList();
	LinkedList* t5 = new LinkedList(*t4);
	cout<<"T5 Size: "<<t5->GetSize()<<endl;
	t5->Clear();
	t4->Clear();
	delete t2;
	delete t3;
	delete t5;
	delete t4;
	cout<<"Delete"<<endl;

	return 0;
}

[doothedew]

it dies on line 61 of my test code when it gets to the node->next part

[NickDMax]

In the copy constructor -- you need to set first and last to NULL BEFORE you try to delete them...

Generally I like to use initialization lists:

LinkedList::LinkedList(const LinkedList & other) : first(NULL), last(NULL) {
//no need to Clear() because this is a new object, there is nothing to clear.
    if(!other.IsEmpty())
    {
        LLNode* otherPointer = other.first;
        while(otherPointer!=NULL)
        {
            Insert(otherPointer->value ,GetLast());
            otherPointer=otherPointer->GetNext();
        }
    }
}

[doothedew]

But won't that leak memory if I don't clear the list before I can copy the other one to this one?

Clarification: I know I am running into the problem because I am trying to clear an empty list but what if I am copying a list that has stuff in it from another list? wont that leak memory?

[NickDMax]

constructor - a constructor is used when creating a new instance of an object.

i.e. the current object did not exist prior to the constructor and therefore it does not have anything to "clear". How can this be a memory leak?

Now an assignment operator is a different story, there you need to ensure you clear the existing data before you copy in the new data. but a copy constructor is making a new instance of the class.