数据结构-双向链表

#include
using namespace std;

//双向链表

//双向链表在 *** 作时要注意首尾指针的改变


template
class node
{
public:
	node() { data = NULL; ago = nullptr; next = nullptr; }
	node(T _data) { data = _data; ago = nullptr; next = nullptr; }
	~node() { ago = nullptr; next = nullptr; }

	T data;

	node* ago;

	node* next;
};


template
class pairList
{
public:
	pairList() { length = 0; L = new node; L->next = nullptr; L->ago = nullptr; N = L; }
	~pairList() { if (L != nullptr) { removeList(); delete L; }N = nullptr; }

	//插入
	void insertList(int loc,T data) 
	{
		node* p = new node(data);
		
		if (loc <= 1 || length < 1) //头插
		{
			node* temp = L;
			p->ago = temp;
			p->next = temp->next;
			if (temp->next != nullptr) { temp->next->ago = p; }
			else { N = p; }
			temp->next = p;
			length++;
		}
		else if (loc > 1 && loc < length && length != 0) //中间插
		{
			if (loc < length - loc)
			{
				node* temp = L;
				for (int i = 0; i < loc; i++) { temp = temp->next; }
				p->next = temp;
				p->ago = temp->ago;
				node* _temp = temp->ago;
				temp->ago = p;
				_temp->next = p;
				length++;
			}
			else
			{
				node* temp = N;
				for (int i = 0; i < length - loc; i++) { temp = temp->ago; }
				p->next = temp;
				p->ago = temp->ago;
				node* _temp = temp->ago;
				temp->ago = p;
				_temp->next = p;
				length++;
			}
		}
		else if (loc >= length) //尾插
		{
			node* temp = N;
			p->next = temp->next;
			p->ago = temp;
			temp->next = p;
			N = p;
			length++;
		}
	}

	//删除
	void deleteList(int loc) 
	{
		if (loc <= 1)
		{
			node* temp = L;
			temp = temp->next;
			node* _temp = temp->next;
			_temp->ago = L;
			L->next = _temp;
			delete temp;
			length--;
		}
		else if (loc > 1 && loc < length)
		{
			if (loc > length - loc)
			{ 
				node* temp = N; 
				for (int i = 0; i < length - loc; i++) { temp = temp->ago; }
				node* _temp = temp->next;
				_temp->ago = temp->ago;
				_temp = temp->ago;
				_temp->next = temp;
				delete temp;
				length--;
			}
			else 
			{ 
				node* temp = L; 
				for (int i = 0; i < loc; i++) { temp = temp->next; }
				node* _temp = temp->ago;
				_temp->next = temp->next;
				_temp = temp->next;
				_temp->ago = temp->ago;
				delete temp;
				length--;
			}
		}
		else if (loc >= length)
		{
			node* temp = N;
			node* _temp = temp->ago;
			_temp->next = temp->next;
			N = _temp;
			delete temp;
			length--;
		}
	}

	//遍历
	void printList(bool ret) 
	{
		if (ret)//正序
		{
			node* temp = L;
			for (int i = 0; i < length; i++) {temp = temp->next; cout << temp->data << " ";}
			cout << endl;
		}
		else//倒序
		{
			node* temp = N;
			for (int i = 0; i < length; i++) 
			{ 
				cout << temp->data << " ";
				if (temp->ago != nullptr) { temp = temp->ago; }
			}
			cout << endl;
		}
	}

	//查找
	void findList(T _data) 
	{
		node* temp = L;
		for (int i = 0; i < length; i++)
		{
			temp = temp->next;
			if (temp->data == _data) { cout << "位置：" << i + 1 << "值：" << temp->data << endl; }
		}
		cout << "查找完毕！" << endl;
	}

	//清空
	void removeList() 
	{
		node* temp = N;
		node* _temp = N;
		for (int i = 0; i < length; i++)
		{
			_temp = _temp->ago;
			delete temp;
			temp = _temp;
		}
		L->next = nullptr;
		L->ago = nullptr;
		length = 0;
	}

	//获取表长
	int getList() { return length; }
private:

	int length;

	node* L;		//头节点

	node* N;		//尾节点

};