Archived

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

Dark Star

deleting dynamically allocated memory.

Recommended Posts

Hi all, I wanted to know how I can delete a link list of structs. For example, I have a structure in my game called BloodList struct BloodList { int x,y; BloodList *next; }bloodStains; The next pointer points to another structure of type BloodList. I have no problem creating this linked list but my problem is deleting it. I have thought of this method of deleting all of the memory allocated for the linked list like this: void ClearList(BloodList *p) { if (p->next) { // this node has a link visit that first. ClearList(p->next); } // delete this node delete p; p=0; } I have not got a chance to try this yet as I have been away from my computer, but do u think this will work? You see, this function tests if the current node points to anything else, if so then that node is visited and if that one does not point to anything then it is deleted. This function is recursive as you can see and it has been written to delete all the nodes in reverse order. Can you tell me if this works or not? Am I doing anything wrong here? This is my first time using a method of dynamic memory allocation so I need guidance please I use to use arrays for this type of situation but I want to break out of that old habit of programming, because I''d be wasting memory if I did not use all the array elements so I want alllocate memory as and when I need it. Oh yeah, if you are wondering why I have named the structure BloodList, it is because I am making a remake of the classic game "Snake" and when the snake crashes into a wall or itself I want its head to explode and leave a bloodstain on the floor. So on every collision the x,y position of the snake''s head is put into the linked List of BloodList. This is so when the screen is drawn the bloodstains of where the snake previously crashed will be drawn at the positions: (BloodStain.x, BloodStain.y) Also could you tell me if my method of creating the linked list is okay and could you suggest any improvements: void InsertNewBloodStain(int x, int y, BloodList *p) { if (p->next) { // if this node points to another one, it means // that this node is taken so visit the next one InsertNewBloodStain(x,y,p->next); } else { // node does not point to anything // insert position for new blood stain in list. p->x=x; p->y=y; // point to a new blood stain. p->next=new BloodList P->next=0; } } I hope this method works. I would really be greatful if someone could tell me if I am wrong or suggest any improvements. This is the first time I am using dynamic memory allocation so go easy on me. Thanks in advance. Dark Star

Share this post


Link to post
Share on other sites
Although your ClearList function will work, will delete all your list, you first have to go through the list. Though not lots of time to do.

How about this way... ???

void ClearList(BloodList *p)
{
BloodList *q;
while(p->next) {
q=p->next;
delete p;
p=q;
}
}

Short, to the point and clears as it goes.??

Share this post


Link to post
Share on other sites
The clear list is ok, but the recursion is not at all needed. If reverse deletion is not needed, something like this would work.

void ClearList(BloodList *p)
{
while (p->next)
{
BloodList *next = p->next;
delete p;
p = next;
}
}

As you can see, no recursion.

As far as the allocation goes, it is slow (but given the application, it doesn't look like it matters.) However, here are some alternatives:

1) Insert new entries at head of list instead of tail.

// Global
BloobList *firstblood = NULL;

void InsertNewBloodStain (int x, int y)
{
BloodList *p = new BloodList;
p ->x = x;
p ->y = y;
p ->next = firstblood;
firstblood = p;
}

2) Insert new entries at tail of list.

// Globals
BloodList *firstblood = NULL;
BloodList *lastblood = NULL;

void InsertNewBloodStain (int x, int y)
{
BloodList *p = new BloodList;
p ->x = x;
p ->y = y;
p ->next = NULL;
if (lastblood == NULL)
{
firstblood = lastblood = p;
}
else
{
lastblood ->next = p;
lastblood = p;
}
}

3) Finally, a non-recursive version of your original.

void InsertNewBloodStain (int x, int y, BloodList *p)
{
while (p ->next)
{
p = p ->next;
}
p->x=x;
p->y=y;
p->next=new BloodList;
P->next=0;
}

In versions 1 and 2, remember that ClearList would also need to reinitialize firstblood and lastblood back to NULL. Also, with versions 1 and 2, the list is not primed with a blank BloodList to mark the end of the list.

Tim


Edited by - timsmith on June 14, 2000 7:39:20 AM

Share this post


Link to post
Share on other sites
Found out how to do the source thing so make it look neater.

    
void ClearList(BloodList *p)
{
BloodList *q;
while(p->next) {
q=p->next;
delete p;
p=q;
}
}

Share this post


Link to post
Share on other sites