双向链表和双向循环链表初探

双向循环链表和双向循环链表是十分重要的基础数据结构。在前面探索的单向链表和单向循环链表的基础上，双向链表和双向循环链表理解起来就会简单一些。
我们先看一下双向链表的定义：每个节点都有两个指针域，一个数据域，两个指针域分别是前驱指针 prior 和后继指针 next，而头节点的前驱指针指向 NULL，尾节点的后继指针指向 NULL，其余节点的前驱指针指向前一个节点，后继指针指向后一个节点。
双向循环链表的定义比较类似：每个节点都有两个指针域，一个数据域，两个指针域分别是前驱指针 prior 和后继指针 next，而头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点，其余节点的前驱指针指向前一个节点，后继指针指向后一个节点。
我们通过下面的两张图片就能更加直观的理解双向链表和双向循环链表。

双向链表

双向循环链表

双向链表

双向链表的数据结构定义

由前面的定义以及示意图，用代码来实现双向链表的结构并不复杂，代码如下:

// 双向链表节点
typedef struct Node
{
    // 数据域
    ElemType data;
    // 前驱指针
    struct Node *prior;
    // 后继指针
    struct Node *next;
}Node;
// 双向链表结构体指针
typedef struct Node *LinkList;

双向链表的创建

这里我们还是按照国际惯例给双向链表设计一个空的头节点，所以在创建的时候需要先创建一个头节点，然后让头节点的前驱指针 prior 指向 NULL，让头节点的后继指针 next 也指向 NULL。这里为了方便，我们直接给一些初始化数据来进行剩下节点的创建。这里其他节点相当于是在头节点之后进行插入，那么是否需要额外判断呢？我们分析一下：

当插入首元节点的时候，我们需要先初始化一个空的节点 temp，同时将其前驱和后继都指向 NULL，接着将数据赋值到 temp 的数据域上，然后让 temp 的前驱指向头节点，让头节点的后驱指向 temp，而 temp 的后驱已经在初始化的时候被指向 NULL 了，所以不用再额外处理。
当在首元节点后插入新节点时，还是需要先初始化一个空的节点 temp，同时将其前驱和后继都指向 NULL，接着将数据赋值到 temp 的数据域上，然后让 temp 的前驱指向首元节点，让首元节点的后驱指向 temp，而 temp 的后驱已经在初始化的时候被指向 NULL 了，所以不用再额外处理。

通过分析前两个节点的插入情况，我们可以知道这里并不需要做多余的判断操作，所以我们直接上代码吧。

Status LinkListCreate(LinkList *L)
{
    // 1.创建空的头节点
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    (*L)->prior = NULL;
    (*L)->next = NULL;
    (*L)->data = -1;
    // 声明一个尾节点指向头节点
    LinkList tail = *L;
    for(int i = 1;i <= 10;i++)
    {
        LinkList temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) return ERROR;
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = i;
        // 尾节点
        tail->next = temp;
        temp->prior = tail;
        tail = temp;
    }
    return OK;
}

双向链表的插入

双向链表的插入操作，我们可以简单分析一下几种情况:

在首元节点之前插入
在尾节点之后插入
在中间位置插入

显然第一种和第三种情况由于有空的头节点存在，流程是一模模一样样的，分别是
0.找到待插入位置的前一个节点
1.让原来待插入位置的后一个节点的前驱指针指向新节点
2.让新节点的后继指针指向待插入位置的后一个节点
3.让待插入位置的前一个节点的后继指针指向新节点
4.让新节点的前驱指针指向待插入位置的前一个节点

其中，1和2步骤可以对调，3和4步骤可以对调。但是前两步和后两步之间不能交换，否则首元节点就找不到了。

通过这幅图可以清楚的看到整个插入的过程。

而对于在尾节点之后插入新节点的情况，步骤1显然就没有意义了，因为新节点的后继已经是 NULL，就没有将 NULL 的前驱指向新节点的意义了。

具体实现代码如下:

Status ListInsert(LinkList *L, int place, ElemType e)
{
    //1.判断头节点是否为空
    if ((*L) == NULL) return ERROR;
    //2.遍历双向链表找到待插入位置的前一个节点
    int i = 1;
    LinkList p = *L;
    while (i < place && p)
    {
        p = p->next;
        i++;
    }
    // 插入位置大于链表长度或插入位置为负
    if (p == NULL || i > place) return ERROR;
    //3.创建一个新节点
    LinkList temp = (LinkList)malloc(sizeof(Node));
    if (temp == NULL) return ERROR;
    temp->next = NULL;
    temp->prior = NULL;
    temp->data = e;
    //4.执行具体的插入操作
    // 先判断 p->next 是否为 NULL
    if (p->next != NULL)
    {
        // 4.1 待插入位置的后一个节点的前驱指向新节点
        p->next->prior = temp;
    }
    // 4.2 新节点指向待插入位置的后一个节点
    temp->next = p->next;
    // 4.3 待插入位置的前一个节点的后继指向新节点
    p->next = temp;
    // 4.4 新节点的前驱指向待插入位置的前一个节点
    temp->prior = p;
    return OK;
}

双向链表的删除

对于双向链表的删除操作，我们还是可以分析下面几种不同的场景:

1.删除中间位置的节点
2.删除尾节点
3.删除首元节点

删除中间位置的节点

这种场景的话需要我们找到待删除位置的前一个节点 p，然后依次执行下面的步骤
0.声明一个临时节点 delTemp 指向 p->next
1.让 p 的后继指针指向 delTemp 的后继节点
2.让 delTemp 的后继节点的前驱指向 p
3.释放掉 delTemp

删除尾节点

如果要删除的是尾节点，我们还是需要找到尾节点的前一个节点 p，然后依次执行下面的步骤
0.声明一个临时节点 delTemp 指向 p->next ，也就是尾节点
1.让 p 的后继指针指向 delTemp 的后继节点，也就是让 p 的后继指针指向 NULL
2.释放掉 delTemp

删除首元节点

如果要删除的是首元节点，我们直接声明一个节点 p 指向头节点即可，然后依次执行下面的步骤
0.声明一个临时节点 delTemp 指向 p->next ，也就是首元节点
1.让 p 的后继指针指向 delTemp 的后继节点，也就是首元节点后面的一个节点
2.让 delTemp 的后继节点的前驱指向 p
3.释放掉 delTemp

具体实现

根据上面三种场景的分析，其实带头节点双向链表的删除只需要分两种情况，即删除尾节点和删除非尾节点。话不多说，直接上代码吧:

Status LinkListDelete(LinkList *L, int place, ElemType *e)
{
    // 1.判断头节点是否为空
    if (*L == NULL) return ERROR;
    // 2.遍历找到待删除节点的前一个节点 p
    int i = 1;
    LinkList p = *L;
    while (i < place && p)
    {
        p = p->next;
        i++;
    }
    // 如果要删除的位置的前一个节点为空或删除位置为为负，则返回 ERROR
    if (p == NULL || i > place) return NULL;
    // 3.执行具体的删除操作
    LinkList delTemp = p->next;
    *e = delTemp->data;
    if (delTemp->next == NULL)
    {
        // 3.1 要删除的是尾节点
        p->next = NULL;
    }
    else 
    {
        // 3.2 要删除的不是尾节点
        p->next = delTemp->next;
        delTemp->next->prior = p;
    }
    free(delTemp);
    return OK;
}

双向链表根据给定值删除节点

通过给定值去双向链表中删除节点的逻辑和上一个小节中的删除操作有一些不同，判断逻辑如下
1.从首元节点开始遍历双向链表，如果遍历到的节点的值与给定值相等，则结束遍历，取出待删除的节点
2.判断待删除的节点是否为尾节点
3.如果是尾节点，则声明一个待删除节点指向尾节点，然后让前一个节点指向NULL，并释放掉尾节点
4.如果不是尾节点，则声明一个待删除节点指向节点，然后让前一个节点指向待删除节点的后继，并让待删除节点的后继节点的前驱指向前一个节点

代码实现如下:

Status LinkListDeleteVal(LinkList *L, ElemType e)
{
    // 如果首元节点为空，返回ERROR
    if ((*L)->next == NULL) return ERROR;
    LinkList p = (*L)->next;
    LinkList delTemp;
    while (p)
    {
        if (p->data == e)
        {
            if (p->next != NULL)
            {
                p->next->prior = p->prior;
            }
            p->prior->next = p->next;
            free(delTemp);
            break;
        }
        p = p->next;
    }
    return OK;
}

双向链表的遍历

遍历双向链表的操作很简单，只需要判断是否首元节点是否为空即可，代码如下:

Status LinkListTraverse(LinkList L)
{
    LinkList p = L->next;
    if (p == NULL) printf("打印的双向链表为空\n");
    while (p)
    {
        printf("%d\n", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

双向循环链表

双向循环链表的数据结构定义

双向循环链表的数据结构和双向链表并无区别，代码如下:

// 双向链表节点
typedef struct Node
{
    // 数据域
    ElemType data;
    // 前驱指针
    struct Node *prior;
    // 后继指针
    struct Node *next;
}Node;
// 双向链表结构体指针
typedef struct Node *LinkList;

双向循环链表的创建

这里我们还是按照国际惯例给双向循环链表设计一个空的头节点，所以在创建的时候需要先创建一个头节点，然后让头节点的前驱指针 prior 指向 头节点自己，让头节点的后继指针 next 也指向 头节点自己。这里为了方便，我们直接给一些初始化数据来进行剩下节点的创建。这里其他节点相当于是在头节点之后进行插入，那么是否需要额外判断呢？我们分析一下：

当插入首元节点的时候，我们需要先初始化一个空的节点 temp，同时将其前驱和后继都指向 NULL，接着将数据赋值到 temp 的数据域上，然后让 temp 的前驱指向头节点，让头节点的后驱指向 temp，而 temp 的后驱需要指回头结点。
当在首元节点后插入新节点时，还是需要先初始化一个空的节点 temp，同时将其前驱和后继都指向 NULL，接着将数据赋值到 temp 的数据域上，然后让 temp 的前驱指向首元节点，让首元节点的后驱指向 temp，而 temp 的后驱需要指回头结点。

具体代码如下:

Status InitLinkList(LinkList *L)
{
    // 1.创建空的头节点
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    (*L)->prior = *L;
    (*L)->next = *L;
    (*L)->data = -1;
    // 声明一个节点指向头节点
    LinkList p = *L;
    for(int i = 1;i <= 10;i++)
    {
        LinkList temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) return ERROR;
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = i;
        // temp 是 p 的后继
        p->next = temp;
        // temp 的前驱是 p
        temp->prior = p;
        // temp 的后继是 *L
        temp->next = *L;
        // p 的前驱是新建的temp
        p->prior = temp;
        //⑤ p 要记录最后的结点的位置,方便下一次插入
        p = p->next;
    }
    return OK;
}

双向循环链表的插入

双向循环链表的插入处理起来相较于双向链表，只需要处理头节点的前驱和尾节点的后驱即可。代码如下:

Status LinkListInsert(LinkList *L, int place, ElemType e)
{
    // 如果头节点为空，返回 ERROR
    if ((*L)->next == NULL) return ERROR;

    // 遍历链表找到待插入位置的前一个节点
    int i = 1;
    LinkList p = *L;
    while (i < place && p->next != *L)
    {
        i++;
        p = p->next;
    }

    if (p == NULL || i > place) return ERROR;

    LinkList temp = (LinkList)malloc(sizeof(Node));
    if (temp == NULL) return ERROR;
    temp->data = e;

    temp->prior = p;
    temp->next = p->next;
    p->next = temp;
    temp->next->prior = temp;

    return OK;
}

双向循环链表的删除

删除操作也跟双向链表的大同小异，代码如下:

Status LinkListDelete(LinkList *L, int place, ElemType *e)
{
    // 1.判断头节点是否为空
    if (*L == NULL) return ERROR;

    // 2.遍历找到待删除节点的前一个节点 p
    int i = 1;
    LinkList p = *L;
    while (i < place && p->next != *L)
    {
        p = p->next;
        i++;
    }
    // 如果要删除的位置的前一个节点为空或删除位置为为负，则返回 ERROR
    if (p == NULL || i > place) return ERROR;

    // 3.执行具体的删除操作
    LinkList delTemp = p->next;
    *e = delTemp->data;
    if (delTemp->next == *L)
    {
        // 3.1 要删除的是尾节点
        p->next = *L;
        (*L)->prior = p;
    }
    else 
    {
        // 3.2 要删除的不是尾节点
        p->next = delTemp->next;
        delTemp->next->prior = p;
    }
    free(delTemp);

    return OK;
}

双向循环链表的遍历

遍历双向循环链表的操作相比于双向链表，只是在循环的结束条件判断那里改为不等于头节点即可，代码如下：

Status LinkListTraverse(LinkList L)
{
    LinkList p = L->next;
    if (p == NULL) printf("打印的双向链表为空\n");
    while (p != L) 
    {
        printf("%d\n", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}