// This program creates a simple link list of integers based on the user's
// input of a sequence of numbers.  The program then prints out the list.

// This program builds a linked list.  The user enters a list of numbers.
// Each number is stored in one link of the linked list.  The advantage
// of a linked list over an array is that the maximum size does not have
// to be declared in advance.  Also, links can easily be inserted in the list.

#include <stdlib.h>
#include <iomanip.h>

// define one link in the linked list

struct link
{
    int data;
    struct link *next;
};

// function prototypes

void chase(link *l);
link * prepend_link(link *newlink, link *head);
link * append_link(link *newlink, link *head);
link * insert_link(link *newlink, link *head);

///////////////////////////////////// main /////////////////////////////////////

int main(void)
{
    int current;
    link *head = NULL;  // pointer to first link
    link *newlink;        // pointer to newly created link

    cout << "Enter a list of numbers: ";
    // read the first value
    cin >> current;

    while(!cin.fail()) // loop while a valid number was read from the input 
		               // stream (any nonnumeric value will terminate)
    {
        // create a new link

        newlink = new link;
        newlink->data = current;

        head = insert_link(newlink, head);
        
        // read the next value
        cin >> current;
    }

    // print out the link list of integers

    chase(head);
}

///////////////////////////////////// prepend_link /////////////////////////////
// this function puts the new item at the beginning of the list. 
// the function returns a pointer to the link list.

link * prepend_link(link *newlink, link *head)
{
    newlink->next = head;
    return newlink;
}

///////////////////////////////////// chase ////////////////////////////////////
// This function chases down a link list and prints each data item
// in the list.  This function was written recursively but could also
// have been written using a loop.  You should figure out how to do this.

void chase(link *l)
{
    if (l != NULL) 
    {
        cout << "data value " << l->data << endl;
        chase(l->next);
    }
}

///////////////////////////////////// append_link //////////////////////////////
// this function puts the new item at the end of the list.
// the function returns a pointer to the link list.

link * append_link(link *newlink, link *head)
{
    link *cur;

    newlink->next = NULL;

    if (head == NULL)
        return newlink;

    // chase down the list until we come to the end (i.e., the link whose
    // next pointer is NULL
    
    for (cur = head; cur->next != NULL; cur = cur->next);

    // redirect the former end of the list to the new link
    cur->next = newlink;

    return head;
}

///////////////////////////////////// insert_link //////////////////////////////
// This function puts the new item into the list in numerical order.
// The function returns a pointer to the link list.

link * insert_link(link *newlink, link *head)
{
    link *cur, *prev;

    newlink->next = NULL;

    // special case for the empty list
    
    if (head == NULL)
    {
        newlink->next = NULL;
        return newlink;
    }

    // special case if the new data item belongs before the first item on
    // the list.
    

    else if (newlink->data < head->data)
    {
	newlink->next = head;
	return newlink;
    }

    // otherwise, chase down the list until the next data item in the list
    // is numerically larger than the new data item.
    
    else 
    {
	head->next = insert_link(newlink, head->next);
	return head;
    }
}