双向链表中基本函数的实现

#include<iostream>
using namespace std;
typedef int DateType;

struct ListNode     
{
	DateType _date;      
	ListNode* _next;    //前驱指针
	ListNode* _prev;    //后驱指针
	ListNode(DateType x)  //对节点进行初始化
		:_date(x)
		, _next(NULL)
		, _prev(NULL)
	{}
	
};

class List
{
public:
     List()       //构造函数
		:_head(NULL), _tail(NULL){}
		
		
	~List()   //析构函数
	{
		Clear();
	}
	

	void PushBack(DateType x)   //尾插法
	{
		if (_head == NULL)
		{
			_head = _tail = new ListNode(x);

		}
		else
		{
			ListNode* tmp = new ListNode(x);
			_tail->_next = tmp;
			tmp->_prev = _tail;
			_tail = tmp;
		}
	}
	
	
	void Clear()       //清空链表
	{
		ListNode* cur = _head;
		while (cur)
		{
			ListNode* del = cur;
			cur = cur->_next;
			delete del;
		}
	}
	
	
	void PrintfList()     //打印链表
	{
		ListNode* cur = _head;
		while (cur)
		{
			cout << cur->_date << "->";
			cur = cur->_next;
		}
		cout << "NULL " << endl;
	}
	
	
	void PopBack()     //尾出法
	{
		
		if (_head==NULL)
		{
			return;
		}
		 else if(_head->_next==NULL)
		{
			 delete _head;
			 _head = _tail = NULL;
		}
		 else
		 {
			 ListNode* cur = _tail->_prev;
			 delete _tail;
			 _tail = cur;
			 cur->_next = NULL;

		 }
	}
	
	
	void PushFront(DateType x)    //头插法
	{
		if (_head == NULL)
		{
			_head = _tail = new ListNode(x);

		}
		else
		{
			ListNode* tmp = new ListNode(x);
			tmp->_next = _head;
			_head->_prev = tmp;
			_head = tmp;
		}

	}
	
	
	void PopFront()     //头出发
	{
		if (_head == _tail)
		{
			if (_head)
			{
				delete _head;
				_head = _tail = NULL;
			}
		}

		else
		{
			ListNode* cur = _head->_next;
			delete _head;
			_head = cur;
			cur->_prev = NULL;

		}
	}
	
	
	void Insert(ListNode* pos, DateType x)     //插入某个数字
	{
		if (_head == _tail)
		{
			if (_head)
			{
				ListNode* tmp = new ListNode(x);
				pos->_next = tmp;
				tmp->_prev = pos;

			}
			else
			{
				_head = _tail = new ListNode(x);
			}
		}
		else if (pos->_next == NULL)
		{
			ListNode* tmp = new ListNode(x);
			tmp->_next = NULL;
			tmp->_prev = pos;
			pos->_next = tmp;
		}
		else
		{
			ListNode* tmp = new ListNode(x);
		
		    tmp->_next = pos->_next;
			pos->_next->_prev = tmp;
			tmp->_prev = pos;
			pos->_next = tmp;

		}
	}



	ListNode* Find(DateType x)   //寻找某个数字，并返回该节点地址
	{

		ListNode* cur = _head;
		while ( (cur->_date != x) && (cur != NULL) )
		{
			cur = cur->_next;
		}

		return cur;

	}
	
	
	void Erase(ListNode*  pos )  //删除某个节点
	{
		if (!pos)
		{
			return;
		}
		else if (pos->_prev == NULL)
		{
			if (pos->_next)
			{
				ListNode* next = pos->_next;
			    delete pos;
				next->_prev = NULL;
				_head = next;
			}
			
			else
			{
				pos->_next = NULL;
				pos->_prev = NULL;
				delete pos;

			}
		}
		else if (pos->_next == NULL)
		{
			ListNode* prev = pos->_prev;
			delete pos;
			prev->_next = NULL;
		}
		else
		{
			ListNode* prev = pos->_prev;
			ListNode* next = pos->_next;
			delete pos;
			prev->_next = next;
			next->_prev = prev;
		}
		
         }

private:
	ListNode* _head;
	ListNode* _tail;

};

本文出自 “零点时光” 博客，请务必保留此出处http://10741764.blog.51cto.com/10731764/1747567

双向链表中基本函数的实现

原文：http://10741764.blog.51cto.com/10731764/1747567