Deleting one node of single linked list use double pointers in C language

Question

I have been reading something related to C language's double pointers, and I have some doubts about the following piece of code. The following piece of code is about the operation of deleting a node of single linked list using double pointers in C language.

#include<stdio.h>
#include<stdlib.h>

struct ListNode
{
    int val;
    unsigned should_remove:1;
    struct ListNode* next;
};

struct ListNode* CreateList(int n)
{
    struct ListNode* node;
    struct ListNode* next_node = NULL;
    int i;
    for (i = n-1; i >= 0; --i) {
        node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = i;
        node->next = next_node;
        node->should_remove = i % 2;
        next_node = node;
    }
    return node;
}

void RemoveList(struct ListNode* head){
    struct ListNode* next;
    while(head) {
        next = head->next;
        free(head);
        head = next;
    }
}
int IsRemove(struct ListNode* node)
{
    return node->val == 4;
}
typedef int RemoveFn(struct ListNode*);

void PrintList(struct ListNode* head)
{
    while(head->next) {
        printf("%d, ", head->val);
        head = head->next;
    }
    if(head) printf("%d\n", head->val);
}

void RemoveIf3(struct ListNode** head, RemoveFn * Remove)
{
    struct ListNode** ptr_current_node  = head;
    struct ListNode* entry;
    while(*ptr_current_node) {
        entry = *ptr_current_node;
        if (Remove(entry)) {
            *ptr_current_node = entry->next;
            free(entry);
        } else {
            ptr_current_node = &entry->next;
        }
    }

}

int main()
{
    printf("test 3: ");
    struct ListNode* head3 = CreateList(10);
    struct ListNode** p = &head3;
    RemoveIf3(p, IsRemove);
    PrintList(*p);
    return 0;
}

And it can used gcc compile and run OK.

gcc test.c -o test

./test

However I change the func RemoveIf3 one line of code:

ptr_current_node = &entry->next;

to:

*ptr_current_node = entry->next;

and the function code will change like this:

void RemoveIf3(struct ListNode** head, RemoveFn * Remove)
{
    struct ListNode** ptr_current_node  = head;
    struct ListNode* entry;
    while(*ptr_current_node) {
        entry = *ptr_current_node;
        if (Remove(entry)) {
            *ptr_current_node = entry->next;
            free(entry);
        } else {
            *ptr_current_node = entry->next;
        }
    }

}

And it can be compile,but when we run it and will have a error:

Segmentation fault (core dumped)

the first if remove branch can use pointer like this: *ptr_current_node = entry->next;, why the other branch can not use double pointer such as this, what wrong with it?

Answer 1

Thanks for all people's good answers. And Based on these, I think maybe I understand the differences between the two operations.

*ptr_current_node = entry->next;

and

ptr_current_node = &entry->next;

I have drawn a diagram to illustrate the remove function RemoveIf3. And the 2nd, 3rd steps is my understand of the two different operation of points.

Answer 2

To make it more clear what happens within this function

void RemoveIf3(struct ListNode** head, RemoveFn * Remove)
{
    struct ListNode** ptr_current_node  = head;
    struct ListNode* entry;
    while(*ptr_current_node) {
        entry = *ptr_current_node;
        if (Remove(entry)) {
            *ptr_current_node = entry->next;
            free(entry);
        } else {
            *ptr_current_node = entry->next;
        }
    }

}

you may remove this redundant declaration

struct ListNode** ptr_current_node  = head;

and the function will look the following way

void RemoveIf3(struct ListNode** head, RemoveFn * Remove)
{
    struct ListNode* entry;
    while( *head != NULL ) {
        entry = *head;
        if (Remove(entry)) {
            *head = entry->next;
            free(entry);
        } else {
            *head = entry->next;
        }
    }
}

That is within the function the original pointer to the head node passed to the function indirectly through a pointer to it is being changed until it becomes equal to NULL.

So after exiting the function you get the pointer to the head node equal to NULL. And this null pointer is passed to the function PrintList which does not check whether a passed pointer is equal to NULL in the while loop. It uses the null pointer to access memory in the expression head->next that invokes undefined behavior.

void PrintList(struct ListNode* head)
{
    while(head->next) {
        printf("%d, ", head->val);
        head = head->next;
    }
    if(head) printf("%d\n", head->val);
}

In the source definition of the function RemoveIf3 the pointer to pointer ptr_current_node is reassigned to point to a pointer to the next node

ptr_current_node = &entry->next;

So the original pointer to the head node can be equal to NULL only when the list has one node which is deleted within the function due to this statement

*head = entry->next;

By the way as within the function PrintList the list is not changed its parameter should be declared with qualifier const. The function can look for example the following way

void PrintList( const struct ListNode *head )
{
    for ( ; head != NULL; head = head->next ) 
    {
        printf( head->next ? "%d, " : "%d\n", head->val );
    }
}

Also the function RemoveList should accept a pointer to the pointer to the head node. In this case indeed after calling the function the list will be empty. For example

void RemoveList( struct ListNode **head )
{
    for ( struct ListNode *current = *head; current != NULL; ) 
    {
        struct ListNode *next = current->next;
        free( current );
        current = next;
    }

    *head = NULL;
}

or

void RemoveList( struct ListNode **head )
{
    while ( *head ) 
    {
        struct ListNode *next = ( *head )->next;
        free( *head );
        *head = next;
    }
}

Answer 3

In the second version, you never change ptr_current_node. As such,

• ptr_current_node is always equal to head.
• ptr_current_node is always equal to caller's p.
• ptr_current_node is always equal to caller's &head3.
• *ptr_current_node is always equal to caller's head3.

You're always modifying the head pointer (*ptr_current_node aka head3), which means you eventually assign NULL to the head pointer, which means the list is always empty when the function returns (and the nodes that should still be in the list but aren't were never freed).

You had it right the first time.

---

While that's wrong, it's not the bug that causes the program to crash. While you didn't mean to remove every node from the entire list, doing so shouldn't cause the program to crash, and the memory leak is far too small to affect your program.

The bug that causes the program to crash is in PrintList: It doesn't check if the provided list is empty.

Fixed:

void PrintList(struct ListNode *node) {
   printf( "List:" );

   while ( node ) {
      printf( " %d", node->val );
      node = node->next;
   }

   printf( "\n" );
}