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

• forsvarir: Your first malloc calls look a little odd to me... You aren't using the memory anywhere.
• 1201ProgramAlarm: Your question would be more complete if you showed the definition for node_t.
• forsvarir: 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.

Answer 1

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

• awwwww: 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?
• Joop Eggen: Yes, curr points to head, then nodes' next field, being able to change those variable/fields.
• awwwww: 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 :)
• Joop Eggen: 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).
• awwwww: 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

Answer 2

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.

Answer 3

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.

• awwwww: 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 :)

Answer 4

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)).