template <class T>
struct elem_link1
{
	T inf;
	elem_link1<T> *link;
};

template <class T>
class LList
{
public:
	LList();
	~LList();
	LList(LList const &);
	LList& operator=(LList const &);
	bool empty() const;
	void IterStart(elem_link1<T>* = NULL);
	elem_link1<T>* Iter();
	void ToEnd(T const &);
	void InsertAfter(elem_link1<T> *, T const &);
	void InsertBefore(elem_link1<T> *, T const &);
	void DeleteElem(elem_link1<T> *, T &);
	int DeleteAfter(elem_link1<T> *, T &);
	int DeleteBefore(elem_link1<T> *, T &);
	int length();
	void concat(LList const &);
	void reverse();
	void print();
private:
	elem_link1<T> *Start,
				  *End,
				  *Current;
	void DeleteList();
	void CopyList(LList<T> const &);
};

template <class T>
LList<T>::LList()
{
	Start = End = Current = NULL;
}

template <class T>
LList<T>::~LList()
{
	DeleteList();
}

template <class T>
LList<T>::LList(LList<T> const &r)
{
	CopyList(r);
}

template <class T>
LList<T>& LList<T>::operator=(LList<T> const &r)
{
	if (this != &r)
	{
		DeleteList();
		CopyList(r);
	}

	return *this;
}


template <class T>
void LList<T>::DeleteList()
{
	if (Start)
	{
		elem_link1<T> *p;
		while (Start)
		{
			p = Start;
			Start = Start->link;
			delete p;
		}
		End = NULL;
	}
}

template <class T>
void LList<T>::CopyList(LList<T> const &r)
{
	Start = End = NULL;
	elem_link1<T> *p = r.Start;
	while (p)
	{
		ToEnd(p->inf);
		p = p->link;
	}
}

template <class T>
bool LList<T>::empty() const
{
	return Start == NULL;
}

template <class T>
void LList<T>::IterStart(elem_link1<T> *p)
{
	if (p)
		Current = p;
	else
		Current = Start;
}

template <class T>
elem_link1<T>* LList<T>::Iter()
{
	elem_link1<T> *p = Current;
	if (Current)
		Current = Current->link;
	return p;
}

template <class T>
int LList<T>::length()
{
	int n = 0;
	IterStart();
	while (Iter())
		n++;
	return n;
}

template <class T>
void LList<T>::ToEnd(T const &x)
{
	Current = End;
	End = new elem_link1<T>;
	End->inf = x;
	End->link = NULL;
	if (Current)
		Current->link = End;
	else
		Start = End;
}

template <class T>
void LList<T>::InsertAfter(elem_link1<T> *p, T const &x)
{
	elem_link1<T> *q = new elem_link1<T>;
	q->inf = x;
	q->link = p->link;
	if (p == End)
		End = q;
	p->link = q;
}

template <class T>
void LList<T>::InsertBefore(elem_link1<T> *p, T const &x)
{
	elem_link1<T> *q = new elem_link1<T>;
	*q = *p;
	p->inf = x;
	p->link = q;
	if (End == p)
		End = q;
}

template <class T>
int LList<T>::DeleteAfter(elem_link1<T> *p, T &x)
{
	if (p == End)
		return 0;
	elem_link1<T> *q = p->link;
	x = q->inf;
	p->link = q->link;
	if (End == q)
		End = p;
	delete q;
	return 1;
}

template <class T>
void LList<T>::DeleteElem(elem_link1<T> *p, T &x)
{
	if (p == Start)
	{
		x = p->inf;
		if (Start == End)
		{
			Start = NULL;
			End = NULL;
			delete p;
		}
		else
		{
			Start = Start->link;
			delete p;
		}
	}
	else
	{
		elem_link1<T> *q = Start;
		while (q->link != p)
			q = q->link;
		DeleteAfter(q,x);
	}
}

template <class T>
int LList<T>::DeleteBefore(elem_link1<T> *p, T &x)
{
	if (p == Start)
		return 0;
	elem_link1<T> *q = Start;
	while (q->link != p)
		q = q->link;
	DeleteElem(q,x);
	return 1;
}

template <class T>
void LList<T>::concat(LList<T> const &L)
{
	elem_link1<T> *p = L.Start;
	while (p)
	{
		ToEnd(p->inf);
		p = p->link;
	}
}

template <class T>
void LList<T>::reverse()
{
	LList<T> L;
	elem_link1<T> *p = Start;
	if (p)
	{
		L.ToEnd(p->inf);
		p = p->link;
		while (p)
		{
			L.InsertBefore(L.Start, p->inf);
			p = p->link;
		}
	}
	*this = L;
}

template <class T>
void LList<T>::print()
{
	elem_link1<T> *p = Start;
	while (p)
	{
		cout<< p->inf <<" ";
		p = p->link;
	}
	cout<<"\n";
}