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

#define SIZE 10

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

void insertAtFront (linkedPtr* hd, int val)
{
 /* create the new node */
 linkedPtr ptr = (linkedPtr) malloc (sizeof(linked));

 /* store information into the new node  */
 ptr->elem = val;
 ptr->next = *hd;

 /* update the head of the list to refer to the new node */
 *hd = ptr;
}

void insertAtEnd (linkedPtr* hd, int val)
{
 linkedPtr curr = *hd;
 linkedPtr prev = NULL;

 /* find the end of the list */
 while (curr != NULL)
   {
    prev = curr;
    curr = curr->next;
   }

 /* create the new node to be inserted into the list */
 linkedPtr ptr = (linkedPtr) malloc (sizeof(linked));
 ptr->elem = val;
 ptr->next = curr;   /* curr is always NULL at this line of code */

 /* if the list is empty the new node goes at the front (update head) */
 if (prev == NULL)
   {
    *hd = ptr;
   }
 else
   {
    prev->next = ptr;
   }
}

void insertInOrder (linkedPtr* hd, int val)
{
 linkedPtr curr = *hd;
 linkedPtr prev = NULL;

 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)
   {
    *hd = ptr;
   }
 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 head = 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 (&head, temp);
     insertAtEnd (&head, temp);
     // insertInOrder (&head, temp);

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

  printf ("\n");


}