Jump to content
  • Advertisement

Archived

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

aaron_ds

deleting linkedlists which contain linkedlists

This topic is 5392 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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!