/* This program demonstrates a linked list. 
 * A linked list is a proto array where the elements are not in contiguous locations.
 * We need to have each element point to the next element in the list.
 * This requires a self referential structure, which is a structure that contains a pointer to the structure type.
 */
#include<iostream>

using namespace std;
//Self referential structure.
struct Num
{
	int val;
	struct Num *next; // We need the struct keyword here because Num is not completely defined yet
};
int main()
{
	//We're going to need 3 pointers of Num type to build the list.
	Num *head=NULL, *pre =NULL, *cur=NULL;
	cout<<"Enter the numbers (0 to stop):";
	int x;
	cin>>x;
	while(x!=0)
	{
		cur = new Num; //create a new node
		cur->val = x;	//assign the values
		cur->next = NULL; //as of now, this node is standalone
	
		if(head==NULL)	//This is the first element
			head=cur; //Once head is set, we don't change it unless absolutely necessary
		else
			pre->next = cur; //attach this node to the end of the list
		pre=cur;// we have moved on. For the next iteration, the current number becomes the previous number.
		cin>>x; // get the next number
	}

	//print
	cur=head; //start at the beginning
	while(cur!=NULL) //until we get to the end
	{
		cout<<cur->val<<"\t";
		cur=cur->next; //move to the next element of the list
	}

	//cleanup
	cur=head;
	pre=head;
	head=NULL;
	while(cur!=NULL)
	{
		pre=cur->next; //store the next one. otherwise we lose the list
		delete cur;	//get rid of the current
		cur=pre; 	//move on to the next
	}
	
	return 0;
}