Linked list - simple coding question

[DotNetGnat]

Hi Guys,

Below is my attempt to create a double linked list in C++. Please take a look at the classes I came up
with and let me know if there are any sever memory leaks or other errors...

The below code shows partial classes...

I just want to make sure that I am creating and destroying the list and node objects correctly...I am not sure if the code in the destructors is good enough to take care of destroying all objects...

Node Class
___________

node.h
______

class Node
{
private:
	Node *pnext, *pprev;
	char *name;
public:
	Node();
	Node(const char*);
	~Node();
};

node.cpp
________

Node::Node()
{
	name=0;
	pprev=0;
	pnext=0;
}

Node::~Node()
{
	delete [] name;
}

Node::Node(const char* nameval): pprev(0), pnext(0), name(0)
{
	if(nameval)
	{
		int sz = strlen(nameval)+1;
		name = new char[sz];
		memcpy(name,nameval, sz);
	}
}

[green]
List Class
__________

list.h
______
class List
{
private:
	Node *phead;
public:
	List();
	~List();
	int insert_object (Node*,Node*);
	int  delete_all();
};

list.cpp
_________

List::List()
{
	phead=0;
}

List::~List()
{
	[red]delete_all();[/red]
}

int List::delete_all()
{
	int count = 0;
	Node* ptemp;
	while(phead!=0)
	{
		ptemp=phead->getNext();
		phead=ptemp;
		count++;
	}
	return count;
}
[/green]

[blue]
main.cpp
_________
int main(int argc, char* argv[])
{
	
	Node a("Ryan");
	Node b("John");
	Node c("Adam");

	List L1;
	L1.insert_object(&a,0);
	L1.insert_object(&b,0);
	L1.insert_object(&c,0);

	cout << "Total number of objects in the list : " << L1.total_count() << endl;
	return 0;
}

[/blue]

Thanks
-DNG

 

[cpjust]

You do know C++ already has a linked-list in the <list> header right?

 

[DotNetGnat]

yes...I am just trying to learn some basics and mainly trying to avoid memory leaks and other memory related issues...

any suggestions regarding my above code would be really helpful to me...

thanks

-DNG

 

[cpjust]

Yes, you have a 100% memory leak. The delete_all() function never deletes anything, it just moves through the nodes and increments a counter for some reason, even though the destructor isn't using the count for anything.

Your Node class has no accessor functions, so there's no way for anyone to see the data that you're storing in there and there's no way to see the prev & next pointers.

 

[DotNetGnat]

thanks for your reply...I appreciate it...I was just showing the partial classes...i have all the accessors...

thanks

-DNG

 

[uolj]

Make sure to implement or disable copying for both classes. Lookup the Rule of Three for more information on why. In summary, if you don't, you might accidentally copy a Node or List and then your program will probably crash.

(Note: This is one reason why people don't normally use C-style strings and write their own lists.)

 

[bledazemi]

DotNetGnat,

I had a look at the code you posted and thought that the following might be of help to you. (Especially if you come from a .Net background)


Stack vs Heap memory

The code of main function you posted allocates memory variables a,b,c and L1 from the stack. The destructor of each of stack variable will be called as soon as the function or block in which the variable is defined finishes (i.e. when the variables go out of scope). I adjusted slightly your main function to illustrate this.

int main(int argc, char* argv[])
{
    
    Node a("Ryan"); //<-- Stack variable (goes out of scope after main finishes)
    Node b("John"); //<-- Stack variable (goes out of scope after main finishes)
    Node c("Adam"); //<-- Stack variable (goes out of scope after main finishes)

    //Added a block to illustrate the scope of variable is within the block it is defined
    {	
    	List L1; //<-- Stack variable(goes out of scope after this block finishes)

    	L1.insert_object(&a,0);
    	L1.insert_object(&b,0);
    	L1.insert_object(&c,0);
        cout << "Total number of objects in the list : " << L1.total_count() << endl;
    }	
    //At this point L1 goes out of scope and its destructor of L1 will be called
    //You can verify this by putting a break point on List::~List

    return 0;
	
    
}//After main function finishes the destructor of a,b and c will be called

The code in constructor Node you posted allocates memory for the name member variable from the heap (using the new keyword). Your code of Node::~Node destructor correctly frees the memory allocated in heap.

Node::Node(const char* nameval): pprev(0), pnext(0), name(0)
{
    if(nameval)
    {
        int sz = strlen(nameval)+1;
        name = new char[sz]; 		//<-- Heap variable
        memcpy(name,nameval, sz);
    }
}

Node::~Node()
{
    //Already correctly freeing memory allocated on heap for name member variable	
    delete [] name; 
}

So in your code variables are a,b,c and L1 are samples of stack variables. name is a sample of heap variable.



Memory leaks
Because stack memory is automatically freed, the memory leaks are only related to heap memory allocated but not freed. In the sample code that you posted there are absolutely no memory leaks eventhough your List::delete_all is useless (as far as freeing memory is concerned). Thats only because you are defining your nodes as stack variables and these go automatically when the function finishes. (Of course when each node goes out of scope it calls Node::~Node destructor which is written correctly and ensures that the heap memory allocated for name member variable is freed correctly).


Linked Lists and the Heap
In my opinion a linked lists is expected to have memory of each of their nodes on the allocated heap. One reason would be is to avoid nodes being freed automatically whilst the list expects them to still be there. To understand this issue consider the following code.

int main(int argc, char* argv[])
{
    List L1; //<-- Stack variable (goes out of scope after main finishes)

    {
    	Node a("Ryan"); //<-- Stack variable (goes out of scope after this block finishes)
    	Node b("John"); //<-- Stack variable (goes out of scope after this block finishes)
    	Node c("Adam"); //<-- Stack variable (goes out of scope after this block finishes)
    	
    	L1.insert_object(&a,0);
    	L1.insert_object(&b,0);
    	L1.insert_object(&c,0);

    }	

    //At this point a,b, c go out of scope therefore they will be freed 

    //...

    //L1 is still in scope however any processing of the content of its nodes is bound to fail

    return 0;	
}

Possible solutions
In addition to understanding the rule of three (as suggested by uolj) There are two things you need to do.

1. Allocate memory for your nodes on the heap
E.g. Node * pA= new Node("Ryan");

2. Fix your List::delete_all to free the memory on each nodes
If you don't then you will have 100% of memory allocated for your nodes will be leaked (as pointed out by cpjust).



[small]"It is in our collective behaviour that we are most mysterious" Lewis Thomas [/small]