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

#define SIZE 10

struct linkedStruct
{
 int elem;
 struct linkedStruct*  next;
};
 
typedef struct linkedStruct linked;
typedef linked* linkedPtr; 

/* Insert the value at the beginning of the linked list */
void insertAtFront (linkedPtr* hd, int val)
{
 linkedPtr ptr = (linkedPtr) malloc (sizeof(linked));
 ptr->elem = val;
 ptr->next = *hd;
 *hd = ptr;
}

/* Insert the value at the end of the linked list */
void insertAtEnd (linkedPtr* hd, int val)
{
 linkedPtr curr = *hd;
 linkedPtr prev = NULL;

 /* traverse to the end of the list */
 /*    prev is always one node "behind" curr */
 while (curr != NULL)
   {
    prev = curr;
    curr = curr->next;
   }

 linkedPtr ptr = (linkedPtr) malloc (sizeof(linked));
 ptr->elem = val;
 ptr->next = curr;

 /* when prev == NULL - the list was originally empty */
 if (prev == NULL)
   {
    *hd = ptr;
   }
 /* else prev refers to the last node in the list */
 else
   {
    prev->next = ptr;
   }
}

/* insert the values so that the smallest value is at the front of the list, */
/*   the largest value is at the end of the list, and the values are in      */
/*   increasing order from the front to the end of the list                  */
void insertInOrder (linkedPtr* hd, int val)
{
 linkedPtr curr = *hd;
 linkedPtr prev = NULL;

 /* stop when the end of found or when the current node contains a value   */
 /*   greater than or equal to the value being inserted                    */
 while ((curr != NULL) && (curr->elem < val))
   {
    prev = curr;
    curr = curr->next;
   }

 linkedPtr ptr = (linkedPtr) malloc (sizeof(linked));
 ptr->elem = val;
 ptr->next = curr;

 /* if prev == NULL - then we must insert at the front of the list */
 if (prev == NULL)
   {
    *hd = ptr;
   }
 /* else insert after the node previous is referring to */
 else
   {
    prev->next = ptr;
   }
}

void show (linkedPtr hd)
{
 while (hd != NULL)
   {
    printf ("%d, ", hd->elem);
    hd = hd->next;
   }
 printf ("\n");
}

int listLength (linkedPtr hd)
{
 int length = 0;
 while (hd != NULL)
   {
    length++;
    hd = hd->next;
   }
 return length;
}


int main (int argc, char**argv)
{
  linkedPtr head1 = NULL;
  linkedPtr head2 = NULL;
  linkedPtr head3 = NULL;
  int i;
  int temp;

  for (i = 0 ; i < SIZE; ++i)
    {
     temp = rand() % 100;
     printf ("In main(): temp: %6d\n", temp);

     // select which one you want to use
     insertAtFront (&head1, temp);
     insertAtEnd (&head2, temp);
     insertInOrder (&head3, temp);

     show (head1);
     show (head2);
     show (head3);
     printf ("The list has %d nodes\n", listLength(head1));
    }

  printf ("\n");


}