// Linked list demo 3
// By DreamVB 23:15 04/10/2016

#include <iostream>

using namespace std;
using std::cout;
using std::endl;

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

Node *head = NULL;
int UserData = 0;

void IsertNodeFirst(int somevalue){
	Node *temp;
	//Create room for new node.
	temp = (Node*)malloc(sizeof(Node));
	//Set node value
	temp->data = somevalue;
	//Set temp node to head
	temp->next = head;
	//Set head to temp
	head = temp;
}

void IsertNodeLast(int somevalue){
	Node *temp;
	Node *Temp2;

	if (head == NULL){
		temp = (Node*)malloc(sizeof(Node));
		temp->data = somevalue;
		temp->next = NULL;
		head = temp;
	}
	else{
		//Create space for node
		temp = (Node*)malloc(sizeof(Node));
		//Set temp to head first node
		temp = head;

		while (temp->next != NULL){
			//Move to next node
			temp = temp->next;
		}
		//Add the node at the end of the list
		Temp2 = (Node*)malloc(sizeof(Node));
		Temp2->data = somevalue;
		Temp2->next = NULL;
		temp->next = Temp2;
	}
}

void NodeDelete(int index){
	Node *temp1;
	Node *temp2;
	int i = 1;

	//The linked list is empty just return
	if (head == NULL){
		return;
	}

	//Check for only one item in the list.
	if (head->next == NULL){
		head = NULL;
		return;
	}

	//Create space for temp1 and temp2 to hold node
	temp1 = (Node*)malloc(sizeof(Node));
	temp2 = (Node*)malloc(sizeof(Node));

	//Set temp to the head node
	temp1 = head;
	//Set temp to temp1
	temp2 = temp1;

	if ((index == 0) | (index == 1)){
		//Get the next node.
		head = temp1->next;
		//Delete prev node
		delete temp1;
		//Return
		return;
	}

	while (i < index){
		temp2 = temp1;
		//Get next node
		temp1 = temp1->next;
		//INC counter
		i++;
	}

	//Set temp2 to next node in list
	temp2->next = temp1->next;
	//Delete temp1 node.
	delete temp1;

}

void DisplayNodes(){
	int i = 0;
	Node *cur = head;

	//This lists all the nodes in the list
	while (cur != NULL){
		//Print out node data
		cout << cur->data << endl;
		//Move to next node.
		cur = cur->next;
	}
}

void GetUserValue(){
	cout << "Enter a number: ";
	cin >> UserData;
}

int main(int argc, char *argv[]){
	char c = '\0';

	//Main menu
	do{
		cout << "(A) Insert node at beginning " << endl;
		cout << "(B) Insert node at end" << endl;
		cout << "(C) List nodes" << endl;
		cout << "(D) Delete node at index" << endl;
		cout << "(Q) Exit" << endl << endl;
		cout << "Enter a choice: ";
		cin >> c;
		//Convert to uppercase
		c = toupper(c);
		system("cls");

		switch (c){
			case 'Q':
				cout << "Are you sure you want to exit Yes(Y) / No(N) ";
				cin >> c;
				if((c=='y') || (c=='Y')){
					c = 'Q';
					break;
				}
				system("cls");
				break;
			case 'A':
				GetUserValue();
				IsertNodeFirst(UserData);
				system("cls");
				break;
			case 'B':
				GetUserValue();
				IsertNodeLast(UserData);
				system("cls");
				break;
			case 'C':
				cout << "Linked list contents: " << endl;
				DisplayNodes();
				system("pause");
				system("cls");
				break;
			case 'D':
				cout << "Enter index of node: ";
				cin >> UserData;
				NodeDelete(UserData);
				system("cls");
				break;
			default:
				cout << "Invaild choice entered." << endl << endl;
				break;
		}
	} while (c != 'Q');

	return 0;
}