Jump to content
  • Advertisement
Sign in to follow this  
Dospro

Whats wrong with this linked list?

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

Hi. I have a little problem, i made alinked list dinamycally, and now i want to free all the memory used. I use this: while(r_list!=NULL) { for(temp=r_list, temp2=r_list; temp!=NULL; temp=temp->next) { temp2=temp; } free(temp2); temp2=NULL; } but it crashes here, do you know whats the problem?

Share this post


Link to post
Share on other sites
Advertisement
Is this any better?

for(temp=r_list; temp!=NULL; temp=temp->next)
{
temp2 = temp->next;
free(temp);
temp = temp2
}

Share this post


Link to post
Share on other sites
You're not deleting the entire list, you're just deleting one i believe.

You have to delete every one sequentially, and you're just storing each node into a temp, and when temp2 is the last node, you free the last node.

should probably be

temp = headNode;
temp2 = NULL;

while(temp)
{
temp2 = temp->next;
delete temp;
temp = temp2;
}


Share this post


Link to post
Share on other sites
[edit] Whoa I type slow... And why does the quote tag not work for me...[headshake]

Original post by Dospro
Hi. I have a little problem, i made alinked list dinamycally, and now i want to free all the memory used.
I use this:

while(r_list!=NULL)
{
for(temp=r_list, temp2=r_list; temp!=NULL; temp=temp->next)
{
temp2=temp;
}
free(temp2);
temp2=NULL;
}


but it crashes here, do you know whats the problem?[/quote]

Well the design of a linked list will have something done such as:

[Node1]->[Node2]->[Node3]->['\0']

So I don't know what your algorithm does really. If you are simply wanting to transverse a linked list and free memory, you will want to do something such as this:

while(r_list!=NULL)
{
temp = r_list->next;
free(r_list)
r_list = temp;
}






And that's it [wink]

The process is that you start with the first node and store the next node. You then free the first node, then set that node's pointer to the stored next one. That way, the list get's advanced until the end. So here's a visual of it:

// Original: r_list = [Node1]
[Node1]->[Node2]->[Node3]->['\0']

// temp = r_list->next;
// r_list = [Node1]
[Node1]->[Node2]->[Node3]->['\0']
[Temp]->[Node2]

// free(r_list)
// r_list = NULL
[Node2]->[Node3]->['\0']
[Temp]->[Node2]

// r_list = temp;
[Node2]->[Node3]->['\0']


Then the same thing is done again, effectively rremoving Node2, then Node3, then the loop is done when NULL is reached.

Share this post


Link to post
Share on other sites
Personally, I always found it neater to make the "remove one link from the list" function first.

Destroy the list then becomes something like:


while(list){
list->remove(begin());
}


Nice and neat.

Share this post


Link to post
Share on other sites
Ok, what i tried was to free the memory but starting at the end instead of at the beginning.
Thanks for your help.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dospro
Ok, what i tried was to free the memory but starting at the end instead of at the beginning.
Thanks for your help.
You easily can do exactly that, by writing it recursively:

void clear(node *&r_list)
{
if (r_list != NULL)
{
clear(r_list->next);
delete r_list;
r_list = NULL;
}
}
However, it is better to not involve recursion because that uses more stack space, and is therefore slightly slower, and (worst of all) prone to stack overflow errors.

[smile]Use Drew_Benton's code[smile].

Share this post


Link to post
Share on other sites
Deleting from end to front will be much slower - nothing to do with recursion; it's traversing the whole (remaining) list for each removal, which makes it a needlessly O(n^2) algorithm (in classic Shlemiel the Painter fashion).

The original code had the right steps for the intended algorithm (go to back of list for each removal, and then remove), but had problems:

1) The traversal to the end goes one step too far; temp2 ends up pointing at the last element and temp ends up pointing at NULL.

2) Then, temp2 is deleted (it should be temp, except that it's gone one too far), but the node before temp2 doesn't get its next pointer nulled out. Therefore, the next time through, the iteration comes to the same spot - except the last node has already been freed, and kaboom.

One reasonable solution is Drew's. Another much better idea (in C++) is to use std::list :D (although calls to free() suggest use of plain C which would prevent that option.)

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Deleting from end to front will be much slower - nothing to do with recursion; it's traversing the whole (remaining) list for each removal, which makes it a needlessly O(n^2) algorithm (in classic Shlemiel the Painter fashion).
Um, I hope that sentence wasn't in response to the code I posted, because that would be quite a blunder to claim what I posted was an O(n^2) operation.

The recursive solution I posted is indeed only slower because of the fact that it is recursive, and thus uses more stack space, meaning more potential for more cache misses etc.

More caffiene huh Zahlman!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!