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.

Answer 1

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

Answer 2

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.

Answer 3

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