# Remove nodes of a linked list on condition (C)

I am doing an exercise with a linked list, in which I need to remove some nodes according to a condition. The condition is ''remove the nodes that have a data stored that is less or equal to 'avg''.

I should consider three cases:

- removing a node in the middle

- removing last node

I used three pointers, but this doesn't seem to work. What am I doing wrong? Am I accidentally missing some pointers? Thank you in advance!

``void checkAvg(int avg, struct list* head_node){struct list* prev;struct list* curr;struct list* next;prev = head;curr = prev->link;next = curr->link;while (curr!=NULL) {if (prev->data <= avg) {head = curr;}if (curr->data <= avg) {prev->link = curr->link;}if (next->data <= avg) {curr->link = next->link;}prev = prev->link;curr = curr->link;next = next->link;}}``

EDIT:

I am sorry, as you told me, I wasn't specific. The program has to do this:

2) Generate an output average of the values I read (sum of values / # of values)

3) remove from the list the nodes that have a data that is <= to the average

Free the memory of those nodes.

About the free() part, I have some difficulties with that, so I thought I first had to learn how to properly use pointers. As you may have noticed, I am not really good at that, I am starter.

Thank you for everyone who has replied, I am checking the replies right now

If your linked list does not have some sentinel head-node (and I strongly advise that it does not, as `NULL` is a damn fine value to indicate "I'm empty"), removal traversal is not overtly complicated. The places in your code where you seem to go astray are:

• Passing the head pointer by-address and declaring the parameter as a pointer-to-pointer OR returning the new head pointer if the old one was disposed.
• Maintaining consistency in your local pointer variables. You have to know for sure what everything points to at all times.

You can use pointer values, or you can use the actual pointers themselves (by address). I prefer the latter. In either case, the head node pointer must be passed by-address to allow potential modification of the caller's variable (like everything else in C) or the function can return the potentially new head node address. I prefer the former of those methods, as it leaves you the option of using the function return value for communicating error states to your caller. You're not doing that right now, but you should (hint).

``````void checkAvg(int avg, struct list** pp)
{
while (*pp)
{
if ((*pp)->data <= avg)
{
struct list *victim = *pp;
free(victim);
}
else
}
}
}
``````

It is worth noting this can be significantly simpler if the list is maintained as sorted in ascending order. If that is the case, the entire `checkAvg` function becomes substantially simpler. You can exit the loop as soon as you detect a value that no longer fits your condition:

``````void checkAvg(int avg, struct list** pp)
{
while (*pp && (*pp)->data <= avg)
{
struct list *victim = *pp;
free(victim)
}
}
``````

In either case, the function is invoked by passing the head pointer on the caller-side by-address:

``````struct list *head = NULL;

//... populate list....

``````

How it Works

A linked list is just something that looks like this:

``````          --------      --------      --------
| val1 |      | val2 |      | val3 |
--------      --------      --------
``````

Using the methods posted, traversing the list uses a pointer-to-pointer, which does something like this:

``````pp --:
:        --------      --------      --------
| val1 |      | val2 |      | val3 |
--------      --------      --------
``````

`pp` points to a pointer; not a node. Initially `pp` holds the address of the `head` pointer (was passed in by-address as a parameter).

So what happens if the first node matches your criteria? Ultimately, this is the result

``````pp --:
:        --------      --------
| val2 |      | val3 |
--------      --------

--------
| val1 |
--------
``````

and the victim node is summarily discarded (the link of victim actually still references the second node, but is meaningless in this context after the detachment happens.

So, what about if the second node was the one that needed removal (i.e. we skipped the first node). That gets a little more complicated:

``````         pp -----:
:
---:----      --------
| val1 |      | val3 |
--------      --------
--------
| val2 |
--------
``````

What this is trying to show (admittedly poorly) is that the `pp` pointer-to-pointer always holds the address of the pointer that we may be modifying. If we don't need to modify that pointer, we change the address held in `pp` to point to the next `link` pointer in the list (obtained through `pp = &(*pp)->link`

The latter case doesn't happen when the list is already sorted , thus the reason its iterative loop is simpler. We just enumerate the list, throwing out nodes until we find one that no longer meets our condition.

But no matter what, `pp` always holds the address of the pointer that points to the node we're working with.. Initially, that address is the address of the caller's `head` pointer.

Ok. I can only hope that makes it clearer. Some debugging with `printf("pp=%p, *pp=%p\n", pp, *pp)` in the loop makes what is actually happening most-educational. Walking through the algorithms by-hand in a debugger would be highly informative.

It's a lot easier than you think.

You're walking and modifying a linked list, so set up a current and previous.

``````void checkAvg(int avg, struct list** head_node){ //when calling, use checkAvg(avg, &head_node);
struct list* prev = NULL;
``````

``````while(curr != NULL){
if(curr->data <= avg){
if(prev == NULL){
} else {
prev->next = curr->next; //removes the unwanted node
}
}
curr = curr->next;
}
``````

You really don't need a special end case because the while loop terminates when curr is NULL; for the last item in the list, curr->next is NULL so when it get set it will end the loop. You also don't need to check if the list is empty, because the loop will end if it `curr == NULL` and you assign the head to `curr` at first.

You're checking each node three times in each iteration, which leads to some weird behavior. Check the head before entering the loop, and only compare the current node each time:

``````void checkAvg(int avg, struct list* head_node){

struct list* prev;
struct list* curr;

} else {
break;
}
}

while (curr!=NULL) {

if (curr->data <= avg) {

}
}
}
``````

Rather than checking the data of prev, curr and next, just check for one single data in the loop.
You also need to return the new head in case it changes.
I'd suggest something like that (tested):

``````#include <stdio.h>
#include <malloc.h>

typedef struct list_ {
int data;
} list;

list* RemoveElementsBelow(int avg, list* head_node) {
// Remove the first.
}
return NULL;
}

list* prev;
list* curr;

while (curr != NULL) {
if (curr->data <= avg) {
prev->link = curr->link;  // Will be NULL at the end of the list.
free(curr);
} else {
prev = curr;
}
}
}

list* new_node = malloc(sizeof(list));
new_node->data = value;
return new_node;
}

}
printf("\n");
}
int main(int argc, char **argv) {
list* my_list = NULL;
int i;
int sum = 0;
for (i = 1; i < argc; ++i) {
int value = atoi(argv[i]);
sum += value;
}
if (argc == 1) {
return 1;
}
int avg = sum / (argc - 1);
printf("Average value: %d\n", avg);

my_list = RemoveElementsBelow(avg, my_list);

PrintAndDeleteList(my_list);
return 0;
}
``````

Compiled:

``````gcc -o test test.c
``````

Tested: ./test 10 20 30 40 50 Average value: 30 50 40 ./test 50 40 30 20 10 Average value: 30 40 50

I want some recursive magic tonight

``````Node* deleteBad(Node *head, int(*pred)(int)) {
return NULL;
}
}
else {
}
}
``````

And accumulators

``````void deleteBad2(Node *head, int(*pred)(int), Node *out) {
} else {
}
}
}
``````

And for those coxcombs who dislike recursion optimized version

``````void deleteBad3(Node *head, int(*pred)(int), Node *out) {
begin:
out = out->next;
goto begin;
}
else {
goto begin;
}
}
}
``````

and if someone dislike gotos

``````void deleteBad3nogoto(Node *head, int(*pred)(int), Node *out) {
while (1) {
out = out->next;

}
else {

}
}
else {
break;
}
}
}
``````