【まとめ】逆置き双方向チェーンテーブルの3つの方法

双方向チェーンテーブルの遍歴は一方向チェーンテーブルよりもずっと便利であるため、逆置き方法は単鎖テーブルよりも豊富であり、後から前へ遍歴できるため、逆置き配列のように操作することもできるし、単鎖テーブルの特性に基づいて逆置きすることもできるし、二重チェーンテーブル独自の特性で逆置きすることもできる.具体的な方法は以下の通りです.
チェーンテーブルのクラス定義は次のとおりです.

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)
	{
		_Clear();
		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();// 
	DNSList* Reverse();// 

	//  
	void Print();


private:
	void _Clear()
	{
		while (_head)
		{
			DSNode*cur = _head;
			_head = _head->_next;
			delete cur;
		}
	}
	DSNode *_head;
	DSNode *_tail;
};

単一空間の複雑さ:
    1.格納されたコンテンツは,ヘッダテールポインタによって中間に遍歴され,交換される.

void DNSList::Reverse()
{
	DSNode *begin = _head;
	DSNode *end = _tail;
	while (!(begin==end||begin->_prev==end))
	{
		DataType tmp = begin->_data;
		begin->_data = end->_data;
		end->_data = tmp;
		end = end->_prev;
		begin = begin->_next;
	}
}

    2.単純にヘッドポインタを介して後方に遍歴し,各ノードの前駆と後継を交換する.

void DNSList::Reverse()
{
	std::swap(_head, _tail);
	DSNode*cur = _head;
	while (cur)
	{
		std::swap(cur->_next, cur->_prev);
		cur = cur->_next;
	}
}

複数空間の複雑さ:
新しい双方向チェーンテーブルポインタを作成し、ターゲットチェーンテーブルを前から後ろへ/後ろから前へ、各ノードの要素を頭挿入/尾挿入します.

DNSList* DNSList::Reverse()
{
	DNSList*NewList = new DNSList;
	DSNode *cur = _head;
	while (cur)
	{
		NewList->PushFront(cur->_data);
		cur = cur->_next;
	}
	return NewList;
}

不足や誤りがあれば,批判して指摘してほしい.