?
Solved

deleting from singly linked list: free()

Posted on 2005-03-26
33
Medium Priority
?
299 Views
Last Modified: 2010-04-15
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;
}
0
Comment
Question by:luna621
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 19
  • 9
  • 5
33 Comments
 
LVL 15

Expert Comment

by:efn
ID: 13637287
The appropriate point to free a record is when you don't need it any more.  When control leaves the while loop, you know that curr is NULL, so it makes no sense to free it, and you don't know that you don't need either prev or temp.  So none of those free calls seems useful.

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.
0
 

Author Comment

by:luna621
ID: 13637824
So, within this:


        if(strcmp(name, curr -> name) == 0)
        {
            if(prev == curr)
            {
                /* REMOVE HEAD */
                *start = curr -> next;
                free(curr); <---------------- there???
            }
            else
            {
                /* remove CURR */
                ...
       }
0
 

Author Comment

by:luna621
ID: 13637838
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);
            }
            ...
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

Author Comment

by:luna621
ID: 13637845
I did the same thing with the else statement.  The program seems to be running ok...
0
 
LVL 15

Expert Comment

by:efn
ID: 13637883
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.
0
 

Author Comment

by:luna621
ID: 13638119
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;
}
0
 

Author Comment

by:luna621
ID: 13638137
Actually, I take that back.  It's missing the 2ND item in the list.
0
 

Author Comment

by:luna621
ID: 13638157
Oops!  Nevermind.  It was skipping the 1ST item in the list.
0
 

Author Comment

by:luna621
ID: 13638237
It also crashes when the last item in the list is removed.
0
 
LVL 15

Assisted Solution

by:efn
efn earned 400 total points
ID: 13638254
In the case where it removes the first thing in the list, it advances curr to the second thing.  Then the code after the if statement advances it again, so the second element doesn't get examined.  After you fix this, you may find you can factor some code out of the blocks of the if statement.  This factoring is not required for correctness; it would just be a tightening or polishing step.

Another problem:  It detects the special case of being at the head of the list by checking for prev == curr.  When it removes the first element, it leaves curr pointing to the old second element, now the first element, but it leaves prev pointing to the old, deleted first element.  Therefore, even though it is still on the (new) first node in the list, when it comes through the loop again, it will not detect this, because curr will not be == prev, so it will not do the right head-of-the-list special-case thing.

Those are the only remaining problems I see.
0
 

Author Comment

by:luna621
ID: 13638262
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?
0
 
LVL 15

Expert Comment

by:efn
ID: 13638277
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.
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 13638291
> 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
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 13638294
ooops ... sorry ... I had the window open for a long time
0
 

Author Comment

by:luna621
ID: 13638307
>>  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.
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 13638312
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
0
 

Author Comment

by:luna621
ID: 13638313
>>  errr ... do you plan to remove all nodes which match name ?

Yes, all names that match will be deleted.
0
 

Author Comment

by:luna621
ID: 13638316
>> 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: ");
...
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 13638319
ok, just make sure that start is not NULL whenever a call  to delete is made
0
 

Author Comment

by:luna621
ID: 13638329
>> > 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
            {
            ...
0
 

Author Comment

by:luna621
ID: 13638332
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 */
...
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 13638335
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

0
 

Author Comment

by:luna621
ID: 13638336
>> 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.
0
 

Author Comment

by:luna621
ID: 13638338
>> ok, your current code is correct

Not quite.  It's still skipping the 2nd item in the list.
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 13638341
You mean not deleting first and second nodes when both are identical?
0
 

Author Comment

by:luna621
ID: 13638375
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
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 13638379
0
 

Author Comment

by:luna621
ID: 13638391
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...
0
 
LVL 45

Accepted Solution

by:
sunnycoder earned 1600 total points
ID: 13638398
       if(strcmp(name, curr -> name) == 0)
        {
            if(prev == curr)
            {
                /* remove first item in list */
                temp = curr;
                *start = curr -> next;
                curr = *start;
                free(temp);
                prev=curr;       >>>>> add these two lines
                continue;
            }
0
 
LVL 15

Expert Comment

by:efn
ID: 13638412
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.
0
 

Author Comment

by:luna621
ID: 13638418
OMG!!  It worked.  Hold on, let me test it in UNIX really quick :D
0
 

Author Comment

by:luna621
ID: 13638432
sunnycoder, you're the best :D
And, thank you too efn for helping!!

Points distributed!!
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 13638438
thanks :-)
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
Suggested Courses
Course of the Month10 days, 8 hours left to enroll

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question