/*
  This program demonstrates how to create a self-referential linked list
  structure.  A linked list is constructed from a sequence of node 
  structures.  Each node contains some data, in this case it is an integer,
  and a pointer to the next node in the sequence.  A linked list is then
  a pointer to the first node in the sequence, called the head, and an 
  integer representing the number of items stored in the list.
*/

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

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

typedef struct {
  node *head;
  int length;
} list;

list *NewList();
void InsertAtHead(int value, list *ls);
void InsertInOrder(int value, list *ls);
void PrintList(list *ls);

main() {
  list *ls;
  
  ls = NewList();
  PrintList(ls);  // should be empty
  InsertAtHead(10, ls);  
  PrintList(ls);  // should contain 10
  InsertAtHead(30, ls);
  PrintList(ls);  // should contain 30, 10
  InsertAtHead(15, ls);
  PrintList(ls);  // should contain 15, 30, 10
  InsertAtHead(5, ls);
  PrintList(ls);  // should contain 5, 15, 30, 10
}

/*
  This function creates and returns a new empty list.
*/
list *NewList() {
  list *result;

  result = (list *)malloc(sizeof(list));
  if (result==NULL) {
    printf("Insufficient memory to create new linked list.");
    exit(1);
  }
  result->head = NULL;
  result->length = 0;
  return(result);
}

/*
  This function takes a new value and a pointer to an existing list and
  adds the new value into a new node at the head of the list.  For
  example, if the list already contained 2->6->10 and we inserted 15,
  it would now contain 15->2->6->10.
*/
void InsertAtHead(int value, list *ls) {
  // declare a node pointer
  // malloc space for the new node 
  // check that the malloc was successful
  // initialize the data portion of the new node
  // initialize the next pointer portion of the new node
  // update the the head pointer of the list
  // update the length of the list
}

/*
  This function prints information about the size and contents of an 
  existing list.
*/
void PrintList(list *ls) {
  // declare a node pointer
  // initialize the node pointer to the head of the list
  // print a message about the number of items in the list
  // while this pointer is not NULL
    // print the data at this pointer
    // move the pointer forward to the next node
}

/*
  Only try this function after you have the other two working.
  This function assumes that the list is in sorted order and 
  inserts a new value into its proper order.  For example, if
  the list already contained 10->20->30 and we inserted 25,
  then the list would now contain 10->20->25->30.  You will need
  to use two pointers into the list to accomplish this, called
  previous and current.  Try to break down the problem into a 
  series of steps as we did before.  
*/
void InsertInOrder(int value, list *ls) {

}