本节主要介绍双向链表及双向链表的插入及删除算法。
本文部分ppt、视频截图来自：[青岛大学-王卓老师的个人空间-王卓老师个人主页-哔哩哔哩视频]
1. 双向链表
（1）为什么讨论双向链表
单链表的结点 → 有指示后继的指针域 → 找后继结点方便，即查找某结点的后继结点的执行时间为O(1)。
单链表 → 无指示前驱的指针域 → 找前驱结点难 ：从表头出发查找，即：查找某结点的前驱结点的执行时间为O(n)。因此，可以采用双向链表，能够克服单链表不便找前驱结点的缺点。
（2）双向链表定义
- 双向链表是什么？
双向链表：在单链表的每个结点里再增加一个指向其直接前驱的指针域 prior ，这样链表中就形成了有两个方向不同的链，故称为双向链表。
- 双向链表的结构和结构定义
双向链表结构可定义如下：
typedef struct DuLNode{Elemtype data;struct DuLNode *prior,*next;
}DuLNode, *DuLinkList;
（3）双向循环链表
和单链的循环表类似，双向链表也可以有循环表
- 让头结点的前驱指针指向链表的最后一个结点；
- 让最后一个结点的后继指针指向头结点。
（4）双向链表结构的对称性
双向链表结构的对称性（设指针 p 指向某一结点）：
//要找某个结点，可以通过它前驱的后继，也可以通过它后继的前驱找到
p -> prior -> next = p = p -> next -> prior
在双向链表中有些操作(如:ListLength、GetElem等)，因仅涉及一个方向的指针，故它们的算法与线性链表的相同。但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为 O(n)。
2. 双向链表的插入、删除算法
（1）双向链表的插入
在 a 结点和 b 结点中间插入新结点 x ：此时只知道b的地址p和x的地址s
【分析】
① 新结点 x 的前驱指针指向结点 a。
s -> prior = p -> prior;
② 结点 a 的后继指针指向新结点 x
p -> prior -> next = s;
③ 新结点 x 的后继指针指向结点 b
s -> next = p;
④ 结点 b 的前驱指针指向新结点 x
p -> prior = s;
【双向链表的插入算法描述】
void ListInsert_DuL(DuLinkList &L, int i, ElemType e){ //在带头结点的双向循环链表 L 中第 i 个位置之前插入元素 eif(!(p = GetElemP_DuL(L,i))) return ERROR;s = new DuLNode; s -> data = e;s -> prior = p -> prior; p -> prior -> next = s;s -> next = p; p -> prior = s;return OK;
} //ListInsert_DuL
（1）双向链表的删除
删掉 p 指针指向的结点 b
【分析】
① a 结点的 next指针指向c。
p -> prior -> next = p -> next;
② c 结点的前驱指针指向结点 a 的 next 域
p -> next -> prior = p -> prior;
③ 释放 b 结点
free(p);
【双向链表的删除算法描述】
void ListDelete_DuL(DuLink &L,int i,ElemType &e){//删除带头结点的双向循环链表L的第i个元素，并用e返回if(!(p = GetElemP_DuL(L.i))) return ERROR;e = p -> data;p -> prior -> next = p -> next;p -> next -> prior = p-> prior;free(p);return OK;
} //ListDelete_DuL
