#include <iostream>
#include <stdio.h>
#include <malloc.h>

/*
struct Node
*/
struct node{
	int Data;
	node *Next;
};

/*
struct List
*/
struct List{
	node *Head; // node dau
	node *Tail; // node cuoi
};

/*
 Khoi tao List
*/
void Init(List *L)
{
	L->Head = L->Tail = NULL;
}

/*
 Tao Node

 return Node
*/
node *CreateNode(int x)
{
	node* p = (node*)malloc(sizeof(node)); // cap phat bo nho
	if(p == NULL) // kiem tra neu bo nho day
	{
		return NULL; // return NULL
	}
	p->Next = NULL;
	p->Data = x;
	return p;
}
/*
	return true neu danh sach rong
*/
bool isEmpty(List L)
{
	return (L.Head == NULL);
}
/*
	them vao dau
*/
void AddHead(List *L, int value)
{
	node *p = CreateNode(value);
	if(isEmpty(*L))
	{
		L->Head = L->Tail = p;
	}
	else
	{
		p->Next = L->Head;
		L->Head = p;
	}
}

/*
 them vao duoi
*/
void AddTail(List *L, int value)
{
	node *p = CreateNode(value);
	if(isEmpty(*L))
	{
		L->Head = L->Tail = p;
	}
	else
	{
		L->Tail->Next = p;
		L->Tail = p;
	}
}

/*
	Addat(&L, 3, 1);
	them vao vi tri bat ki
*/
void Addat(List *L, int position, int value)
{
	int count = 0;
	if(position == 0)
	{
		AddHead(L, value);
	}
	else
	{
		node *p = L->Head;
		while( p != NULL )
		{
			if(position == count)
			{
				node *temp = CreateNode(value);
				temp->Next = p->Next;
				p->Next = temp;
				break;
			}
			count++;
			p = p->Next;
		}
	}
}
void Input(List *L, int n)
{
	for(int i = 0; i < n; i++)
	{
		int x;
		printf("Nhap so phan tu thu [%d] = ", i);
		scanf("%d", &x);
		AddTail(L, x);
	}
}

void Print(List L)
{
	for(node *p = L.Head; p != NULL; p = p->Next)
	{
		printf("%d->", p->Data);
	}
}

int Lenght(List L)
{
	int Count = 0;
	for(node *p = L.Head; p!= NULL; p = p->Next)
	{
		Count++;
	}
	return Count;
}


node *GetNode(List L, int x)
{
	node *p = L.Head;

	while(p!=NULL)
	{
		if(p->Data == x)
		{
			return p;
		}
		else
		{
			p=p->Next;
		}
	}
	return p;
}

void DeleteFisrtData(List *L)
{
	node *p = L->Head;
	L->Head = L->Head->Next;
	free(p);
}

void DeleteLastData(List *L)
{
	node *p;
	node *k = L->Head;
	while(k != NULL)
	{
		if(k == L->Tail)
		{
			L->Tail = p;
			L->Tail->Next = NULL;
			free(k);
			break;
		}
		p = k;
		k=k->Next;
	}
}

void Delete(List *L, int value)
{
	if(L->Head->Data == value)
	{
		DeleteFisrtData(L);
	}
	if(L->Tail->Data == value)
	{
		DeleteLastData(L);
	}
	node *k = L->Head->Next;
	node *p;
	while( k!= NULL)
	{
		if(k->Data == value)
		{
			p->Next = k->Next;
			free(k);
			return;
		}
		p = k;
		k = k->Next;
	}

}

void Swap(node *p, node *q)
{
	int temp;
	temp = p->Data;
	p->Data = q->Data;
	q->Data = temp;
}

void Sort(List *L)
{
	node *p = L->Head;
	while( p != NULL)
	{
		node *k = p->Next;
		while(k != NULL)
		{
			if(p->Data < k->Data)
			{
				Swap(p, k);
			}
			k = k->Next;
		}
		p = p->Next;
	}
}

void Menu()
{
	printf("\n1: Add head");
	printf("\n2: Add hail");
	printf("\n3: Add at posiotion");
	printf("\nYour choice: ");
}

int main()
{
	List L;
	int n, value, position;
	Init(&L);
	AddTail(&L, 1);
	AddTail(&L, 2);
	AddTail(&L, 5);
	AddTail(&L, 3);
	Print(L);
	printf("\n");
	printf("Nhap gia tri muon them: "); scanf("%d", &n);
	printf("Nhap vi tri muon them:  "); scanf("%d", &position);

	Addat(&L, position, n);
	printf("\nsau khi them\n");

	Print(L);
	system("pause");
	return 0;
}