Whats wrong with this linked list?

Started by
7 comments, last by iMalc 18 years, 10 months ago
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?
Advertisement
Is this any better?

for(temp=r_list; temp!=NULL; temp=temp->next)
{
temp2 = temp->next;
free(temp);
temp = temp2
}
.
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;}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                                                          
Looking for video game music? Check out some of my samples at http://www.youtube.c...ser/cminortunes            
                                                          
I'm currently looking to create music for a project, if you are interested e-mail me at cminortunes@gmail.com    
                                                          
Please only message me for hobby projects, I am not looking to create music for anything serious.
[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?

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.
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.
Ok, what i tried was to free the memory but starting at the end instead of at the beginning.
Thanks for your help.
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].
"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms
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.)
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!
"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

This topic is closed to new replies.

Advertisement