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