luna621
asked on
deleting from singly linked list: free()
Hello,
I had this code, and it ran nicely before. But, when I added the free(prev), free(curr), & free(temp) statements I get these funny looking characters printed to the screen. And, it looks like it's printing data from a random place in the stack/heap. Maybe I'm not "freeing" in the right place? Thank you!
Here's my code:
--------------------------
int deleteRecord(struct record ** start, char name[])
{
struct record *curr = *start;
struct record *prev = *start;
struct record *temp;
while(curr != NULL)
{
if(strcmp(name, curr -> name) == 0)
{
if(prev == curr)
{
/* REMOVE HEAD */
*start = curr -> next;
}
else
{
/* remove CURR */
temp = curr;
prev -> next = curr -> next;
curr = curr -> next;
/* goto top again */
continue;
}
}
prev = curr;
curr = curr -> next;
} /* end while */
free(prev); /* <---------- here's what's giving me all the problems */
free(curr);
free(temp);
return 0;
}
I had this code, and it ran nicely before. But, when I added the free(prev), free(curr), & free(temp) statements I get these funny looking characters printed to the screen. And, it looks like it's printing data from a random place in the stack/heap. Maybe I'm not "freeing" in the right place? Thank you!
Here's my code:
--------------------------
int deleteRecord(struct record ** start, char name[])
{
struct record *curr = *start;
struct record *prev = *start;
struct record *temp;
while(curr != NULL)
{
if(strcmp(name, curr -> name) == 0)
{
if(prev == curr)
{
/* REMOVE HEAD */
*start = curr -> next;
}
else
{
/* remove CURR */
temp = curr;
prev -> next = curr -> next;
curr = curr -> next;
/* goto top again */
continue;
}
}
prev = curr;
curr = curr -> next;
} /* end while */
free(prev); /* <---------- here's what's giving me all the problems */
free(curr);
free(temp);
return 0;
}
ASKER
So, within this:
if(strcmp(name, curr -> name) == 0)
{
if(prev == curr)
{
/* REMOVE HEAD */
*start = curr -> next;
free(curr); <---------------- there???
}
else
{
/* remove CURR */
...
}
if(strcmp(name, curr -> name) == 0)
{
if(prev == curr)
{
/* REMOVE HEAD */
*start = curr -> next;
free(curr); <---------------- there???
}
else
{
/* remove CURR */
...
}
ASKER
Okay, fixed it. How about this?
struct record *temp;
...
if(strcmp(name, curr -> name) == 0)
{
if(prev == curr)
{
/* remove first item in list */
temp = curr;
*start = curr -> next;
curr = *start;
free(temp);
}
...
struct record *temp;
...
if(strcmp(name, curr -> name) == 0)
{
if(prev == curr)
{
/* remove first item in list */
temp = curr;
*start = curr -> next;
curr = *start;
free(temp);
}
...
ASKER
I did the same thing with the else statement. The program seems to be running ok...
It's probably better, but may not be completely right yet. Try testing it with a list where the first three records are all to be deleted. Or post the code and the experts can inspect it.
ASKER
Ah, it seems to be skipping the first record... here's the code:
int deleteRecord(struct record ** start, char name[])
{
struct record *curr = *start;
struct record *prev = *start;
struct record *temp;
while(curr != NULL)
{
if(strcmp(name, curr -> name) == 0)
{
if(prev == curr)
{
/* remove first item in list */
temp = curr;
*start = curr -> next;
curr = *start;
free(temp);
}
else
{
/* remove CURR */
temp = curr;
prev -> next = curr -> next;
curr = curr -> next;
free(temp);
/* goto top again */
continue;
}
}
prev = curr;
curr = curr -> next;
} /* end while */
return 0;
}
int deleteRecord(struct record ** start, char name[])
{
struct record *curr = *start;
struct record *prev = *start;
struct record *temp;
while(curr != NULL)
{
if(strcmp(name, curr -> name) == 0)
{
if(prev == curr)
{
/* remove first item in list */
temp = curr;
*start = curr -> next;
curr = *start;
free(temp);
}
else
{
/* remove CURR */
temp = curr;
prev -> next = curr -> next;
curr = curr -> next;
free(temp);
/* goto top again */
continue;
}
}
prev = curr;
curr = curr -> next;
} /* end while */
return 0;
}
ASKER
Actually, I take that back. It's missing the 2ND item in the list.
ASKER
Oops! Nevermind. It was skipping the 1ST item in the list.
ASKER
It also crashes when the last item in the list is removed.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Okay, I rebooted my computer and different things are happening. Maybe I have too much stuff running at the same time. I posted my code here: http://www2.hawaii.edu/~fklam/C/
I left everything the way it was. I guess you'll have to run it and see what happens (since it's been doing different things for me). I think I need to add something to the deleteRecord() to catch the last item deletion... any ideas?
I left everything the way it was. I guess you'll have to run it and see what happens (since it's been doing different things for me). I think I need to add something to the deleteRecord() to catch the last item deletion... any ideas?
I don't see any problem specific to the last record. You might want to check that the list is properly terminated with a null next pointer in the last record.
Otherwise, I suggest you fix the two problems I pointed out in my preceding comment and see how that works.
Otherwise, I suggest you fix the two problems I pointed out in my preceding comment and see how that works.
> if(prev == curr)
you can take this out of the loop ... Just add a check in the beginning to see if *start->name is same as name.
Also you are not checking if char ** start given to you is NULL or not
Now on to the error in your function
assume something like
A -> B -> C -> ...
and we wish to delete A
curr=A
prev=A
name=A
if(strcmp(name, curr -> name) == 0) >>>>> true
{
if(prev == curr) >>>>> true
{
/* remove first item in list */
temp = curr; >>>>>> temp=A
*start = curr -> next; >>>>>> *start=B
curr = *start; >>>>>> curr=B
free(temp); >>>>>>> free A
}
...
prev = curr; >>>>>>>> prev = B
curr = curr -> next; >>>>>>> curr = C
so you would never be examining B .... errr ... do you plan to remove all nodes which match name ? If names are unique then you do not have to traverse the whole list ... you can simply return after a deletion
you can take this out of the loop ... Just add a check in the beginning to see if *start->name is same as name.
Also you are not checking if char ** start given to you is NULL or not
Now on to the error in your function
assume something like
A -> B -> C -> ...
and we wish to delete A
curr=A
prev=A
name=A
if(strcmp(name, curr -> name) == 0) >>>>> true
{
if(prev == curr) >>>>> true
{
/* remove first item in list */
temp = curr; >>>>>> temp=A
*start = curr -> next; >>>>>> *start=B
curr = *start; >>>>>> curr=B
free(temp); >>>>>>> free A
}
...
prev = curr; >>>>>>>> prev = B
curr = curr -> next; >>>>>>> curr = C
so you would never be examining B .... errr ... do you plan to remove all nodes which match name ? If names are unique then you do not have to traverse the whole list ... you can simply return after a deletion
ooops ... sorry ... I had the window open for a long time
ASKER
>> I don't see any problem specific to the last record.
What I meant was if there's only one record in the list. If I try to delete it, the program crashes.
What I meant was if there's only one record in the list. If I try to delete it, the program crashes.
You need to add special check at the beginning of your program to check it ...
> if(prev == curr)
you can take this out of the loop ... Just add a check in the beginning to see if *start->name is same as name.
Also you are not checking if char ** start given to you is NULL or not
> if(prev == curr)
you can take this out of the loop ... Just add a check in the beginning to see if *start->name is same as name.
Also you are not checking if char ** start given to you is NULL or not
ASKER
>> errr ... do you plan to remove all nodes which match name ?
Yes, all names that match will be deleted.
Yes, all names that match will be deleted.
ASKER
>> Also you are not checking if char ** start given to you is NULL or not
I do, it's in the UI.c
...
if(start != NULL)
{
printf("\nPlease enter first and last name separated by a space.\n"
"Type $ when you are done: ");
...
I do, it's in the UI.c
...
if(start != NULL)
{
printf("\nPlease enter first and last name separated by a space.\n"
"Type $ when you are done: ");
...
ok, just make sure that start is not NULL whenever a call to delete is made
ASKER
>> > if(prev == curr)
>>you can take this out of the loop ... Just add a check in the beginning to see if *start->name is same as name.
Isn't that what I'm doing? Since curr is pointing to start, it's checking to see if the names are the same. I did the (prev == curr) to see if they're pointing to the same node.
struct record *curr = *start;
struct record *prev = *start;
...
if(strcmp(name, curr -> name) == 0) >>>>> true
{
if(prev == curr) >>>>> true
{
...
>>you can take this out of the loop ... Just add a check in the beginning to see if *start->name is same as name.
Isn't that what I'm doing? Since curr is pointing to start, it's checking to see if the names are the same. I did the (prev == curr) to see if they're pointing to the same node.
struct record *curr = *start;
struct record *prev = *start;
...
if(strcmp(name, curr -> name) == 0) >>>>> true
{
if(prev == curr) >>>>> true
{
...
ASKER
Okay, my while loop currently looks like this:
...
while(curr != NULL)
{
if(strcmp(name, curr -> name) == 0)
{
if(prev == curr)
{
/* remove first item in list */
temp = curr;
*start = curr -> next;
curr = *start;
prev = *start;
free(temp);
}
else
{
/* remove CURR */
temp = curr;
prev -> next = curr -> next;
curr = curr -> next;
free(temp);
/* goto top again */
continue;
}
}
prev = curr;
curr = curr -> next;
} /* end while */
...
...
while(curr != NULL)
{
if(strcmp(name, curr -> name) == 0)
{
if(prev == curr)
{
/* remove first item in list */
temp = curr;
*start = curr -> next;
curr = *start;
prev = *start;
free(temp);
}
else
{
/* remove CURR */
temp = curr;
prev -> next = curr -> next;
curr = curr -> next;
free(temp);
/* goto top again */
continue;
}
}
prev = curr;
curr = curr -> next;
} /* end while */
...
yeah but this check is in the while loop ... since it can occur only once, why not have it outside loop ...
But oh, your first two elements could be identical since you have non-unique list ... ok, your current code is correct
But oh, your first two elements could be identical since you have non-unique list ... ok, your current code is correct
ASKER
>> assume something like
>>
>> A -> B -> C -> ...
>> and we wish to delete A
Okay, now let's say there is this list:
A
I want to delete A. However, I think the program doesn't handle that. Maybe it's just a Visual .NET thing. I'll test it in UNIX.
>>
>> A -> B -> C -> ...
>> and we wish to delete A
Okay, now let's say there is this list:
A
I want to delete A. However, I think the program doesn't handle that. Maybe it's just a Visual .NET thing. I'll test it in UNIX.
ASKER
>> ok, your current code is correct
Not quite. It's still skipping the 2nd item in the list.
Not quite. It's still skipping the 2nd item in the list.
You mean not deleting first and second nodes when both are identical?
ASKER
If I have:
John Smith <--------- get's deleted
bfdjk
dnsjukn
vsjk
njks
John Smith <--------- DOES NOT get's deleted
fbjsksdb
nvsdjk
vdsnjk
John Smith <--------- get's deleted
fbajk
vns
vsdnj
John Smith <--------- get's deleted
bfdjk
dnsjukn
vsjk
njks
John Smith <--------- DOES NOT get's deleted
fbjsksdb
nvsdjk
vdsnjk
John Smith <--------- get's deleted
fbajk
vns
vsdnj
ASKER
I know my error is here:
else
{
/* remove CURR */
temp = curr;
prev -> next = curr -> next;
curr = curr -> next;
free(temp);
/* goto top again */
continue;
}
}
prev = curr;
curr = curr -> next; <------------ this is moving curr over to the next node, so (prev == curr) will never occur again. I don't know how to fix this...
else
{
/* remove CURR */
temp = curr;
prev -> next = curr -> next;
curr = curr -> next;
free(temp);
/* goto top again */
continue;
}
}
prev = curr;
curr = curr -> next; <------------ this is moving curr over to the next node, so (prev == curr) will never occur again. I don't know how to fix this...
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Back at 08:35PM PST, I pointed out two defects. You have fixed the second one; the first one is still there in your latest code.
To review: If you have nodes A -> B -> C and delete A, after the deletion, curr points to B, then after the if blocks, curr gets advanced to point to C, so B is never checked, so it never gets deleted, even if it should be.
This would account for the second node not getting deleted when the first one is. It would also account for problems with a one-node list. The if block would delete A and leave curr with a null value. Then the code after the if blocks would blow up when it tries to evaluate curr->next when curr is null.
To review: If you have nodes A -> B -> C and delete A, after the deletion, curr points to B, then after the if blocks, curr gets advanced to point to C, so B is never checked, so it never gets deleted, even if it should be.
This would account for the second node not getting deleted when the first one is. It would also account for problems with a one-node list. The if block would delete A and leave curr with a null value. Then the code after the if blocks would blow up when it tries to evaluate curr->next when curr is null.
ASKER
OMG!! It worked. Hold on, let me test it in UNIX really quick :D
ASKER
sunnycoder, you're the best :D
And, thank you too efn for helping!!
Points distributed!!
And, thank you too efn for helping!!
Points distributed!!
thanks :-)
Inside the loop, when the test
if(strcmp(name, curr -> name) == 0)
is true, you know you are going to remove a node from the list. That is the time to free that one node.