双向链表---C++实现

双向链表在类中的实现

#include<stdio.h>#include<assert.h>#include<iostream>using namespace std;typedef int DataType;struct Node{	Node(const DataType& data)		: _pNext(NULL)		, _pPRe(NULL)		, _data(data)	{}	Node* _pNext;	Node* _pPre;	int _data;};class List{public:	explicit List()		:_pHead(NULL)		,_pTail(NULL)		,_size(0)	{}	List(const List& l)	{		Node* pTemp = l._pHead;		Node* pNode1 = new Node(pTemp->_data);   //创建一个新节点作为新链表的头节点		Node* pNewTemp = pNode1;                //创建一个临时变量指针指向新链表的头节点		_pHead = pNode1;		size_t ret = l._size;		while(--ret)                            //循环里创建ret-1个节点		{			pTemp = pTemp->_pNext;			Node* pNode2 = new Node(pTemp->_data);  //复制l链表值为pTemp->_data的节点			pNewTemp->_pNext = pNode2;             //将新创建的节点与新链表连接起来			pNode2->_pPre = pNewTemp;			if(ret != 1)                          //判断是否是最后一个节点，若不是，则临时指针指向下一个节点			{				pNewTemp = pNewTemp->_pNext ;			}			else                                  //若是最后一个节点，则尾指针指向空			{				pNode2->_pNext = NULL;			}		}		_size = l._size;	}	List(size_t n, const DataType& data = DataType())	{		Node* pNode1 = new Node(data);		Node* pNewTemp = pNode1;		_pHead = pNode1;		size_t ret = n;		while(--ret)		{			Node* pNode2 = new Node(data);			pNewTemp->_pNext = pNode2;			pNode2->_pPre = pNewTemp;			if(ret != 1)			{				pNewTemp = pNewTemp->_pNext ;			}			else			{				pNode2->_pNext = NULL;			}		}		_size = n;	}	List& Operator=(const List& l)   //与拷贝构造函数类似	{		if(this != &l)		{			Node* pTemp = l._pHead;			Node* pNode1 = new Node(pTemp->_data);			Node* pNewTemp = pNode1;			_pHead = pNode1;			size_t ret = l._size;			while(--ret)			{				pTemp = pTemp->_pNext;				Node* pNode2 = new Node(pTemp->_data);				pNewTemp->_pNext = pNode2;				pNode2->_pPre = pNewTemp;				if(ret != 1)				{					pNewTemp = pNewTemp->_pNext ;				}				else				{					pNode2->_pNext = NULL;				}			}			_size = l._size;		}		return *this;	}	//////////Capacity///////////////////////	size_t Size()const	{		return _size;	}	size_t Empty()const	{		return (0==_size);	}	////////Acess///////////////////	Node& Front()	{		assert(_pHead);		return *_pHead;	}	const Node& Front()const	{		assert(_pHead);		return *_pHead;	}	Node& Back()	{		assert(_pHead);		Node* pTemp = _pHead;		while(--_size)		{			pTemp = pTemp->_pNext;		}		return *pTemp;	}	const Node& Back()const	{		assert(_pHead);		Node* pTemp = _pHead;		size_t ret = _size;		while(--ret)		{			pTemp = pTemp->_pNext;		}		return *pTemp;	}	////////////Modify/////////////////////////	void Assign(size_t n, const DataType& data)	{		Node* pTemp = _pHead;		Node* pNode1 = new Node(data);		Node* pNewTemp = pNode1;		_pHead = pNode1;		size_t ret = n;		while(--ret)		{			pTemp = pTemp->_pNext;			Node* pNode2 = new Node(data);			pNewTemp->_pNext = pNode2;			pNode2->_pPre = pNewTemp;			if(ret != 1)			{				pNewTemp = pNewTemp->_pNext ;			}			else			{				pNode2->_pNext = NULL;			}		}		_size = n;	}	void PushBack(const DataType& data)	{		Node* pNewNode = new Node(data);		if(NULL == _pHead)		{			_pHead = pNewNode;			pNewNode->_pNext = NULL;			pNewNode->_pPre = _pHead;			_size = _size+1;		}		else		{			Node* pTemp = _pHead;			size_t ret = _size;			while(--ret)			{				pTemp = pTemp->_pNext;			}			pTemp->_pNext = pNewNode;			pNewNode->_pPre = pTemp;			pNewNode->_pNext = NULL;			_size = _size+1;		}	}	void PopBack()	{		if(NULL == _pHead)//链表不存在		{			return;		}		if(1 == _size) //只有一个节点		{			delete _pHead;			_pHead = _pTail = NULL;			_size = 0;		}		else //多个节点		{			Node* pTemp = _pHead;			while(pTemp->_pNext)			{				pTemp = pTemp->_pNext;			}			_pTail = pTemp;			Node* pTemp1 = _pTail;			_pTail = _pTail->_pPre;			_pTail->_pNext = NULL;			delete pTemp1;			_size = _size-1;		}	}	void PushFront(const DataType& data)	{		Node* pNode = new Node(data);		if(NULL == _pHead)//链表没有节点		{			_pHead = pNode;			_size = _size+1;		}		else//链表有一个或多个节点		{			Node* pTemp = _pHead;			_pHead = pNode;			pNode->_pNext = pTemp;			pTemp->_pPre = _pHead;			_size = _size+1;		}	}	void PopFront()	{		if(NULL == _pHead)  //链表没有节点		{			return;		}		else if(1 == _size)//链表有一个节点		{			delete _pHead;			_pHead = _pTail = NULL;			_size = 0;		}		else              //链表有一个或多个节点		{			Node* pTemp = _pHead;     			_pHead = _pHead->_pNext;			_pHead->_pPre  = NULL;			delete pTemp;			_size = _size-1;		}	}	Node* Find(const DataType& data)	{		Node* pTemp = _pHead;		if(NULL == _pHead)		{			return NULL;		}		else		{			while(pTemp)			{				if(pTemp->_data == data)				{					return pTemp;				}				pTemp =pTemp->_pNext;			}			return NULL;		}			}	void Insert(Node* pos, const DataType& data)	{		if(NULL == pos)  //没有该节点		{			return;		}		else if(pos->_pNext == NULL)   //该节点为尾结点		{			PushBack(data);		}		else                          //其他节点		{			Node* pNewNode = new Node(data);			pNewNode->_pNext = pos->_pNext ;			pos->_pNext->_pPre = pNewNode;			pos->_pNext = pNewNode;			pNewNode->_pPre = pos;			_size++;		}	}	void Erase(Node* pos)	{		if(NULL == pos)   //没有该节点		{			return;		}		else if(pos->_pNext == NULL)    //该节点为尾结点		{			PopBack();		}		else                            //其他节点		{			Node* pTemp = pos;			pos->_pPre->_pNext = pos->_pNext;			pos->_pNext->_pPre = pos->_pPre;			delete pTemp;			_size = _size-1;		}	}	~List()	{		if(_pHead != NULL)		{			Node* pTemp = _pHead;				while(pTemp->_pNext)			{				pTemp = pTemp->_pNext;			}			_pTail = pTemp;			while((_pTail != _pHead)&&(_pTail!=NULL))			{				Node *pTemp = _pTail;				_pTail = _pTail->_pPre;				delete pTemp;			}			delete _pHead;			_pHead =_pTail = NULL;			_size = 0;		}	}private:	Node* _pHead;	Node* _pTail;	size_t _size;};void funtest(){	 List l1(5,10);	 List l2(l1);	 List l3;	 l3 = l1;	 l1.PushBack(5);	 l1.PopBack();	 l1.PushFront(1);	 l1.PopFront();	 l1.PushBack(3);	 Node *temp = l1.Find(3);	 l1.Insert(temp,1);	 l1.Erase(temp);	 l1.~List();}int main(){	funtest();	return 0;}