基于双向链表的增删改查和排序（C++实现）

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

由于双向链表可以方便地实现正序和逆序两个方向的插入、查找等功能，在很多算法中经常被使用，

这里用C＋＋构造了一个双向链表，提供了对双向链表的插入、查找、删除节点、排序等功能，其中排序提供了插入排序和冒泡排序两种方式

#include
using namespace std;

class Node          //组成双向链表的节点
{
public:
    int data;
    Node * pNext;
    Node * pLast;
};

class List      //构造一个双向链表
{
private:
    Node * pHead;
    Node * pTail;
    int length;
public:
    List(int length)　　　　//创建双向链表
    {
        this->length=length;
        pHead=new Node();
        pHead->pLast=NULL;
        pTail=pHead;
        for(int i=0;ipNext;
        while(p!=NULL)
        {
            coutpNext)
        {
            for(q=p->pNext;q!=NULL;q=q->pNext)
            {
                if(q->datadata)
                {
                    temp=q->data;
                    q->data=p->data;
                    p->data=temp;
                }
            }
        }
    }
    
    void sortListByInsertWay()        //插入排序
    {
        if(pHead->pNext==NULL||pHead->pNext->pNext==NULL)
        {
            return;
        }
        Node * p2=pHead->pNext->pNext;
        Node * p1=pHead;
        pHead->pNext->pNext=NULL;
        while(p2)
        {
            Node * pN=p2->pNext;
            while(p1->pNext)
            {
                if(p2->datapNext->data)
                {
                    p2->pNext=p1->pNext;
                    p2->pLast=p1;
                    p1->pNext->pLast=p2;
                    p1->pNext=p2;
                    break;
                }
                p1=p1->pNext;
            }
            if(p1->pNext==NULL)
            {
                p2->pNext=NULL;
                p2->pLast=p1;
                p1->pNext=p2;
            }
            p2=pN;
        }
        
        //重新查找pTail的位置
        Node * pt=pHead;
        while(pt->pNext)
        {
            pt=pt->pNext;
        }
        pTail=pt;
    }
    
    void changeList(int num,int position)　　　　//修改链表中指定位置的节点
    {
        Node * p=pHead->pNext;
        if(position>length||positionpLast=temp;
        length++;
    }
    
    void clearList()　　　　　　//清空
    {
        Node * q;
        Node * p=pHead->pNext;
        while(p!=NULL)
        {
            q=p;
            p=p->pNext;
            delete q;
        }
        p=NULL;
        q=NULL;
    }
    
    void deleteList(int position)　　　//删除指定位置的节点
    {
        Node * p=pHead->pNext;
        if(position>length||positionpLast=p->pLast;
        delete p;
        length--;
    }
    
    int getItemInList(int position)　　　　　　//查找指定位置的节点
    {
        Node * p=pHead->pNext;
        if(position>length||position