#include <iostream>
#include <fstream>
using namespace std;

ifstream doc("input.txt");

struct Node{
	int number;
	Node* next;
};

struct List{
	Node* head;
	Node* tail;
};

void createEmptylist(List &list){
	list.head = list.tail = NULL;
}

Node *createNode(int x){
	Node* newNode = new Node;
	if (newNode != NULL){
		newNode->number = x;
		newNode->next = NULL;
	}
	return newNode;
}

void ATH(List &list, int x){
	Node *p = createNode(x);
	if (list.head == NULL){
		list.head = list.tail=p;
	}
	else{
		p->next = list.head;
		list.head = p;
	}
}

void ATT(List &list, int x){
	Node *p = createNode(x);
	if (list.tail == NULL){
		list.tail = list.head= p;
	}
	else{
		list.tail->next = p;
		list.tail = p;
	}
}

int count(List &list){
	int i = 0;
	for (Node *p = list.head; p; p = p->next){
		i++;
	}
	return i;
}

void DT(List &list){
	Node *p = list.head;
	if (p == NULL) return;
	else{
		while (p->next != list.tail){
			p = p->next;
		}
		p->next = NULL;
		delete(list.tail);
		list.tail = p;
	}
}

int search(List &list, int x){
	int i = 0;
	for (Node *p = list.head; p; p = p->next){
		i++;
		if (x == p->number){
			cout << "Da tim thay tai Node " << i << endl;
		}
	}
	return i;
}

void DH(List &list){
	Node *p = list.head;
	if (p == NULL) return;
	else{
		if (count(list) == 1)
		{
			cout << "Ko the xoa duoc";
		}
		else{
			Node *tam = p;
			list.head = p->next;
			delete(tam);
		}
	}
}

int SAD(List &list, int x){
	Node *p = list.head;
	int k = -1;
	while (p!=NULL && p->number != x)
		p = p->next;
	if (p->number == x && p == list.head){
		DH(list);
	}
	if (p->number == x && p == list.tail) DT(list);
	else{
			Node *q = list.head;
			while (q->next != p) q = q->next;
			q->next = p->next;
			delete(p);
	}
	return k;
}

void AN(List &list, int x, int k){
	Node *newNode = createNode(x);
	int i = 1;
	if (k == 1){
		ATH(list, x);
	}
	else{
		Node *p = list.head;
		while (p != NULL && i != k - 1){
			i++;
			p = p->next;
		}
		newNode->next = p->next;
		p->next = newNode;
	}
}

void xuat(List list){
	int i = 1;
	for (Node *p = list.head; p; p = p->next){
		cout << "Node " << i++ << ": " << p->number << endl;
	}
}


int menu(){
	cout << "1. Them vao dau danh sach";
	cout << "\n2. Them vao cuoi danh sach";
	cout << "\n3. Tim phan tu trong danh sach";
	cout << "\n4. Xoa phan tu dau danh sach";
	cout << "\n5. Xoa phan tu cuoi danh sach";
	cout << "\n6. Tim va Xoa phan tu";
	cout << "\n7. Them phan tu";
	cout << "\n8. Xuat danh sach";
	cout << "\n0. Ket thuc";
	cout << endl;
	int chon;
	cout << "\nMoi ban chon: ";
	cin >> chon;
	return chon;
}

void main(){
	int x;
	int k;
	List list;
	createEmptylist(list);
	do{
		int chon = menu();
		switch (chon)
		{
		case 1:
			doc >> x;
			ATH(list, x);
			cout << endl;
			break;
		case 2:
			doc >> x;
			ATT(list, x);
			cout << endl;
			break;
		case 3:
			cout << "Nhap phan tu can tim: ";
			cin >> x;
			search(list, x);
			cout << endl;
			break;
		case 4:
			DH(list);
			break;
		case 5:
			DT(list);
			break;
		case 6:
			cout << "Nhap vao phan tu can tim va xoa: ";
			cin >>x;
			SAD(list, x);
			cout << endl;
			break;
		case 7:
			cout << "Nhap vao phan tu muon them va vi tri them vao: ";
			cin >> x >> k;
			AN(list, x, k);
			cout << endl;
			break;
		case 8:
			xuat(list);
			break;
		default:
			cout << "Tam biet.";
			cout << endl;
			break;
		}
		if (chon < 1)
			break;
	} while (1);
	doc.close();
}