//BT CTDL so 1
//Nguyen Le Hoang Chuong - 0650080089
//Lop: 06_ÐHCNTT3
#include <iostream.h>
using namespace std;
struct Node
{
	int data;
	Node* pNext;
};
typedef struct Node NODE;
struct List
{
Node* pHead;
Node* pTail;
};
typedef struct List LIST;
void Init(List &l)
{
l.pHead = l.pTail = NULL;
}
NODE* GetNODE(int x) 
{
	NODE *p = new NODE;
	if(p == NULL)
	{
		return NULL;
	}
	p->data = x;
	p->pNext = NULL;
	return p;
}
void AddHead(LIST &l,NODE *p)
{
	if(l.pHead == NULL) 
	{
		l.pHead = l.pTail = p;
	}
	else
	{
		p ->pNext = l.pHead; 
		l.pHead = p; 		 
	}
}
void themdauds(List &l, Node* new_node)
{
if (l.pHead == NULL)	// DS r?ng
{
l.pHead = l.pTail = new_node;
}
else
{
new_node->pNext = l.pHead;  
l.pHead = new_node;
}
}
void themcuoids(List &l, Node *new_node)
{
if (l.pHead == NULL)
{
l.pHead = l.pTail = new_node;
}
else
{
l.pTail->pNext = new_node;
l.pTail = new_node ;
}
}

void ThemGiua(LIST &l, NODE *p, NODE *q)
{
	for (NODE *k = l.pHead; k != NULL; k = k->pNext)
	{
		if (k->data == q->data) // Tìm thay q ne
		{
			NODE *q = k->pNext;
			k->pNext = p;
			p->pNext = q;
			return; // Ket thúc
		}
	}
}
int xoadauds(List &l)
{
	if (l.pHead == NULL)
		return 0;
	Node* p=l.pHead;  
	l.pHead = p->pNext;
	if (l.pHead == NULL)	
		l.pTail=NULL; //Neu danh sách rong
	delete p;
	return 1;
}
void xoagiuads(List &l, int k)
{
    Node *p=l.pHead;
    Node *q=NULL;
   while(p)
   {
       if(p->data==k)
       break;
       q=p;
       p=p->pNext;     //p luon duyet truoc q 1 node
   }
   if(p==NULL)
   cout<<"sv tim thay";
    if(q!=NULL)
    {
        if(p!=NULL)
        {
            q->pNext=p->pNext;
            delete (p);
            if(p==l.pTail) l.pTail=q;
            delete(p);
        }
    }
    else
    {
        l.pHead=p->pNext;
        delete(p);
        if(l.pHead==NULL)  l.pTail=NULL;
    }
}
void xoacuoids(List &l)
{
	NODE *p;
	for(NODE *k = l.pHead; k != NULL; k = k ->pNext)
	{
		if(k == l.pTail)
		{
			l.pTail = p;
			l.pTail ->pNext = NULL;
			delete k;
			return;
		}
		p = k;
	}
}
int timkiem(List &l, int value)
{
    int position = 1;
    for(Node *p = l.pHead; p != NULL; p = p->pNext)
	{
        if(p->data == value){
            return position;
        }
        position++;
    }
    return -1;
}
void InPut(LIST &l,int n)
{
	Init(l); 
	for(int i = 1; i <= n; i++)
	{
		int x;
		cout<<"a["<<i<<"]= ";
		cin>>x;
		
		NODE *p = GetNODE(x); 
		AddHead(l, p);
	}
}
void OutPut(LIST &l)
{
	for(NODE *p = l.pHead; p != NULL; p = p ->pNext)
	{
		cout<<" "<<p->data;
	}
	cout<<"\n";
}
int main(int argc, char *argv[])
{
	LIST l;
	int n;
	string ten;
	cout<<"Nhap ho ten cua ban: ";
	getline(cin,ten);
	cout<<"Ban muon nhap bao nhieu Node: ";
	cin>>n;
	InPut(l,n);
	cout<<"Danh sach ban da nhap la:\n";
	OutPut(l);
	int x;  
	cout<<"Nhap X de them vao dau ds= ";  
	cin>>x;
	Node* new_node = GetNODE(x);
	if (new_node != NULL)  
	themdauds(l, new_node);
	OutPut(l);
	int vt,gt;
	cout<<"Nhap vi tri ban muon them node phia truoc= ";
	cin>>vt;
	NODE* k=GetNODE(vt);
	cout<<"Nhap gia tri = ";
	cin>>gt;
	NODE* h=GetNODE(gt);
	ThemGiua(l,h,k);
	OutPut(l);
	int y;
	cout<<"Nhap y de them vao cuoi ds= ";  
	cin>>y;
	NODE* cuoi=GetNODE(y);
	themcuoids(l,cuoi);
	OutPut(l);
	cout<<"Xoa phan tu dau danh sach:\n";
	xoadauds(l);
	OutPut(l);
	int r;
	cout<<"chon vi tri can xoa :\n";
	cin>>r;
	xoagiuads(l,r);
	OutPut(l);
	cout<<"Xoa phan tu o cuoi danh sach\n";
	xoacuoids(l);
	OutPut(l);
	int stt;
	cout<<"Nhap STT cua sv ban muon tim: ";
	cin>>stt;
	cout<<"vi tri cua STT la: "<<timkiem(l,stt)<<endl;
	return 0;
}