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?

Why are you using a ** at all here. It's not necessary. All I can think of it that you're doing it to allow you to change the head node, but that isn't really a clean way of doing it. A better way is to introduce a list struct, which has a head (an optional additional data like tail and size). Then you don't need (or want) to pass around ListNode** or try to use double pointers to update the head pointer. — Gabe Sechan
– Gabe Sechan, Commented Dec 31, 2024 at 5:50
Additionally, using a ** trick like this can be dangerous. Let's say I store a struct ListNode * myList, and create a list in that variable. Now let's say I also store it in another variable myOtherList. Same list, same pointer held in two variables. If I try to update the head by using a trick of **, it will update only one of the two- the one I pass in. The other will maintain the old value. Which is why using ** like this is a bad idea. — Gabe Sechan
– Gabe Sechan, Commented Dec 31, 2024 at 5:55
@Gabe Sechan, Re "Why are you using a ** at all here. It's not necessary.", It's necessary to remove the head. /// Re "All I can think of it that you're doing it to allow you to change the head node, but that isn't really a clean way of doing it.", Quite the contrary. I consider all the baggage of a entire additional struct to be the messy way. — ikegami
– ikegami, Commented Dec 31, 2024 at 7:06
@Gabe Sechan, Re "Let's say I store a struct ListNode * myList", This is a manufactured problem. The caller shouldn't be the one creating the node. That's an internal detail. The value to be stored should be what's passed to the function. There's no reason for the node to be anything but an opaque type to the caller. — ikegami
– ikegami, Commented Dec 31, 2024 at 7:07
Tip: struct ListNode** p = &head3; RemoveIf3(p, IsRemove); is a complicated and confusing way of writing RemoveIf3(&head3, IsRemove); — ikegami
– ikegami, Commented Dec 31, 2024 at 7:13

ikegami · Accepted Answer · 2024-12-31 15:50:54Z

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

Vlad from Moscow · Accepted Answer · 2024-12-31 17:44:00Z

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

user3034702 · Accepted Answer · 2025-01-02 07:04:23Z

0

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.

answered Jan 2 at 7:04

user3034702

711 gold badge1 silver badge3 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related