Removing nodes with a given value from a linked list

Question

Is this a good way of removing all the nodes that contains a value x? This function takes as input the head of a list and has to delete all the nodes that contain a given value taken. If there is any better way of doing this can you please show them to me?

node_t *funzione(node_t *head){

    int x;
    node_t *temp = head;
    node_t *curr = head;

    temp = (node_t *)malloc(sizeof(node_t));
    curr = (node_t *)malloc(sizeof(node_t));

    printf("Inserisci il valore che vuoi eliminare: \n");
    scanf("%d", &x);

    if (head == NULL)
        exit(0);

    while(head->val == x){
        head = head->next;
        free(temp);
        temp = head;
    }

    curr = head;
    temp = curr->next;

    while (temp != NULL){
        if (temp->val == x){
            if(temp->next != NULL){
                curr->next = temp->next;
                free (temp);
                temp = curr->next; 
            }
            else {
                curr->next = NULL;
            }
        }
        else {
            curr = temp;
            temp = temp->next;
        }
    }

    return head;
}

Your first malloc calls look a little odd to me... You aren't using the memory anywhere. — forsvarir
– forsvarir, Commented Feb 10, 2020 at 23:20
Your question would be more complete if you showed the definition for node_t. — 1201ProgramAlarm
– 1201ProgramAlarm, Commented Feb 11, 2020 at 1:04
Please don't modify your question to reflect changes based on answers, it creates confusion and mismatched Q & A. If you want changes reviewed, please ask another question. — forsvarir
– forsvarir, Commented Feb 11, 2020 at 13:58

Joop Eggen · Accepted Answer · 2020-02-14 14:31:39Z

3

A function that asks its parameter is not really usable, but let's assume it is for the code review question.

The main error is starting right away to declare and create variables. Allocation certainly is not needed when deleting nodes.

Try postpone creating variables until one needs them. Thus reducing the effort to read the code, and being sure one needs them in that way.

C/C++ can use aliasing: keeping a variable pointing to either head or some node_t->next field. This really is a special feature of these languages. The usage here would be:

node_t *funzione(node_t *head) {

    printf("Inserisci il valore che vuoi eliminare: \n");

    int x;
    scanf("%d", &x);

    node_t **curr = &head;
    while (*curr != NULL) {
        if ((*curr)->val == x) {
            node_t *removed = *curr;
            *curr = (*curr)-> next;
            free(removed);
        } else {
            curr = &(*curr)->next;
        }
    }
    return head;
}

As you see: the code is more straight forward. The alternative you applied: first handle head, and then in the loop remember the previous node, so its next field may be corrected.

Declaring the removed inside the loop is not more inefficient, neither costs more time or space.

Sketchy

curr ---> head or next field ---> node with data sought
                  insidde the preceding node

*curr = xxx; will change head or next fields value
curr = &(*curr)->next; will remove the node

Example:

  head         node1          node2        node3
+-------+    +---------+    +-------+    +-------+
| node1 |--->| +-----+ |    | node3 |--->| null  |---|
+-------+    | |node2| |--->| val2  |    | val3  |
             | + -^--+ |    +-------+    +-------+
             +----|----+
                  |
                 curr
      has the address of the next field containing node2

*curr == node2
(*curr).val == val2

edited Feb 14, 2020 at 14:31

answered Feb 11, 2020 at 16:57

Joop Eggen

4,71615 silver badges19 bronze badges

\$\begingroup\$ so you are creating a **curr variable instead of creating a new variable and you use it to go through the list. So this short function has the same result of the one I should have had? \$\endgroup\$

awwwww
– awwwww

2020-02-11 17:16:58 +00:00
Commented Feb 11, 2020 at 17:16
\$\begingroup\$ Yes, curr points to head, then nodes' next field, being able to change those variable/fields. \$\endgroup\$

Joop Eggen
– Joop Eggen

2020-02-11 17:18:48 +00:00
Commented Feb 11, 2020 at 17:18
\$\begingroup\$ Thanks very much for your help man it really means a lot for me, could you just explain the last thing? What is the meaning of &head, I mean when you are assigning to **curr = &head what's really happening, what's &head, I know & is used to dereference but you are dereferencing a pointer am I wrong? And last but not least, could you explain why there is the need to do this: "curr = &(*curr)->next;" Thanks a lot in advance :) \$\endgroup\$

awwwww
– awwwww

2020-02-11 20:45:05 +00:00
Commented Feb 11, 2020 at 20:45
\$\begingroup\$ Inverse, & takes the address/reference of the variable. So *curr = xxx; is the same as head = xxx;. Then curr = &(*curr)->next takes the address of the node_t*next field. So then *curr = xxx; is the same as (*curr)->next == xxx;. A pointer to pointer. The effect is addressing the next node from the current (head or next field). \$\endgroup\$

Joop Eggen
– Joop Eggen

2020-02-12 09:27:21 +00:00
Commented Feb 12, 2020 at 9:27
\$\begingroup\$ Hi Joop, sorry if I bother you too much but there is still something that I cannot get about the code you wrote. I know it works perfectly cause I have tested it, but you don't have a reference to the precedente element, so you can not delete current element. Am I wrong? If there is the reference could you please show it to me? Many thanks and sorry again if bothered you \$\endgroup\$

awwwww
– awwwww

2020-02-14 13:15:51 +00:00
Commented Feb 14, 2020 at 13:15

| Show 3 more comments

1201ProgramAlarm · Accepted Answer · 2020-02-11 01:03:40Z

The input asking for which value to delete can/should be placed in a separate function. Then the function to remove the nodes can take that value as a parameter.

The two malloc calls for temp and curr near the top are completely unnecessary and just leak memory. You want to remove nodes, so you shouldn't have to allocate any memory.

If your list consists of a single node where val == x (or, more generally, all nodes in the list have that value), your program will crash.

If the last node in the list matches the value (and there are other nodes that don't), you'd be leaking that node except that you will be stuck in an infinite loop. You shouldn't need to handle the last node any differently than removing any other node.

forsvarir · Accepted Answer · 2020-02-11 09:57:24Z

node_t *funzione(node_t *head){

This is a weird name for a function to remove a node. The naming should reflect what the operation does, not what it is.

    int x;
    node_t *temp = head;
    node_t *curr = head;

The way the rest of your function works, it assumes that temp points to the node after curr in the list, assigning them to the same node is asking for trouble.

    temp = (node_t *)malloc(sizeof(node_t));
    curr = (node_t *)malloc(sizeof(node_t));

You don't need to malloc anything here, you're not doing anything with the memory. Since malloc returns void *, casting it to node_t* would be unnecessary.

    printf("Inserisci il valore che vuoi eliminare: \n");
    scanf("%d", &x);

This would be better done in another method, with the value being passed in as a parameter to this method, to indicate what to remove.

    if (head == NULL)
        exit(0);

This is pretty drastic. If you're going to just abort the app like this, then it would be a good idea to print something to stderr to give an indication what happened. Generally, consider wrapping if clauses in {}, even when they're single line. I think it would be ok in this situation to return head, i.e. NULL in this situation, rather than exiting the program. If the caller passed in a head of NULL, they're probably ok handling it coming back from the method.

    while(head->val == x){
        head = head->next;
        free(temp);
        temp = head;
    }

This frees the memory allocated for temp above, however it doesn't free the actual node pointed to by head on the first pass.

    curr = head;
    temp = curr->next;

    while (temp != NULL){
        if (temp->val == x){
            if(temp->next != NULL){
                curr->next = temp->next;
                free (temp);
                temp = curr->next; 
            }
            else {
                curr->next = NULL;

You stop pointing at temp, but never free it, or break out of the loop, so you'll just keep revisiting this assignment over and over again.

Hi thanks a lot for your reply I have modified the code applying some of the things you have said. I haven't understood your last commend about stop pointing at temp but never free it, how should I modify it to make it work? cause when i exe it it works. About your second to last comment, do I have modified it correctly? Thanks in advance man, really apprecciate your help :) — awwwww
– awwwww, Commented Feb 11, 2020 at 13:35

Toby Speight · Accepted Answer · 2020-02-11 17:31:21Z

3

Whenever you perform input like this, don't discard the result of scanf():

int x;
scanf("%d", &x);

At the very least, bail out if invalid input is provided:

int x;
if (scanf("%d", &x) != 1) {
    fputs("Input failed!\n", stderr);
    return NULL;
}

A more sophisticated approach would consume the rest of the line (scanf("%*[^\n]")) and re-try the input, until either it succeeds or the stream reaches an irrecoverable state (feof(stdin)).

answered Feb 11, 2020 at 17:31

Toby Speight

88.7k14 gold badges104 silver badges327 bronze badges

Add a comment |

Stack Exchange Network

Removing nodes with a given value from a linked list

4 Answers 4

You must log in to answer this question.

Linked

Hot Network Questions

Removing nodes with a given value from a linked list

4 Answers 4

You must log in to answer this question.

Linked

Related

Hot Network Questions