Archived

This topic is now archived and is closed to further replies.

jakerrz

Destroying my list... am I doing it right?

Recommended Posts

Hello, I am experimenting with lists (and class templates) so that I can better understand how they work. I made a Linked list class and I got it working I just want to make sure that my destroy function is doing what I think it is. I don''t want any memory leaks. Could someone please proof read my functions and tell me if the destroy function looks like it takes care of everything? The Class:
  
template <class T> class LinkedList
{
	private:
	T* root;

	public:
	
	void
	create();

	void
	destroy();

	bool
	empty();

	void
	insert(T item);
};



template <class T> void LinkedList<T>::create()
{
	root = NULL;
}


template <class T> bool LinkedList<T>::empty()
{

	return (root == NULL);
}

template <class T> void LinkedList<T>::insert(T item)
{

	T* temp;
	
	if(root == NULL)
	{
		root = new T;
		root->data = item.data;
		root->Next = NULL;
	}

	else
	{

	temp = root;
	
	while(temp->Next != NULL)
		temp = temp->Next;

	temp->Next = new T;
	temp = temp->Next;
	temp->data = item.data;
	temp->Next = NULL;

	}
}

//this  is the one I''m worried about ;)

template <class T> void LinkedList<T>::destroy()
{
	if(root == NULL)
		return;
	
	T* temp;
	T* nextone;

	temp = root;
	while(temp->Next != NULL)
	{
		nextone = temp->Next;
		delete temp;
		temp = nextone;
	}

	delete temp;
	root = NULL;

}
  

Share this post


Link to post
Share on other sites
Your destroy function seems ok.
Just make sure you have the destructor for the class you want well done. For example, it may be possible for your T.data to be a pointer wich will need to be freed in your T destructor?

Just one little thing. Your insert has complexity O(n). You could make it O(1) if you kept a pointer to the tail of your list.

note:
if you''re using linux (which i doubt) you can test the memory consumed/freed by your program by using memusage.
i''m not very confortable with VStudio.Net, but there must be an option somewhere to test your program for mem consumed/freed

Share this post


Link to post
Share on other sites
Your destroy function will work, but i though i''d give you some tips anways. while(temp->next !=NULL) should just be
while(temp->next), since once you traverse the list completely temp->next will be NULL. Also there is no need to to introduce two new pointers to T, just use root and temp. This way you can use while(root->next) and delete the temp object, and you wont have to assign root to NULL at the end. Additionally unless you specifically #define or const int NULL = 0; globally you should not use NULL. Just my two cents.

Share this post


Link to post
Share on other sites
Look here:
http://151.196.11.50/spring2003/intprog/lecture-notes/pointers.html
http://www.doc.ic.ac.uk/lab/cplus/c++.rules/chap12.html
Although there are some good arguments against it, I continue to use NULL because I don''t like ''magic numbers'' throughout my code and because there''s no guarantee that setting a pointer to equal 0 will make it have an all-zero bits representation anyway.



[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
quote:
Original post by petewood
[quote]there''s no guarantee that setting a pointer to equal 0 will make it have an all-zero bits representation anyway.


come again?
The C/C++ standard does not specify that the pointer constant 0 will map to the memory address represented by all zeros. For instance, a compiler may decide that
void* abc = 0;

may cause the value in abc to be something like 0x24242424. Any value is acceptable, as long as it never matches a valid pointer.


How appropriate. You fight like a cow.

Share this post


Link to post
Share on other sites
hello again,
I just worked on my list class again today and I think I made some improvements.

quote:
Original post by wolverine
Just one little thing. Your insert has complexity O(n). You could make it O(1) if you kept a pointer to the tail of your list.



I haven't studied big O yet so I'm not sure what it means exatly but I added a tail pointer and I think It optomised it quite a bit.

I haven't added a destructor yet either but I will.

oh yeah and I added a function called foreachnode() which is passed a function, it just traverses the list and calls the function passing that function the current node.

        
template <class T> class LinkedList
{
private:
T* root;
T* tail;

public:

void
create();

void
destroy();

bool
empty();

void
insert(T item);

void
foreachnode(void(*)(T));
};



template <class T> void LinkedList<T>::create()
{
root = NULL;
tail = NULL;
}

template <class T> void LinkedList<T>::destroy()
{
if(root == NULL)
return;

T* temp;

temp = root;
while(temp)
{
root = root->Next;
delete temp;
temp = root;
}

delete temp;
tail = NULL;

}

template <class T> bool LinkedList<T>::empty()
{

return (root == NULL);
}

template <class T> void LinkedList<T>::insert(T item)
{


if(root == NULL)
{
root = new T;
root->data = item.data;
root->Next = NULL;
tail = root;
}

else
{

tail->Next = new T;
tail = tail->Next;
tail->data = item.data;
tail->Next = NULL;

}
}

template <class T> void LinkedList<T>::foreachnode(void (*customfunction)(T))
{
T* temp;
if(root == NULL)
return;
temp = root;

while(temp)
{
(*customfunction)(*temp);
temp = temp->Next;
}

}


So does it look better? can anyone tell me how to implement the destructor in the way wolverine suggested?

quote:
Original post by wolverine
Just make sure you have the destructor for the class you want well done. For example, it may be possible for your T.data to be a pointer wich will need to be freed in your T destructor?



Thanks again!!


[edited by - jakerrz on May 6, 2003 2:49:43 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Sneftel
The C/C++ standard does not specify that the pointer constant 0 will map to the memory address represented by all zeros. For instance, a compiler may decide that
void* abc = 0;

may cause the value in abc to be something like 0x24242424. Any value is acceptable, as long as it never matches a valid pointer.



Is that a problem though? The point of setting a pointer to zero is so that you can compare it to zero. The comparison operator would either have to convert the pointer to an int or the int to a pointer.

Is that where you see the problem - that converting the pointer back to an int wouldn''t have the expected result? I would have thought the compiler writer would expect the pointer to be used in this way and would provide the correct conversions. If the comparison happens the other way - an int converted to a pointer - there shouldn''t be a problem if there is a consistent conversion, say from 0 to 0x24242424

Share this post


Link to post
Share on other sites