双向链表

双向链表是在单链表的每个结点中，在设置一个指向其前驱结点的指针域。如下图所示

双向链表
双向链表也可以是循环表，成为双向循环链表，如下图所示
image.png
可以看出其具有对称性，即p->next->prior=p=p->prior->next
1.双向链表是单链表扩展出来的结构，所以它的很多操作与单链表相同的（用其中一个指针域next或prior即可），如求长度的ListLength,查找元素的GetElem，获得元素位置的LocateELem等。
2.同理，双向循环链表也与单循环链表有很多操作相同。
重点看一下双向循环链表的插入和删除：

DuLinkList.h

#pragma once

#pragma once

// 函数结果状态代码
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2

//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;

//数据类型
typedef int ElemType;

typedef struct DuLNode
{
    ElemType data;
    DuLNode* next, * prior;

}DuLNode, * DuLinkList;

//双向循环链表初始化
Status InitList_DuL(DuLinkList& L);

//返回双向循环链表中第i个结点
DuLNode* LocateElemP_DuL(DuLinkList L, int i);

//在带头结点的双向循环链表L中第i个位置之前插入元素e
Status ListInsert_DuL(DuLinkList& L, int i, ElemType e);

//删除带头结点的双向循环链表L的第i个元素，并用e返回
Status ListDelete_DuL(DuLinkList& L, int i, ElemType& e);

//遍历双向循环链表
void ListTraverse_DuL(DuLinkList L);

DuLinkList.cpp

#include "DuLinkList.h"
#include <iostream>
using namespace std;

//双向循环链表初始化
Status InitList_DuL(DuLinkList& L)
{
    L = new DuLNode;

    L->next = L;                    //头结点的后继为头结点
    L->prior = L;                   //头结点的前驱为头结点
    cout << "初始化成功" << endl;

    return OK;
}

//返回链表中第i个结点
DuLNode* LocateElemP_DuL(DuLinkList L, int i)
{
    DuLNode* p = L->next;           //第一个结点
    int j = 1;
    while (p != L && j < i)         //到最后一个节点或这到第i个结点
    {
        p = p->next;
        j++;
    }
    if (j != i)                     //不相等表示插入位置不合理
    {
        return NULL;
    }
    return p;
}

插入（在第i个结点之前插入新结点）：

插入
步骤：
1.先找到第i个结点p
2.新结点s的前驱为结点p的前驱
3.结点p的前驱的后继为新结点s
4.新结点s的后继为结点p
5.结点p的前驱为新结点s
当然，也可找到第i-1个结点q，利用此结点进行插入

//在带头结点的双向循环链表L中第i个位置之前插入元素e
Status ListInsert_DuL(DuLinkList& L, int i, ElemType e)
{
    DuLNode* p = LocateElemP_DuL(L, i);     //返回链表中第i个元素结点，即为要插入结点的后继结点
    if (!p)
    {
        cout << "位置不合理" << endl;
        return ERROR;
    }
    DuLNode* s = new DuLNode;               //建立新结点
    s->data = e;
    s->prior = p->prior;                    //新结点前驱为原来p结点的前驱
    p->prior->next = s;                     //原来p结点前驱的后继本来还是p结点，现在改为新结点
    s->next = p;                            //新结点的后继为p结点
    p->prior = s;                           //p结点的前驱为新结点

    cout << "插入成功" << endl;
    return OK;
}

删除（删除第i个结点p）：

删除
步骤：
1.先找到第i个结点p
2.结点p的前驱的后继为p的后继
3.结点p的后继的前驱为p的前驱

//删除带头结点的双向循环链表L的第i个元素，并用e返回
Status ListDelete_DuL(DuLinkList& L, int i, ElemType& e)
{
    DuLNode* p = LocateElemP_DuL(L, i);

    if (!p || p == L)
    {
        cout << "位置不合理" << endl;
        return ERROR;
    }
    p->prior->next = p->next;
    p->next->prior = p->prior;

    e = p->data;
    cout << "删除" << e << "成功" << endl;
    delete p;

    return OK;
}

//遍历双向循环链表
void ListTraverse_DuL(DuLinkList L)
{
    DuLNode* p = L->next;
    while (p != L)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

main.cpp

测试：

#include <iostream>
#include "DuLinkList.h"
using namespace std;

int main(int argc, char** argv)
{
    DuLinkList L;
    InitList_DuL(L);            //初始化双向循环链表

    ListInsert_DuL(L, 1, 1);    //双向循环链表第一个位置插入1
    ListInsert_DuL(L, 2, 2);
    ListInsert_DuL(L, 3, 3);

    ListInsert_DuL(L, 5, 5);    //测试插入是否成功

    ListTraverse_DuL(L);        //遍历

    ElemType e;
    ListDelete_DuL(L, 1, e);    //删除第一个元素所在节点
    ListDelete_DuL(L, 2, e);

    ListDelete_DuL(L, 2, e);    //测试删除是否成功

    ListTraverse_DuL(L);

    return 0;
}