Thread: Freeing a random node from a linked list

  1. #1
    Registered User
    Join Date
    Oct 2019
    Posts
    82

    Freeing a random node from a linked list

    I'm struggling with freeing a random node in a singly linked list.

    With my current code below, if a random node happens to be freed, it will discontinue the list splitting it into two part and the second part gets lost. I am not exactly sure how to proceed. Could someone help?

    Code:
    void traverse(struct n *head, 
            void (*callback_func)(void *user_data, int *free_flag))
    {
      struct n *p;
    
    
      for (p = head; p; p = p->next)    {
        (*callback_func)(p->user_data, p->f);
        if (p->f)           // If they want to free the node, do that
            free(p);
      }
    }
    Any help is appreciated.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    So where in your code do you take care of the following

    Linked list - Wikipedia
    If you delete the first node, you have a new head.
    If you delete a node in the middle, you need to then make prev->next = this->next.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Oct 2019
    Posts
    82
    Quote Originally Posted by Salem View Post
    So where in your code do you take care of the following

    Linked list - Wikipedia
    If you delete the first node, you have a new head.
    If you delete a node in the middle, you need to then make prev->next = this->next.
    I came up with this but are not sure it is right:

    Code:
    void traverse(struct n *head,
           void (*callback_func)(void *user_data, int *free_flag))
    {
     struct n *p, prev = NULL;
    
    
     for (p = head; p; p = p->next)    {
       (*callback_func)(p->user_data, p->f);
       if (p->f){
               if (p == head)
                {
                        head = p->next;
                        free(p);
                } else
                {
                        prev->next = p->next;
                        free(p);
                }
                continue;
        }
        prev = p;          // If they want to free the node, do that
     }
    }
    Last edited by ghoul; 01-26-2022 at 01:16 AM. Reason: code formating

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Why do your nodes have a member named f that appears to function as a "free flag"?

    I would expect that the callback function would set this flag (or not) when called, thus indicating that the node should be freed, but this can be done with a local free flag, e.g.,
    Code:
    void traverse(struct n *head, void (*callback_func)(void *user_data, int *free_flag))
    {
        struct n *p, prev = NULL;
        int free_flag;
    
        for (p = head; p; p = p->next)
        {
            free_flag = 0;
            callback_func(p->user_data, &free_flag);
            if (free_flag)
            {
                if (p == head)
                {
                    head = p->next;
                    free(p);
                }
                else
                {
                    prev->next = p->next;
                    free(p);
                }
                continue;
            }
            prev = p;
        }
    }
    You seem to have a "use after free" problem though. Notice that you call free(p), but before the next assignment to p, control goes to p = p->next, i.e., dereferencing p even though it has been freed.

    There's also a typo here:
    Code:
    struct n *p, prev = NULL;
    The above declares p to be of type pointer to struct n, and also declares prev to be of type struct n, but you want it to be pointer to struct n. Hence:
    Code:
    struct n *p, *prev = NULL;
    Actually, this should have led to a compile error. Which means that when you say this:
    Quote Originally Posted by ghoul
    I came up with this but are not sure it is right:
    Come on, at least try to compile your code before asking for help. I haven't bothered to compile my modified version of your code since you haven't bothered either, so any compile errors are entirely your fault (even if I introduced it ).
    Last edited by laserlight; 01-26-2022 at 05:17 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Also, if you change the head, you need to return it.

    Any function which modifies the list should typically be of the form
    struct n *traverse(struct n *head, ...

    which ultimately results in
    return head;


    And your caller becomes
    head = traverse(head, ... );
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Oct 2019
    Posts
    82
    Quote Originally Posted by laserlight View Post
    You seem to have a "use after free" problem though. Notice that you call free(p), but before the next assignment to p, control goes to p = p->next, i.e., dereferencing p even though it has been freed.
    Thanks for spotting that. I actually have more such in the code.


    Quote Originally Posted by laserlight View Post
    Come on, at least try to compile your code before asking for help. I haven't bothered to compile my modified version of your code since you haven't bothered either, so any compile errors are entirely your fault (even if I introduced it ).
    Sorry, I did not compile this yes because my code does not compile yet o.O

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need help freeing a linked list
    By Muster Mark in forum C Programming
    Replies: 2
    Last Post: 06-14-2011, 05:24 PM
  2. Freeing a linked list
    By Matty_Alan in forum C++ Programming
    Replies: 4
    Last Post: 04-17-2010, 11:19 PM
  3. Replies: 0
    Last Post: 09-16-2008, 05:04 AM
  4. Freeing a linked list
    By CeeCee in forum C++ Programming
    Replies: 7
    Last Post: 02-02-2002, 05:59 PM
  5. Replies: 5
    Last Post: 10-04-2001, 03:42 PM

Tags for this Thread