• Advertisement

Archived

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

deleting linkedlists which contain linkedlists

This topic is 5124 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ive been working more with linked lists lately, but I''m stuck on a problem. I delcare a pointer to a WORLD class and allocate memory with it using ''new''. the WORLD class has a pointer to a linkedlist class. In the WORLD''s constructor I have LINKEDLIST* l_list = new LINKEDLIST; the LINKEDLIST class has a two pointers -head & tail- which point to an OBJECT class. OBJECT are newed with an addobject method which addeds a new object to the linked list. OBJECT, like WORLD, has a pointer to a linkedlist class. In the OBJECT''s constructor I have LINKEDLIST* l_list = new LINKEDLIST; I use OBJECT''s linked list to store a list of polygons, texturecoords, etc. So in effect i have a WORLD class that contains a linked list which contains OBJECTs which contain a linked list which contains POLYGONs. I construct all of this without error. But cant simply ''delete'' the world, or I have a huge problem with memory leaks. I am curently calling each class''s deconstructor before I delete it. The deconstructors call addition deconstructors of classes they contain. I then use the delete keyword followed by a pointer to the the class whom''s decontructor I just called. I loop through for all linked lists - decontructing and delete a class with each iteration. Naturally this isnt working, and as you can tell it''s all very complicated. What is the right way to unallocate memory to nested linked lists? Thanyou

Share this post


Link to post
Share on other sites
Advertisement
You don''t need to call a destructor and call delete - delete will call the destructor for you. Apart from that I don''t really understand what your problem is. Could you post some relevant source code?

Enigma

Share this post


Link to post
Share on other sites
Oh, and while I''m at it, is there a reason you''re using your own linked list class? If it''s for learning purposes then fine, otherwise I''d recommend you ditch it and use std::list (or std::deque or std::vector depending on how you use it).

Enigma

Share this post


Link to post
Share on other sites
Unless he''s got a list of pointers, in which case he does have to manually delete each element in turn.


“Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.”
— Brian W. Kernighan (C programming language co-inventor)

Share this post


Link to post
Share on other sites

class POLYGON_LIST{
public:
POLYGON_LIST();
~POLYGON_LIST();
POLYGON* addPolygon(POINT3f, POINT3f, POINT3f);
POLYGON* head;
POLYGON* tail;
};
POLYGON_LIST::POLYGON_LIST(){
this->head = NULL;
this->tail = NULL;
}
POLYGON_LIST::~POLYGON_LIST(){
for(POLYGON* poly_cur= head; ; poly_cur=poly_cur->next){
poly_cur->~POLYGON();
delete poly_cur;
if(poly_cur==tail){
break;
}

}

}
POLYGON* POLYGON_LIST::addPolygon(POINT3f pt_1, POINT3f pt_2, POINT3f pt_3){

if(head== NULL && tail==NULL){

tail = head = new POLYGON(pt_1, pt_2, pt_3);
tail->next = NULL;
}
else{
tail->next= new POLYGON(pt_1, pt_2, pt_3);
tail = tail->next;
tail->next = NULL;
}
return head;
}

class OBJECT{
public:
OBJECT();
~OBJECT();

OBJECT* next;
POLYGON_LIST* polygon_list;
POLYGON_LIST* uvpoly_list;
GLuint draw_list;
};

OBJECT::OBJECT(){
next = NULL;
polygon_list = new POLYGON_LIST;
uvpoly_list = new POLYGON_LIST;
}
OBJECT::~OBJECT(){
polygon_list->~POLYGON_LIST();
uvpoly_list->~POLYGON_LIST();
delete polygon_list;
delete uvpoly_list;
}

class OBJECT_LIST{
public:
OBJECT_LIST();
~OBJECT_LIST();
OBJECT* addObject();
OBJECT* head;
OBJECT* tail;
};
OBJECT_LIST::OBJECT_LIST(){
head = NULL;
tail = NULL;
}
OBJECT_LIST::~OBJECT_LIST(){
for(OBJECT* obj_cur= head; ; obj_cur=obj_cur->next){
obj_cur->~OBJECT();
delete obj_cur;
if(obj_cur==tail){
break;
}

}

}

OBJECT* OBJECT_LIST::addObject(){
if(head==NULL && tail==NULL){

tail = head = new OBJECT;
tail->next = NULL;

}
else{
tail->next = new OBJECT;
tail = tail->next;
tail->next = NULL;
}
return tail;
}

class WORLD{
public:
WORLD();
~WORLD();

OBJECT_LIST* object_list;


};
WORLD::WORLD(){
object_list = new OBJECT_LIST;
}
WORLD::~WORLD(){
object_list->~OBJECT_LIST();
delete object_list;
}

Undocumented source code :-/
I havnt changed it to reflect the changes suggested.
Will do within the hour

Share this post


Link to post
Share on other sites
Having recompiled a version that only uses delete, the problem still exists.
EDIT: It is infact for learning purposes. I enjoy learning how to do things myself first, and afterward using the tools avalible.

[edited by - aaron_ds on February 6, 2004 7:00:05 PM]

Share this post


Link to post
Share on other sites
Well it's a bit unorthadox. Usually a linked list is of the form:
class LinkedListForType
{
public:
LinkedListForType();
~LinkedListForType();
Type append(Type t);
Type get(int index);
private:
Type head;
LinkedListForType* tail;
}

Note the definitions of head and tail.
I can't see anything wrong with it apart from the fact that you call the destructors twice each, once explicitly and once implicitly by deleting, as I mentioned before. Fix that and I think it should work.

One thing I would recommend is that you change this:
for(POLYGON* poly_cur= head; ; poly_cur=poly_cur->next)
{
poly_cur->~POLYGON();
delete poly_cur;
if(poly_cur==tail)
{
break;
}
}

to
for(POLYGON* poly_cur= head; poly_cur != tail; poly_cur=poly_cur->next)
{
delete poly_cur;
}
delete tail;


which I think you'll agree is more readable. This code is in POLYGON_LIST, similar code is in OBJECT_LIST.

Fruny: I never said he didn't have to delete, I said he didn't have to delete and destruct.

EDIT: If it's still not working then I'll have another look. I may well have missed something.

Enigma

EDIT2: Just noticed I'd missed the * from my definition of tail in my LinkedList class.
EDIT3: My suggested code at the end was complete garbage too!

[edited by - Enigma on February 6, 2004 7:16:56 PM]

Share this post


Link to post
Share on other sites
I removed all of the explicit calls to the deconstructors, but the same error orrcurs.
I referenced my data structures after this gamdev article.
which has:

struct node
{
int x;
int y;
node* next;
};

node* head=NULL;
node* tail=NULL;

The head and the tail are both the same datatypes.

Share this post


Link to post
Share on other sites
I think I've found the problem. Change the code I talked about before to:
for(POLYGON* poly_cur= head; poly_cur != tail;)
{
POLYGON* temp = poly_cur;
poly_cur = poly_cur->next;
delete temp;
}
delete tail;

You were deleting the object and then accessing it's next pointer.

EDIT: stupid smiley

Enigma

[edited by - Enigma on February 6, 2004 7:50:05 PM]

Share this post


Link to post
Share on other sites
It''s usually much better to make the LINKEDLIST class be a direct member of WORLD, rather than have a pointer to it. That way, you know that the destructor of LINKEDLIST will get called when the destructor for WORLD gets called, and you don''t have to worry about perhaps forgetting to delete it manually in the destructor.

Share this post


Link to post
Share on other sites
The problem with that approach (article, not what hplus0603 said, which was good advice) is that you are forcing implementation details to do with lists into objects that have nothing to do with lists.

I just tried to find a decent article on linked lists, but I couldn't, so bear with me and I'll try and write one:

Objects in the list should not need to know anything about lists. This way we can change the list for any other data structure and everything will still work.

I gave an outline for a linked list class before. Here's a slightly modified version:
// this is the class of objects we will put in our linked list.
class Content
{
};
// this is out linked list class
class LinkedListForContent
{
public:
LinkedListForContent();
~LinkedListForContent();
void append(Content* object);
Content* get(int index);
private:
Content* head;
LinkedListForContent* tail;
};

Now for the constructor. The initial list has no content and no tail:
LinkedListForContent::LinkedListForContent()
{
head = null;
tail = null;
}

We'll leave the destructor for a bit. Next we'll write the append method.

Our fist LinkedList node has no content, so we can just put the content into the node. After that things get tricky. To simplify things we'll do the following. Everytime we insert an object we check if the current node already has data. If not we put the data in this node and create a new node after this one. If this node already has data then we move on to the next node and try there.

This means that there will always be a free node at the end of the list with no data.
void LinkedListForContent::append(Content* object)
{
if (head == null)
{
head = object;
tail = new LinkedListForContent();
}
else
{
tail->append(object);
}
}

Now for the get function. This one is easy. If the index is zero then we wan't the item from the current node. If not we want the item from (index - 1) nodes further down, so we can just get the (index - 1)'th item from the tail of the list.
Content* LinkedListForContent::get(int index)
{
if (index < 0)
{
// somebody's just being silly
return null;
}
else if (index == 0)
{
return head;
}
else if (tail != null)
{
return tail->get(index - 1);
}
else
{
// there's no more list left
return null;
}
}

Finally the destructor. All we need to do is delete the data object and ask the rest of the list to delete itself.
LinkedListForContent::~LinkedListForContent()
{
delete head;
delete tail;
}


Hopefully that makes sense. If you have any questions then just ask. Note that a real list wouldn't delete the whole list in the destrutor. It would only delete the node. Instead it would provide a function to delete the whole list. This arrangement allows you to do things like remove an item from the middle of the list, or remove the first element.

Enigma

EDIT: typos
EDIT2: more typos
EDIT3: and yet more typos
EDIT4: ditto
EDIT5: clarification

[edited by - Enigma on February 6, 2004 8:23:39 PM]

Share this post


Link to post
Share on other sites
Perhaps this would be better.

template <typename T>

class LINKED_LIST{
public:
LINKED_LIST();
~LINKED_LIST();
T* addNode();
T* head;
T* tail;
};
LINKED_LIST::LINKED_LIST(){
head = NULL;
tail = NULL;
}
LINKED_LIST::~LINKED_LIST(){
for(T* node_cur= head; node_cur!=tail ;){
T* temp = node_cur;
node_cur = node_cur->next;
delete node_cur;
}
delete tail;
}
T* LINKED_LIST::addNode(){
if(head==NULL && tail==NULL){

tail = head = new T;
tail->next = NULL;

}
else{
tail->next = new T;
tail = tail->next;
tail->next = NULL;
}
return tail;
}
LINKED_LIST<OBJECT> OBJECT_LIST;
LINKED_LIST<POLYGON> POLYGON_LIST;

I am leaving tail as a T* as I dont want a linked list of linked lists, although, in effect thats what im doing. I simply want a spartan linked list of one dimension.
EDIT: I'm sorry, my title is misleading. I should have said: I want to delete linked lists of objects that contain linked lists.

[edited by - aaron_ds on February 6, 2004 10:34:19 PM]

Share this post


Link to post
Share on other sites
The problem with your method is that you are still requiring your OBJECT and POLYGON classes to know about lists, because they need to have next pointers. What happens when you decide they ought to go in a different data structure instead? What if you decide that you want a doubly linked list? Now you must add a ''previous'' pointer to every class that will be in a doubly linked list . This is bad design. Only the list should need to know how lists work. This way when you change the list, only the list needs to change.

And yes, templates are definitely the way to go. The only reason I didn''t use them in my example is because people who are writing linked lists for learning purposes usually don''t know templates exist .

Enigma

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
For a linked list tutorial may I recommend the following link :-

http://cslibrary.stanford.edu/103/

Probably not what you are looking for but, if you are just starting out using linked lists, this should point you in the right genral direction.

If I remember correctly it covers both C and C++.

Share this post


Link to post
Share on other sites
yes, I agree, they should not know about lists/ have a next pointer. I guess ill start work on a NODE class
Thankyou so much for your help.

Share this post


Link to post
Share on other sites

  • Advertisement