双向链表的结构

typedef struct DualNode {
    ElemType data;
    struct DualNode *prior; //前驱节点
    struct DualNode *next;  //后继节点
}DualNode, *DuLinkList;

图片.png

• 既然单链表有循环链表，双向链表当然也有双向循环链表，如下图：

图片.png

问： 双向链表中某个节点p的后继节点的前驱节点是什么？ 它自己p

双向链表的插入操作

双向链表的插入操作，顺序很重要，不能写反，如下图：

图片.png

• 代码实现

s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s; 

关键在于交换的过程中不要出现矛盾，例如第4步先被执行了，那么p->prior就会提前变为s，使得插入工作出错。

双向链表的删除操作

图片.png

• 代码实现

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);

总结

双链表比单链表复杂一些， 双链表提高了算法的时间效率，说白了就是用空间换取时间效率。

双向链表的应用

要求实现用户输入一个数使得26个字母的排列发生变化，例如用户输入3，就输出结果：DEFGHIJKLMNOPQRSTUVWXYZABC
同时需要支持负数，例如用户输入-3,输出结果：
XYZABCDEFGHIJKLMNOPQRSTUVW

• 代码实现（C语言）

#include<stdafx.h>
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
typedef struct DualNode {
    ElemType data;
    struct DualNode *prior; //前驱节点
    struct DualNode *next;  //后继节点
}DualNode, *DuLinkList;
Status InitList(DuLinkList *L) {
    DualNode *p, *q;
    int i;
    *L = (DuLinkList)malloc(sizeof(DualNode));
    if(!(*L)) {
        return ERROR;
    }
    (*L)->next = (*L)->prior = NULL;
    p = (*L);
    for (i = 0; i < 26; i++)
    {
        q = (DualNode *)malloc(sizeof(DualNode));
        if (!q)
        {
            return ERROR;
        }
        q->data = 'A' + i;
        q->prior = p;
        q->next = p->next;
        p->next = q;
        p = q;
    }
    p->next = (*L)->next;
    (*L)->next->prior = p;
    return OK;
}
void Caesar(DuLinkList *L, int i) {
    if (i > 0)
    {
        do {
            (*L) = (*L)->next;
        } while (--i);
    }
    if (i < 0)
    {
        do {
            (*L) = (*L)->next;
        } while (++i);
    }
}
int main() {
    DuLinkList L;
    int i, n;
    InitList(&L);
    printf("请输入一个整数：");
    scanf_s("%d", &n);
    Caesar(&L, n);
    for (i = 0; i < 26; i++)
    {
        L = L->next;
        printf("%c", L->data);
    }
    getchar();
    getchar();
    return 0;
}