//【数据结构】用C++实现双链表的各种操作（包括头删，尾删，插入，逆序，摧毁，清空等等）

//头文件

#ifndef _LIST_H
#define _LIST_H


#include<iostream>
using namespace std;


template<class Type>
class DList;


template<class Type>
class ListNode
{
	friend class DList<Type>;
public:
	ListNode() :data(Type()),next(NULL),prio(NULL)
	{}
	ListNode(Type d,ListNode<Type> *n = NULL,ListNode<Type> *m=NULL)
		:data(d),next(n),prio(m)
	{}
	~ListNode()
	{}


private:
	Type data;
	ListNode<Type> *next;
	ListNode<Type> *prio;
};


template<class Type>
class DList
{
public:
	DList()
	{
		first = last = Buynode();
	}
	~DList()
	{
		destroy();
	}
public:




	void push_back(const Type &x)            //尾插``
	{
		ListNode<Type> *s = Buynode(x);
		last->next = s;
		s->prio = last;
		last = s;
		first->data++;
	}




	void push_front(const Type &x)          //头插``
	{
		if (first->data == 0)
		{
			push_back(x);
			return;
		}
		ListNode<Type> *s = Buynode(x);
		s->next = first->next;
		first->next->prio = s;
		first->next = s;
		s->prio = first;
		last = s;
		for (int i = 0; i < first->data; i++)
		{
			last = last->next;
		}
		first->data++;
	}


	void pop_back()                 //尾删``
	{
		if (first->data == 0)
			return;
		ListNode<Type> *p = last;
		last = last->prio;
		last->next = NULL;
		delete p;
		first->data--;


	}


	void pop_front()                //头删``
	{
		if (first->data == 0)
		{
			return;
		}
		else
		{
			ListNode<Type> *s = first->next;
			if (first->data == 1)
			{
				delete s;
				last = first;
				last->next = NULL;
			}
			else
			{
				first->next = s->next;
				s->next->prio = first;
				delete s;
			}
			first->data--;
		}
	}




	void insert_val(const Type &x)          //按值插入``
	{
		ListNode <Type> *p = Buynode(x);
		ListNode <Type> *s = first;
		if (first->data == 0)
		{
			push_back(x);
			return;
		}
		while (s->next->data<x&&s->next->next != NULL)
		{
			s = s->next;
		}
		if (s->next->next == NULL)
		{
			if (s->next->data>x)
			{
				p->next = s->next;
				s->next->prio = p;
				s->next = p;
				p->prio = s;
				first->data++;
			}
			else
				push_back(x);
		}
		else
		{
			p->next = s->next;
			s->next->prio = p;
			s->next = p;
			p->prio = s;
			first->data++;
		}


	}




	void show_list()                //显示``
	{
		if (first->data == 0)
		{
			cout << "NULL" << endl;
			return;
		}
		ListNode<Type> *q = first->next;
		while (q != NULL)
		{
			cout << q->data << "->";
			q = q->next;
		}
		cout << "NULL  first->data=" << first->data <<" last->data="<<last->data<< " last->next=" << last->next <<" "<< endl;
	}


	void sort()                     //排序``
	{
		if (first->data == 0)
		{
			return;
		}
		ListNode<Type> *p = first->next;
		ListNode<Type> *q = p->next;
		p->next = NULL;
		last = p;
		first->data = 1;
		ListNode<Type> *r;
		while (q != NULL)
		{
			insert_val(q->data);
			r = q;
			q = q->next;
			delete r;
		}
	}




	ListNode<Type>* find(const Type &x)              //查找``
	{
		ListNode<Type> *s;
		for (s = first->next; s != NULL; s = s->next)
		{
			if (s->data == x)
			{
				return s;
			}
		}
		return NULL;
	}


	int length()                          //求长度``
	{
		return(first->data);
	}


	void delete_val(const Type &x)       //按值删除``
	{
		if (first->data == 0)
		{
			cout << "未找到该数：" << endl;
			return;
		}
		else
		{


			ListNode<Type> *p = find(x);
			if (p == NULL)
			{
				cout << "未找到该数：" << endl;
				return;
			}
			ListNode<Type> *q = first;
			while (q->next != p)
			{
				q = q->next;
			}
			if (q->next->next == NULL)
			{
				pop_back();
			}
			else
			{
				q->next = p->next;
				p->next->prio = q;
				delete p;
				first->data--;
			}
		}
	}


	void clear()                       //清除``
	{
		if (first->data == 0)
			return;
		while (first->next != NULL)
		{
			pop_back();
		}
	}


	void resver()                       //逆序``
	{
		if (first->data == 0)
		{
			return;
		}
		ListNode<Type> *p = first->next;
		ListNode<Type> *q = p->next;
		p->next = NULL;
		last = p;
		first->data = 1;
		ListNode<Type> *r;
		while (q != NULL)
		{
			push_front(q->data);
			r = q;
			q = q->next;
			delete r;
		}
	}


	void quit_system(int &a)               //退出``
	{
		clear();
		a = 0;
	}


	void destroy()              //摧毁``
	{
		clear();
		delete first;
	}
protected:
	ListNode<Type>* Buynode(Type x = Type())
	{
		ListNode<Type> *p = new ListNode<Type>(x);
		return p;
	}
private:
	ListNode<Type> *first;
	ListNode<Type> *last;
};




//主函数

#endif


#include"DList.h"


void main()
{
	DList<int> mylist;
	int select = 1;
	int Item;
	//int pos;
	while (select)
	{
		cout << "**************************************" << endl;
		cout << "* [1] show_list       [2] push_front *" << endl;
		cout << "* [3] push_back       [4] pop_front  *" << endl;
		cout << "* [5] pop_back        [6] insert_val *" << endl;
		cout << "* [7] find            [8] delete_val *" << endl;
		cout << "* [9]length           [10] clear     *" << endl;
		cout << "* [11] quit_system    [12] destroy   *" << endl;
		cout << "* [13] resver         [14] sort      *" << endl;
		cout << "**************************************" << endl;
		cout << "请选择:>";
		cin >> select;
		switch (select)
		{
		case 1:
			mylist.show_list();
			break;
		case 2:
			cout << "请输入要插入的值(-1结束):>";
			while (cin >> Item,Item != -1)
			{
				mylist.push_front(Item);
			}
			break;
		case 3:
			cout << "请输入要插入的值(-1结束):>";
			while (cin >> Item,Item != -1)
			{
				mylist.push_back(Item);
			}
			break;
		case 4:
			mylist.pop_front();
			;
			break;
		case 5:
			mylist.pop_back();
			break;
		case 6:
			cout << "请输入要插入的值:>";
			cin >> Item;
			mylist.insert_val(Item);
			break;
		case 7:
			cout << "请输入要查找的数：";
			cin >> Item;
			cout << "该数的地址为：";
			cout << mylist.find(Item) << endl;
			break;
		case 8:
			cout << "请输入要删除的值:>";
			cin >> Item;
			mylist.delete_val(Item);
			break;


		case 9:
			cout << "该顺序表长度为：" << mylist.length() << endl;
			break;
		case 10:
			mylist.clear();
			break;
		case 11:
			mylist.quit_system(select);
			break;
		case 12:
			mylist.destroy();
		case 13:
			mylist.resver();
			break;
		case 14:
			mylist.sort();
			break;
		default:
			break;
		}
	}
	return;
}
<img src="http://img.blog.csdn.net/20150531224355335?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZG91ZG91d2ExMjM0/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />