How can I delete an node from a linked list with a single pointer?

Question

The book I study #include an exercise that asks us for modifying the following code which deletes a node from a linked list and building another function that does the exact thing with only one pointer:

struct node {
    int value;
    struct node * next;
};

struct node delete_from_list( struct node * list , int n){
struct node *cur, *prev;

for (cur = list, prev = NULL;
    cur != NULL && cur -> value != n;
    prev = cur, cur -> next)
;

if(cur == NULL)
    return list;
else if(prev == NULL)
    list = list -> next;
else
prev -> next = cur -> next;

free(cur);
return list;
}

Some code I've seen online is:

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

But i have two objections for this:

This code contains two pointers actually entry and list.
We are free()ing the entry yet proceed to use it which "feels" like an error.

Please, if you are willing to help, either explain my objections or write a new code. Thanks.

I'd start with a piece of paper and a pencil and draw the situation. — Jabberwocky
– Jabberwocky, Commented Mar 24, 2020 at 13:44
ad.2: you are not using the entry once freed. There is a break; — Paul Ogilvie
– Paul Ogilvie, Commented Mar 24, 2020 at 13:49
Yes, i drew it but it is actually what made me question it. I drew entry pointing to a block of two boxes which means a struct node structure. And using free(entry) was just replacing the block of two boxes with a huge cross. It is right, isn't it? — Ali A
– Ali A, Commented Mar 24, 2020 at 13:51
@PaulOgilvie Oh OK. That makes more sense right now. Thanks but isn't the code still has 2 pointers? — Ali A
– Ali A, Commented Mar 24, 2020 at 13:53
Welcome to stackoverflow! Its a nice little exercise. I know what you mean about the two pointers, but I think that the question setter is excluding the parameter. If the parameter is included then the original code has three: list, cur, prev. — Tim
– Tim, Commented Mar 24, 2020 at 14:56

Ardent Coder · Accepted Answer · 2020-03-24 13:59:37Z

1

This code contains two pointers actually entry and list.

You are required to build an algorithm that uses a single pointer. In your case, though it seems like two, entry is that one pointer which the algorithm uses apart from list which is actually an input to the function containing the algorithm.

We are free()ing the entry yet proceed to use it which "feels" like an error.

The code doesn't use entry after freeing it. Once freed, the loop breaks immediately due to the break statement succeeding the call to free.

edited Mar 24, 2020 at 13:59

answered Mar 24, 2020 at 13:54

Ardent Coder

4,1159 gold badges35 silver badges62 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How can I delete an node from a linked list with a single pointer?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related