// Lab Problem 4.1 (repeat of Problem 3.3)

// CS211 ADS2

// T Naughton, CS NUIM

#include<iostream>



/* This program reads positive integers, one per line, from the

** keyboard into a list. The user indicates that they are finished

** by entering any negative integer (the negative integer itself is

** not stored). The computer program then prints out the list of

** numbers, on a single line, separated with blank spaces. This

** program uses a linked list.

*/



struct ListElement {

  int element;

  ListElement * next;

};



ListElement * AddtoFront(ListElement * head, int newdata);

ListElement * PrintList(ListElement * list);



ListElement * AddtoFront(ListElement * head, int newdata){

  /*

  ** This function takes a linked list and a piece of data and creates

  ** a new node with that data, adding it to the front of the list.

  */

  ListElement * temp;      // Create a pointer to a new node

  temp = new ListElement;  // Allocate memory for the node

  temp->element = newdata; // Put the data in the node



  /* Put this node at the top of the list by (a) pointing it at the

  ** head of the list and (b) repointing the head of the list at this

  ** node.

  ** Can you see that the first time we add a node to the list

  ** (i.e. when head==NULL) that we end up marking the end of the

  ** list with a NULL?

  */

  temp->next = head;

  head = temp;

  return head;

}



ListElement * PrintList(ListElement * list){

  /*

  ** This function prints out the list. It does so by printing out the

  ** contents of the head of the list and then repointing the head to

  ** the next element in the list. It repeats this until the end of the

  ** list (a NULL) is found. The function returns a pointer to the

  ** head of the list. Note: this function will work if an empty

  ** list is passed to it.

  */

  ListElement * temp;

  temp = list;        /* store a pointer to the head of the list

                      ** to keep a record of it while we are

                      ** traversing the list.

                      */

  cout << endl << endl << "Here's the list:" << endl;

  while (list != NULL) {

    cout << list->element << ' ';

    list = list->next;

  }

  return temp; /* Return the head of the list again (remember 'list'

               ** will be pointing to the end of the list).

               */

}



void main(void){

  ListElement * list; // a pointer to the head of the list

  int tempint;        // temporary storage for ints from user



  list = NULL;    /* Initialise the list (mark the end of the list

                  ** with NULL).

                  */



  cout << endl << endl << "Please enter positive integers (one ";

  cout << "per line). Terminate with any negative integer:" << endl;

  cin >> tempint;



  while (tempint >= 0) {

    list = AddtoFront(list, tempint);

    cin >> tempint;

  }



  list = PrintList(list);

}