# Whats wrong with this linked list?

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

## 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 on other sites
Is this any better?

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

##### 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 on other sites
 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 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 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 on other sites
Quote:
 Original post by DosproOk, 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 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 on other sites
Quote:
 Original post by ZahlmanDeleting 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!

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 14
• 14
• 45
• 22
• 27
• ### Forum Statistics

• Total Topics
634042
• Total Posts
3015204
×