/* This program demonstrates a Linked List.
 * A linked list is a linear collection of data elements, in which linear order
 * is not given by their physical placement in memory, like an array. Instead,
 * each element points to the next. It is a data structure consisting of a 
 * group of nodes which together represent a sequence. Under the simplest form,
 * each node is composed of data and a reference.
 * 
 * Here, we will create a self referential structure, where each structure variable
 * contains a pointer to another structure variable of the same type.
 */

#include<iostream>
using namespace std;

//Declaraing the Node structure.
struct Node
{
	int val;
	struct Node * next; 
	/* Here, we need the struct keyword since the structre declaration is
	 * not yet complete and C++ doesn't yet know what "Node" is.
	 * So, we just ask it to make a pointer to a struct.
 	 */
};

void print(Node* cur);

int main()
{
	/* We declare 3 pointers to the Structure type and set them to NULL.
	 * We always need a pointer to the very first element or we risk losing
	 * the entire list. Once we assign a node as "head" we don't change it 
	 * except for very special circumstances.
	 * the other two pointers are required to hold the last element and the
	 * new Node being created.
	 */
	Node *head = NULL, *pre =NULL, *cur= NULL;
	
	// We're going to read until the user enters 0 and add each number to the list
	cout << "enter the numbers in the list (0 to stop): " << endl;
	int num;
	cin >> num;

	while (num != 0)
	{
		/* We make a new node. We copy the number the user entered into
		 * val. We set the next pointer to NULL temporarily.
		 */
		cur = new Node;
		cur->val = num;
		cur->next = NULL;

		// If head is NULL, then we are adding the first element
		if (head == NULL)
		{
			head = cur;
			pre = head; // the fist node is also the last node.
		}
		else
		{
			// Attach the new node to the end of the list
			pre->next = cur;
			// The new node is now the last node
			pre = cur;
		}
		// get the next number
		cin >> num;
	}

	// We can call the print function to print the list
	print(head);

	/* We need to delete the list. We need two pointers here. Once points 
	 * at the current node. The other one at the next node. Then we delete 
	 * the current node, and the next node becomes the current node.
	 * We keep doing this until the current node is NULL, which means
	 * all the nodes have been deleted.
	 */
	cur = head;
	pre = head;
	while (cur != NULL)
	{
		pre = cur->next;
		delete cur;
		cur = pre;
	}
}

/* this function accepts a pointer to the Node structure.
 * We can keep moving the pointer to the next node once we print the value of the
 * current node. If the current node becomes NULL, we have reached the end and 
 * we're done printing.
 * Since main has the head pointer secured, we don't have to worry about 
 * securing the head pointer here.
 */
void print(Node *head1)
{
	while (head1 != NULL)
	{
		cout << head1->val<< "\t";
		head1 = head1->next;
	}
}