How to remove a specific element from a linked list

In some data structure like the stack, we may want to pop elements content always from the head of the linked list, or, as in the queue case, always from the tail. We may also face very easily a case where the list must be scanned, indexed or sorted in some way, to get to the element we wish to extract the data from. In a case like this, we must be able to search the data, by comparing each piece of it with some kind of query, like an index, a string, or whatever we can use as reference to what it's stored inside the structure. To stick to the style of this tutorial, we will take in to consideration the simplest case scenario, by writing a function that will allow us to check a linked list and determine if it contains a specific integer value. The following function expands on the code given in the previous post

int pop_val( list ** llist, int val )
{
  list * curr = *llist;
  list * prev = NULL;
 
  while( curr != NULL )
    {
      if( curr->data == val )
        {
          if( prev == NULL )
            {
              *llist = curr->next;
            }
          else
            {
              prev->next = curr->next;
            }

          free( curr );
          printf( "pop_val: %d\n", val );
          return 0;
        }

      prev = curr;
      curr = curr->next;
    }

  printf( "pop_val:value %d not found!\n", val );
  return 1;
}  

the function will return 0, if the value passed is found, 1 otherwise.
The most important thing to note is the introduction of the variable prev, which is needed to keep track of the previous element. We need to store an element in case we scan it without finding the value we are looking for. Once we encounter the element containing the right value

      if( curr->data == val ) 

if pre is null, which means that we have found the value in the first element of the list, we simply fix the first element, by copying inside it the second one

      *llist = curr->next;

and deleting the first through curr

      free(curr);

else we copy the next list's element inside prev own next pointer

      prev->next = curr->next;

reconnecting the list before the current element is deleted.
In each iteration we copy curr in prev, if we didn't find in it the value searched. This is done just before the pointer is advanced to the next element

      prev = curr;
      curr = curr->next;

to test the function pop_val(), we will use the code given in the previous post .
The following is the new main function of the test code

int main()
{
  /* Initializes the linked list with 10. mylist = { 10 }     */
  list * mylist = create(10);
  puts("created list with 10 at first node");

  /* Appends 4 elements. mylist = { 10, 20, 30, 40, 50 }      */
  append(mylist, 20);
  append(mylist, 30);
  append(mylist, 40);
  append(mylist, 50);
  /* Pushes 2 elements. mylist = { 4, 2, 10, 20, 30, 40, 50 } */
  push(&mylist, 2);
  push(&mylist, 4);
 
  print(mylist);

  /* Pops 2 elements from tail. mylist = { 4, 2, 10, 20, 30 } */
  int data = pop_tail(&mylist);
  printf("pop_tail returned:%d\n", data);
  data = pop_tail(&mylist);
  printf("pop_tail returned:%d\n", data); 
  /* Pops 1 element from head. mylist = { 2, 10, 20, 30 }     */
  data = pop(&mylist);
  printf("pop returned:%d\n", data); 
 
  /* Pops the element storing 10. mylist = { 2, 20, 30 }      */
  pop_val(&mylist, 20);

  /* Pops the element storing 2. mylist = { 20, 30 }          */
  pop_val(&mylist, 2);  
  print(mylist);
 
  return 0;
}

How to add or remove an element at the beginning of a linked list in C

In this post we expand the code given in the last post about linked lists (I'm in a hurry, bring me to the code ). We have seen how appending and removing an element on the tail of the list is done. To insert one on the opposite side ( head ), we don't need to traverse the list, as we can use the address of the first element in it

void push( list ** llist, int data )
{
  list * curr = malloc( sizeof( list ));
  curr->data = data;
  curr->next = *llist;
  *llist = curr;
  printf("push: %d\n", data);
}

pushing an element on the linked list requires a change in the caller's memory. So, as with the function pop_tail(), with the function push() we need a direct reference to it and not just a copy. That's why we have a pointer to a pointer to a struct list as first parameter of the function ( see the previous post for a more detailed explanation ). The second parameter is, of course, the data stored in the new element. In this particular case, the new element, becomes also the new first element of our list, and, also, the new starting address. In the first two lines of code inside push(), we create a new element with its data load, element which still isn't linked to the list. In the third line of code, curr->next = *llist, we copy the actual first element of the list inside the next pointer of the newly created element ( curr->next -- the linking pointer ). Then we set the new first element of the linked list by copying the new one ( curr ) inside llist. Note how we dereference llist with the indirection operator ( * ), operation which allows us to access and modify the memory at the address stored inside llist.

To finish this part of the tutorial, we write a function which removes an element from the head's side of the linked list

int pop( list ** llist )
{
  int r = (*llist)->data;
  free( *llist );
  *llist = (*llist)->next;
  printf( "pop: %d\n", r );
  return r;
}

again, the code above, is minimalistic and unsafe, as we only want it to show the basic of what it needs to be done for performing the actions on the data. As in the function push(), here we need to access the caller's memory. Thus we have a double pointer parameter. The parenthesis are necessary because the structure member access  via pointer operator ( -> ) has a higher precedence on the indirection operator ( * ). Thus we use parenthesis to prioritize the dereferencing operation and access the data correctly.

The following is the complete code with some minors improvement 

#include <stdio.h>
#include <stdlib.h>

typedef struct list
{
    int data;
    struct list * next;
}list;

list * create(int data)
{
  list * first = malloc(sizeof(list));
  first->data = data;
  first->next = NULL;

  return first;
}

void append( list * llist, int data )
{
  list * curr = llist;
  while( curr->next != NULL )
    {
      curr = curr->next;
    }

  curr->next = create( data );
  printf("append:%d\n", data);
}

int pop_tail( list ** llist )
{
  list * curr = *llist;
  if( curr == NULL )
    {
      printf("pop_tail:list is empty! nothing to pop\n");
      return;
    }

  while( curr->next->next != NULL )
    {
      curr = curr->next;
    }

  int retval = curr->next->data;
  free( curr->next );
  curr->next = NULL;
  printf("pop_tail:%d\n",retval);

  return retval;
}

void push( list ** l, int data )
{
  list * c = malloc(sizeof(list));
  c->data = data;
  c->next = *l;
  *l = c;
  printf("push: %d\n", data);
}

int pop( list ** l )
{
  list * c = *l;

  if(c)
    {
      int r = (*l)->data;
      free(*l);
      *l = (*l)->next;
      printf("pop: %d\n", r);
      return r;
    }
  else
    {
      printf("pop:list is empty! nothing to pop\n");
      return ;
    }
}

void print( list * llist )
{
   list * curr = llist;

  if( curr == NULL ){
      puts("print:List empty!");
      return;
  }

  printf("print:");
  while( curr != NULL )
    {
      printf("%d ", curr->data);
      curr = curr->next;
    }
  puts(" ");
}

int main()
{
  /* Initializes the linked list with 10. mylist = { 10 }     */
  list * mylist = create(10);
  puts("created list with 10 at first node");

  /* Appends 4 elements. mylist = { 10, 20, 30, 40, 50 }      */
  append(mylist, 20);
  append(mylist, 30);
  append(mylist, 40);
  append(mylist, 50);
  /* Pushes 2 elements. mylist = { 4, 2, 10, 20, 30, 40, 50 } */
  push(&mylist, 2);
  push(&mylist, 4);
 
  print(mylist);

  /* Pops 2 elements from tail. mylist = { 4, 2, 10, 20, 30 } */
  int data = pop_tail(&mylist);
  printf("pop_tail returned:%d\n", data);
  data = pop_tail(&mylist);
  printf("pop_tail returned:%d\n", data); 
  /* Pops 1 element from head. mylist = { 2, 10, 20, 30 }     */
  data = pop(&mylist);
  printf("pop returned:%d\n", data); 

  print(mylist);
 
  return 0;
}