Thread: Freeing a random node from a linked list

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.

Originally Posted by Salem

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
 }
}

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:

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

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, ... );