Delete a node from singly linked list in C

Question

I have been struggling with the program below for a couple of days to figure it out:

void *delete_from_list(struct node** list, int n)
{
    struct node *entry = *list;
    while (entry) {
        if (entry->value == n) {
            *list = entry->next;
            free(entry);
        }
        list = &entry->next;
        entry = entry->next;
    }
}

I understand up to the line free(entry);. I, however, can't grasp the last two lines. From my understanding, with this line list = &entry->next the address of entry->next is assigned to a double pointer list, and with the next line entry points to the next node. But if free(entry) releases the block of memory that entry points to, it seems to me that entry wouldn't point anywhere. Hence, entry->next would appear to point nowhere, either. If so, the line entry = entry->next; wouldn't make sense to me.

Does this answer your question? [delete node(s) in a singly linked list in c](https://stackoverflow.com/questions/70194184/delete-nodes-in-a-singly-linked-list-in-c) — Gaurav Pathak, May 03 '23 at 12:11
Can you show how this is used in a [mcve]? It seems odd for more than the reason you've asked about. It also isn't return a value where the signature says it should. — Retired Ninja, May 03 '23 at 12:19
What gives you the assumption the code does not have a use after free error? It seems to me that the code has a use after free error, but still "works" because the value is not overwritten till it is used. — 12431234123412341234123, May 03 '23 at 12:24
Maybe you should look at [What is the pointer-to-pointer technique for the simpler traversal of linked lists?](https://stackoverflow.com/q/3182733/15168) and [An interesting C linked list idiom](https://stackoverflow.com/q/332441/15168). — Jonathan Leffler, May 03 '23 at 16:03

Yves Daoust · Answer 1 · 2023-05-03T12:28:46.040

3

You are right, this code is invalid. The subsequent accesses to entry are explicitly UB in C11.

The reason it can work is because free does not "destroy" memory so that the variable would point "to nowhere". In fact the memory block is left unchanged and just marked as available for a future reallocation. So as long as there are no calls to malloc, the data could still be there "by chance".

edited May 03 '23 at 12:28

answered May 03 '23 at 12:21

Yves Daoust

672
9

Since `entry` still points to the same address after `free(entry);`, `list = &entry->next;` and `entry = entry->next;` work? – Fary May 03 '23 at 12:57
@Fary: is my answer unclear ? UB ! – Yves Daoust May 03 '23 at 13:25
(UB means Undefined Behaivor) – erik258 May 04 '23 at 15:52

score 1 · Answer 2 · answered May 03 '23 at 13:34

Since entry still points to the same address after free(entry);, list = &entry->next; and entry = entry->next; work?

It might, or might not. The code invokes undefined behaviour. Behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which the C International Standard imposes no requirements.

ikegami · Answer 3 · 2023-05-03T17:13:17.070

You are correct. The code makes no sense. Or, to put it in technical terms, it invokes undefined behaviour.

It does so for the reason you gave, and because the function returns nothing even though it claims to return a void *.

This is how the buggy code could be fixed:

void delete_from_list( struct node** list, int n ) {
   while ( *list ) {
      if ( ( *list )->value == n ) {
         struct node tmp = *list;
         *list = ( *list )->next;
         free( tmp );
      } else {
         list = &( ( *list )->next );
      }
   }
}

Delete a node from singly linked list in C

3 Answers3