#include<iostream.h>
template<class T>class HeaderList;
template<class T>
class Node
{
	private:
		T element;
		Node<T>*link;
		friend class HeaderList<T>;
		
};
template<class T>
class HeaderList
{
	public:
	HeaderList();
	~HeaderList();
	bool IsEmpty()const;
    int  Length()const;
	bool Insert(int i,T x);
	bool Delete(int i);
	void Invert();
	void Clear();
	void Output(ostream& out)const;
	private:
		Node<T>*first;
		int n;
};
template<class T>
HeaderList<T>::HeaderList()
{
	first=new Node<T>;
	first->link=NULL;
	n=0;
}
template<class T>
HeaderList<T>::~HeaderList()
{
	Node<T>*p=first;

	
	while(first)
	{
		p=first->link;
		delete first;
		first=p;
	}
}
template<class T>
int HeaderList<T>::Length()const
{return n;}
template<class T>
bool HeaderList<T>::IsEmpty()const
{return n==0;}

//template<class T>

template<class T>
bool HeaderList<T>::Insert(int i,T x)
{
	if(i<-1||i>n-1)
	{cout<<"Out of Bounds"<<endl;return false;}
	Node<T>*q=new Node<T>;
	q->element=x;
	Node<T> *p=first;
	for(int j=0;j<=i;j++)
		p=p->link;

	q->link=p->link;
	p->link=q;
	n++;
	return true;
}
template<class T>
bool HeaderList<T>::Delete(int i)
{
	if(!n){cout<<"UnderFlow"<<endl;return false;}
	if(i<0||i>n-1)
	{cout<<"Out of bounds"<<endl;return false;}
	Node<T>*q=first,*p;
	for(int j=0;j<i;j++)
		q=q->link;
	p=q->link;
	q->link=p->link;
	delete p;
	n--;return true;
}
template<class T>
void HeaderList<T>::Invert()
{
	Node<T>*p,*q;
	p=first->link;
	first->link=NULL;
	while(p)
	{
		q=p->link;
		p->link=first->link;
		first->link=p;
		p=q;
	}
}
template<class T>
void HeaderList<T>::Output(ostream& out)const
{
	Node<T>*p=first->link;
	while(p)
	{
		out<<p->element<<" ";
		p=p->link;
	}
	out<<endl;
}
void main()
{
	HeaderList<int> a;
	int m;
    for(m=0;m<5;m++)
		a.Insert(m-1,m);
	a.Output(cout);
	a.Delete(4);
	a.Output(cout);
	a.Invert();
	a.Output(cout);
}