Thread: Linked lists and new/delete?

  1. #1
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964

    Linked lists and new/delete?

    Alot of the tutorials on linked lists that i have gone through lately, uses the new operator to allocate memory for a new node in the list, but never checks if the allocation failed, and they don't use the delete operator to clear the memory afterwards either, this includes the tut on cprogramming.com. Why is that? Is there a particular reason?

    Also, i've tried to make a loop to destroy a linked list of mine after usage, but i keep getting segmentation errors when i run it:

    Code:
    while(conductor != NULL)
    {
    	temp_conductor = conductor->next;
    	delete conductor;
    	conductor = temp_conductor;
    	conductor = conductor->next;
    }
    Conductor is the pointer i'm using to traverse the list, temp_conductor is a similar pointer that i'm using to temporarily hold the value of conductor while i delete the node conductor points to.

    My guess is that the line i've highlighted is giving me problems, rather than deleting conductor itself, i wan't to delete the node that conductor is pointing to, how would i go about this?

  2. #2
    Registered User nempo's Avatar
    Join Date
    Aug 2007
    Posts
    39
    Edit: I'm an idiot, removed my reply ;P.

    Check anons reply.
    Last edited by nempo; 08-10-2007 at 07:07 AM.

  3. #3
    Darkness Prevails Dark_Phoenix's Avatar
    Join Date
    Oct 2006
    Location
    Houston, Texas
    Posts
    174
    How about using a recursive function
    Code:
    void DestroyConductor( (type?) *conductor)
    {
        if (conductor->next)
            DestroyConductor(conductor->next);
        
        delete conductor;
    }
    Using Code::Blocks and Windows XP

    In every hero, there COULD be a villain!

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Or better not if you happen to have long lists...

    Just throw out the conductor = conductor->next as you seem to be advancing twice each iteration.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by anon View Post
    Or better not if you happen to have long lists...

    Just throw out the conductor = conductor->next as you seem to be advancing twice each iteration.
    What a stupid error, i threw out the "conductor = conductor->next" and i am no longer getting seg errors, but how can i be sure that i have deleted the entire list?

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Well, if conductor is initially set to head, the deletion of everything should be the logical outcome (or your list is incorrect anyway).

    There might be tools to check for memory leaks.

    You might also make a list of objects that count the instances and see if the count is 0 after the list gets destructed.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by anon View Post
    Well, if conductor is initially set to head, the deletion of everything should be the logical outcome (or your list is incorrect anyway).

    There might be tools to check for memory leaks.

    You might also make a list of objects that count the instances and see if the count is 0 after the list gets destructed.
    Well, i'm sure that my list is correct or otherwise the rest of my program wouldn't be working. Thanks for helping me out Anon

    Still, why isn't there anything about deleting a linked list in the FAQ?

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Prelude's tutorial in the FAQ here has a paragraph on deleting the memory (basically the same thing you do).

    Alot of the tutorials on linked lists that i have gone through lately, uses the new operator to allocate memory for a new node in the list, but never checks if the allocation failed, and they don't use the delete operator to clear the memory afterwards either, this includes the tut on cprogramming.com. Why is that? Is there a particular reason?
    It is quite annoying and complicated to check everything (new throws an exception, and you might need smart_pointers instead of regular ones to be safe), therefore most tutorials leave error-checking out to keep the focus on the issue at hand.

    Not freeing memory might result from just sloppiness.
    Last edited by anon; 08-10-2007 at 07:40 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  9. #9
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by anon View Post
    Prelude's tutorial in the FAQ here has a paragraph on deleting the memory (basically the same thing you do).
    Oh, i didn't realize that, never got around to checking Prelude's corner to be honest, anyways, thanks for the help.

  10. #10
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    Quote Originally Posted by Neo1 View Post
    Also, i've tried to make a loop to destroy a linked list of mine after usage, but i keep getting segmentation errors when i run it:

    Code:
    while(conductor != NULL)
    {
    	temp_conductor = conductor->next;
    	delete conductor;
    	conductor = temp_conductor;
    	conductor = conductor->next;
    }
    One problem with this code is you're calling delete on a pointer that you haven't checked to be NULL. You get a seg fault when you're at the last node in the list and calling delete on the next pointer which is NULL. Also, as pointed out, you're actually traversing 2 nodes each iteration which will cause memory leaks.

    Code:
    IF head != NULL
       WHILE head->next != NULL
           temp = head
           head = head->next
           delete temp
       END WHILE
       delete head
       head = NULL
    END IF
    Something like this I believe should work.
    Last edited by MacNilly; 08-11-2007 at 03:26 PM.

  11. #11
    Registered User
    Join Date
    Oct 2001
    Posts
    62
    One problem with this code is you're calling delete on a pointer that you haven't checked to be NULL.
    No, he doesn't. Due to the while() condition variable 'conductor' cannot be null when delete is called.

    You get a seg fault when you're at the last node in the list and calling delete on the next pointer which is NULL.
    No he doesn't, deleting null pointers is safe.

    The real problem with this code is:

    Code:
    while(conductor != NULL)
    {
      temp_conductor = conductor->next; /* If temp_conductor becomes NULL... */
      delete conductor;                 /* (delete works anyway) */
      conductor = temp_conductor;       /* conductor becomes NULL too... */
      conductor = conductor->next;      /* so 'conductor->next' = (null)->next = seg fault */
    }

  12. #12
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    Quote Originally Posted by rpet View Post
    No, he doesn't. Due to the while() condition variable 'conductor' cannot be null when delete is called.



    No he doesn't, deleting null pointers is safe.

    The real problem with this code is:

    Code:
    while(conductor != NULL)
    {
      temp_conductor = conductor->next; /* If temp_conductor becomes NULL... */
      delete conductor;                 /* (delete works anyway) */
      conductor = temp_conductor;       /* conductor becomes NULL too... */
      conductor = conductor->next;      /* so 'conductor->next' = (null)->next = seg fault */
    }
    Yup, you're right on all counts. I had a brain fart. Be leery of that pseudo-code for deleting a linked list I posted, I haven't tested it.

  13. #13
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    If you have valgrind on your system, you can run
    Code:
    valgrind main
    To detect memory leaks.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. New/delete vs malloc/free
    By KBriggs in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2009, 03:08 PM
  2. Overriding operator new/delete?
    By Elysia in forum C++ Programming
    Replies: 13
    Last Post: 02-25-2008, 12:10 PM
  3. Replies: 6
    Last Post: 09-14-2006, 10:46 PM
  4. overloading new/delete
    By DavidP in forum C++ Programming
    Replies: 13
    Last Post: 07-02-2004, 08:17 AM
  5. new/delete problems, please help
    By btq in forum C++ Programming
    Replies: 9
    Last Post: 06-07-2002, 11:23 AM