Is using free(p->next) acceptable in C?

Question

I'm working on solving a simple algorithm problem, and here's the question.

In a singly linked list L with a head node, delete all nodes with the value x and free their space. Assume that nodes with the value x are not unique, and try to write an algorithm to achieve the above operation.

I think the problem is quite simple; it only requires two pointers, one P and one L. L is used to traverse the nodes and check if the node's value is equal to the input value, while P points to the predecessor node of L. When a node with the same value as the input (let's say Y) is found, you just need to link the P node to the node after Y and then free Y.

then This is my codes:

void deleteX(int x,LINKLIST h)
{
    linklist P,L;
    P=h->next;
    L=h;
    while(L!=null)
    {
        if(L->data==x)
        {
            L=L->next;
            free(p->next);
            p->next=L;
        }
        else
        {
            p=L;
            L=L->next;
        }
    
    }

}

When I had ChatGPT check my code, it insisted that there were errors in my code, especially regarding

if(L->data==x)
{
    L=L->next;
    free(p->next);
    p->next=L;
}

In this part, he believes that free(p->next) is incorrect, and the correct code should be:

if (L->data == x)
{
    temp = L; 
    P->next = L->next; 
    L = L->next;
    free(temp); 
}

I don't think there's anything wrong with my code, and

if(L->data==x)
{
    L=L->next;
    free(p->next);
    p->next=L;
}

This part is logically acceptable.

I don't understand why I need to store a temporary variable temp first and then free that temporary variable. Can't I just use free(p->next) to release the space of the node being deleted directly?

Answer 1

You have 3 options for the delete interface in order to be able to delete the first node:

1. Allocate a dummy root node that doesn't hold data.
2. Return the (potential) new head.
3. Pass in pointer to pointer so you can (potentially) update the new root.

It looks like you are using option 1 but you should then start the search the search at the 2nd node, or ensure the root's node sentinel data can never occur in the list so if(L->data==x) is false by definition.

The snippet you are concerned about is ok but you initialize L and P incorrectly. It still works because you never delete the root node and the else happens to fix it:

void deleteX(int x, linklist *h) {
    if(!h) return;
    linklist *P = h;
    linklist *L = h->next;
    while(L) {
        if(L->data==x) {
            L=L->next;
            free(P->next);
            P->next=L;
        } else {
            P=L;
            L=L->next;
        }
    }
}

I used an alternate version below as I find that easier to read:

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

typedef struct node {
    int data;
    struct node *next;
} linklist;

void deleteX(int x, linklist *h) {
    if(!h) return;
    linklist *P = h;
    linklist *L = h->next; // skip root
    while(L) {
        if(L->data==x) {
            P->next = L->next;
            free(L);
            L=P->next;
        } else {
            P=L;
            L=L->next;
        }
    }
}

linklist *createNode(int data) {
    linklist *node = malloc(sizeof *node);
    if(!node) {
        perror("malloc");
        exit(1);
    }
    node->data = data;
    return node;
}

linklist *createList(size_t n, const int *data) {
    linklist *head = createNode(-1);
    linklist *tail = head;
    for(size_t i = 0; i < n; i++) {
        tail->next = createNode(data[i]);
        tail = tail->next;
    }
    if(tail)
        tail->next = NULL;
    return head;
}

void print(linklist *h) {
    if(!h) return;
    for(h=h->next; h; h=h->next)
        printf("%d%s", h->data, h->next ? "->" : "\n");
}

int main() {
    linklist *root = createList(3, (int []) {1,0,1});
    print(root);
    deleteX(1, root);
    print(root);
}

and example run:

1->0->1
0

Answer 2

There isn't much wrong with it. You need a temp variable to hold the node that is to be deleted. But here, L is a "temporary" variable.

If we consider the process that's occurring. You have 3 nodes, you want to redirect the first's link to reference the last node and then delete the middle one.

So you have to track the middle one to delete it, or you can track the last node and then reassign the first node to reference it.

Usually we do the former process as its more obvious. Reassign, then delete. This helps ensure there's no issue with accidentally accessing other data that has now been deleted. It also ensures the chain of references is always correct.

However, your approach of tracking the next node, breaking the chain, and then reassigning the reference means there is a short time when your linked list is invalid. Your list now doesn't end correctly - for a short time P has a reference to a dangling pointer. Imagine if (ha! when) another thread decides to loop through your list, and tries to access that node. Its still pointed to but is now deleted and that is bad.

This is why we use the temp. It keeps the list intact and valid at all times. The bug you introduced here trying to write shorter code will hit someone sometime and it'll be a bastard pain in the butt bug to find.