Remove nodes of a linked list on condition (C)

Question

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 the head node - 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: 1) Read a linked list 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

Answer 1

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;
            *pp = victim->link;
            free(victim);
        }
        else
        {   // advance to address of next "link" pointer
            pp = &(*pp)->link;
        }
    }
}

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;
        *pp = victim->link;
        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....

checkAvg(value, &head);

---

How it Works

A linked list is just something that looks like this:

          --------      --------      --------
head ---> | link | ---> | link | ---> | link | ---> NULL
          | val1 |      | val2 |      | val3 |
          --------      --------      --------

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

pp --:
     :        --------      --------      --------
    head ---> | link | ---> | link | ---> | link | ---> NULL
              | 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 --:
     :        --------      --------
    head ---> | link | ---> | link | ---> NULL
              | val2 |      | val3 |
              --------      --------

             --------
 victim ---> | link |
             | 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 -----:
                 :
              ---:----      --------
    head ---> | link | ---> | link | ---> NULL
              | val1 |      | val3 |
              --------      --------
             --------
 victim ---> | link |
             | 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.