由于单链表结构简单，但是操作起来比较复杂，所以就有了双向链表来替代单链表，其结构中比单链表多了一个指向前驱的指针，在逆序遍历上极大的提高了效率，其节点设计如下：

typedef int DataType;class DSNode{public:	friend class DNSList;	DSNode(DataType x=0)		:_data(x),		_next(NULL),		_prev(NULL)	{	}private:	DSNode*_prev;	DSNode*_next;	DataType _data;};

    链表类提供了增删查改等一系列操作，要注意的是，多了一个指向前驱的指针，故操作起来逻辑更加简单，单语言实现还需更加精密，其类定义如下：

class DNSList{public:	DNSList()		:_head(NULL),		_tail(NULL)	{	}	~DNSList()	{		_Clear();	}	DNSList(const DNSList &l)	{		DSNode *cur = l._head;		while (cur)		{			PushBack(cur->_data);		}	}	DNSList operator = (DNSList l)	{		DSNode *cur = l._head;		while (cur)		{			PushBack(cur->_data);		}	}public:	// 头插/头删/尾插/尾删	void PushBack(const DataType& x);	void PopBack();	void PushFront(const DataType& x);	void PopFront();	// 插入/查找/删除	void Insert(DSNode* pos, const DataType& x);	DSNode* Find(const DataType& x);	void Erase(const DataType& x);	void Reverse();	// 打印	void Print();private:	void _Clear()	{		while (_head)		{			DSNode*cur = _head;			_head = _head->_next;			delete cur;		}	}	DSNode *_head;	DSNode *_tail;};

    声明函数具体实现如下：

#include"DSList.h"#include
     
      using namespace std;#include
      
       void DNSList::PushBack(const DataType&x){	if (_head == NULL)	{		_tail = _head = new DSNode(x);		_head->_next = NULL;		_head->_prev = NULL;	}	else	{		_tail->_next = new DSNode(x);		_tail->_next->_prev = _tail;		_tail = _tail->_next;	}}void DNSList::PushFront(const DataType&x){	DSNode*cur = new DSNode(x);	if (_head == NULL)	{		_tail = _head = cur;	}	else	{		cur->_next = _head;		cur->_next->_prev = cur;		_head = cur;	}}void DNSList::PopBack(){	if (_tail)	{		DSNode *cur = _tail;		_tail = _tail->_prev;		_tail->_next = NULL;		delete cur;	}}void DNSList::PopFront(){	if (_head)	{		DSNode *cur = _head;		_head = _head->_next;		_head->_prev = NULL;		delete cur;	}}void DNSList::Insert(DSNode* pos, const DataType& x){	assert(_head);	DSNode *cur = _head;	while (cur)	{		if (cur == pos)		{			if (cur == _tail)			{				PushBack(x);			}			else			{				DSNode *tmp = new DSNode(x);				tmp->_next = cur->_next;				tmp->_prev = cur;				tmp->_next->_prev = tmp;				cur->_next = tmp;			}			return;		}		cur = cur->_next;	}	assert(0);}DSNode* DNSList::Find(const DataType& x){	DSNode*cur = _head;	while (cur)	{		if (cur->_data == x)			return cur;		cur = cur->_next;	}	return NULL;}void DNSList::Erase(const DataType &x){	DSNode *cur = _head;	while (cur)	{		if (cur->_data == x)		{			DSNode*tmp = cur;			cur->_prev->_next = cur->_next;			cur->_next->_prev = cur->_prev;			cur = cur->_next;			delete tmp;		}	}}void DNSList::Reverse(){	std::swap(_head, _tail);	DSNode*cur = _head;	while (cur)	{		std::swap(cur->_next, cur->_prev);		cur = cur->_next;	}}void DNSList::Print(){	DSNode*cur = _head;	while (cur)	{		cout << cur->_data << "->";		cur = cur->_next;	}	cout << "NULL" << endl;}
      
     

    测试用例：

#include 
     
      using namespace std;#include"DSList.h"void Test1(){	DNSList l;	l.PushBack(1);	l.PushBack(2);	l.PushBack(3);	l.PushBack(4);	l.PushBack(5);}void Test2(){	DNSList l;	l.PushFront(5);	l.PushFront(4);	l.PushFront(3);	l.PushFront(2);	l.PushFront(1);	l.Print();	l.PopBack();	l.PopFront();	l.PopBack();	l.PopBack();}void Test3(){	DNSList l;	l.PushBack(1);	l.PushBack(2);	l.PushBack(4);	l.PushBack(5);	DSNode *t = l.Find(2);	DSNode *s = l.Find(5);	l.Insert(t, 3);	l.Insert(s, 6);	l.Print();	l.Reverse();	l.Print();}int main(){	//Test1();	//Test2();	Test3();	return 0;}
     

    如有不足，希望指正。