C++实现带头节点的双向循环链表模板

#include<iostream>
using namespace std;

template<class T>
struct Nodetype{
	Nodetype(const T& data = T())
	: _pNext(NULL)
	, _pPre(NULL)
	, _data(data)
	{}

	Nodetype<T>* _pNext;
	Nodetype<T>* _pPre;
	T _data;
};

template<class T>
class ListIterator{
	typedef Nodetype<T>* pNode;
	typedef ListIterator<T> Self;
public:
	ListIterator()
		:_pCur(NULL)
	{}
	ListIterator(pNode pCur)
		: _pCur(pCur)
	{}
	ListIterator(const Self& s)
		: _pCur(s._pCur)
	{}
	Self& operator++()
	{
		_pCur = _pCur->_pNext;
		return *this;
	}
	Self operator++(int)
	{
		Self temp(*this);
		_pCur = _pCur->_pNext;
		return temp;
	}
	Self& operator--()
	{
		_pCur = _pCur->_pPre;
		return *this;
	}
	Self operator--(int)
	{
		Self temp(*this);
		_pCur = _pCur->_pPre;
		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _pCur != s._pCur;
	}
	bool operator==(const Self& s)
	{
		return _pCur == s._pCur;
	}
	T& operator*()
	{
		return _pCur->_data;
	}
	T* operator->()
	{
		return *(_pCur->_data);
	}
private:
	pNode _pCur; 
};


template<class T>
class List{
	typedef Nodetype<T> Node;
	typedef Node* pNode;
public:
	typedef ListIterator<T> Iterator;
public:
	List()
	{
		CreatListHead();
	}

	List(T* arr, size_t size)
	{
		//创建头节点
		CreatListHead();
		for (size_t i = 0; i < size; ++i)
		{
			PushBack(arr[i]);
		}
	}

	List(const List<T>& l);
	List<T>& operator=(const List<T>& l);
	~List();
	void PushBack(const T& data);
	void PopBack(const T& data);
	void PushFront(const T& data);
	void PopFront(const T& data);
	void Clear();
	void Print();
	//pNode Insert(pNode pos, const T& data);
	pNode Insert(pNode pos, const T& data){
		pNode pNewNode = new Node(data);
		pos->_pPre->_pNext = pNewNode;
		pNewNode->_pPre = pos->_pPre;
		pos->_pPre = pNewNode;
		pNewNode->_pNext = pos;
		return pNewNode;
	}
	//pNode Erase(pNode pos);
	pNode Erase(pNode pos){
		pNode pCur = pos->_pNext;
		pos->_pPre->_pNext = pos->_pNext;
		pos->_pNext->_pPre = pos->_pPre;
		delete pos;
		return pCur;
	}

	size_t size();

	bool Empty()const
	{
		if (pHead->_pNext == pHead)
			return true;
		return false;
	}

	Iterator Begin()
	{
		return Iterator(pHead->_pNext);
	}
	Iterator End()
	{
		return Iterator(pHead);
	}

private:
	void CreatListHead()
	{
		pHead= new Node;
		pHead->_pNext = pHead;
		pHead->_pPre = pHead;
	}

	pNode pHead;
};

template<class T>
void List<T>::PushBack(const T& data){
	pNode pTail = pHead->_pPre;
	pNode pNewNode = new Node(data);
	pTail->_pNext = pNewNode;
	pNewNode->_pPre = pTail;
	pNewNode->_pNext = pHead;
	pHead->_pPre = pNewNode;
}

template<class T>
void List<T>::PopBack(const T& data){
	if (Empty())
		return;
	pNode pProTail = pHead->_pPre->_pPre;
	delete pProTail->_pNext;
	pProTail->_pNext = pHead;
	pHead->_pPre = pProTail;
}

template<class T>
void List<T>::PushFront(const T& data){
	pNode pNewNode = new Node(data);
	pNewNode->_pNext = pHead->_pNext;
	pHead->_pNext->_pPre = pNewNode;
	pHead->_pNext = pNewNode;
	pNewNode->_pPre = pHead;
}

template<class T>
void List<T>::PopFront(const T& data){
	if (Empty())
		return;
	pNode pTail = pHead->_pNext;
	pHead->_pNext = pTail->_pNext;
	pTail->_pNext->_pPre = pHead;
	delete pTail;
}

//template<class T>
//pNode List<T>::Insert(pNode pos, const T& data){
//	pNode pNewNode = new Node(data);
//	pos->_pPre->_pNext = pNewNode;
//	pNewNode->_pPre = pos->_pPre;
//	pos->_pPre = pNewNode;
//	pNewNode->_pNext=pos;
//	return pNewNode;
//}

//template<class T>
//List<T>::pNode List<T>::Erase(pNode pos){
//	pNode pCur = pos->_pNext;
//	pos->_pPre->_pNext = pos->_pNext;
//	pos->_pNext->_pPre = pos->_pPre;
//	delete pos;
//	return pCur;
//}

template<class T>
size_t List<T>::size(){
	pNode pCur = pHead->_pNext;
	size_t count = 0;
	while (pCur != pHead){
		count++;
		pCur = pHead->_pNext;
	}
	return count;
}

template<class T>
void List<T>::Clear(){
	pNode pDel = pHead->_pNext;
	while (!Empty()){
		pDel = pHead->_pNext;
		pHead->_pNext = pDel->_pNext;
		delete pDel;
	}
}

template<class T>
List<T>::~List(){
	Clear();
	delete pHead;
	pHead = NULL;
}

template<class T>
List<T>::List(const List<T>& l){
	pHead = new Node();
	pHead->_pNext = pHead;
	pHead->_pPre = pHead;

	pNode pCur = (l.pHead)->_pNext;
	while (pCur != l.pHead)
	{
		this->PushBack(pCur->_data);
		pCur = pCur->_pNext;
	}
}

template<class T>
List<T>& List<T>::operator=(const List<T>& l){
	if (this != &l)
	{
		this->Clear();
		pNode pCur = (l.pHead)->_pNext;
		while (pCur != l.pHead)
		{
			this->PushBack(pCur->_data);
			pCur = pCur->_pNext;
		}
	}
	return *this;
}

template<class T>
void List<T>::Print()
{
	pNode pCur = pHead->_pNext;
	while (pCur != pHead)
	{
		cout << pCur->_data << " ";
		pCur = pCur->_pNext;
	}
	cout << endl;
}

void Test1()//尾部插入和删除
{
	//插入
	List<int> l;
	l.PushBack(1);
	l.Print();
	l.PushBack(2);
	l.Print();
	l.PushBack(3);
	l.Print();
	l.PushBack(4);
	l.Print();

	//删除
	l.PopBack(1);
	l.Print();
	l.PopBack(1);
	l.Print();
	l.PopBack(1);
	l.Print();
}

void Test2()//头部插入和删除
{
	//插入
	List<int> l;
	l.PushFront(1);
	l.Print();
	l.PushFront(2);
	l.Print();
	l.PushFront(3);
	l.Print();

	//删除
	l.PopFront(1);
	l.Print();
	l.PopFront(1);
	l.Print();
	l.PopFront(1);
	l.Print();
}

int main()
{
	Test1();
	//Test2();
	system("pause");
	return 0;
}