1. ## 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. So where in your code do you take care of the following

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.

3. Originally Posted by Salem
So where in your code do you take care of the following

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){
{
free(p);
} else
{
prev->next = p->next;
free(p);
}
continue;
}
prev = p;          // If they want to free the node, do that
}
}```

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

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