【数据结构】线性表之双向链表

双向链表(double linked list)定义
双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针。所以在双向链表中的结点都有两个指针域：一个指向直接后继，一个指向直接前驱。

线性表的双向链表存储结构代码实现
typedef struct DulNode{

ElemType data;
struct DulNode *prior;  /* 直接前驱指针 */
struct DulNode *next;   /* 直接后继指针 */

}DulNode, *DuLinkList;
循环双向链表图示
双向链表的循环带头结点的空链表：

双向链表的循环带头结点的空链表
非空的循环的带头结点的双向链表：

非空的循环的带头结点的双向链表
特点
对于链表中的某个结点p，它的后继的前驱是它自己，同样，它的前驱的后继也是它自己
p->next->prior = p; p->prior->next = p;
双向链表的操作
双向链表是单链表扩展出来的结构，所以它的很多操作是和单链表相同的，比如求长度的ListLength,查找元素的GetElem,获得元素位置的LocateElem等，这些操作都只要涉及一个方向的指针即可。

插入操作
插入操作并不复杂，但是顺序很重要，一定不能写反。

假设存储元素e的结点为s，要实现将结点s插入到结点p和p->next之间。
双向链表的插入操作图解

核心代码：
s->prior = p; /* 把 p 赋值给 s 的前驱 /
s->next = p->next; / 把 p->next 赋值给 s 的后继 /
p->next->prior = s; / 把 s 赋值给 p->next 的前驱 /
p->next = s; / 把 s 赋值给 p 的后继 */
注意:关键在于他们的顺序，有第二步和第三部都用到了p->next。如果第四步先执行，则会使得p->next提前变成了s,使得插入的工作完不成。

删除操作
删除操作比插入操作更加简单。如果要删除p，只需要两步。
双向链表的删除操作图解

核心代码
p->prior->next = p->next; /* 把 p->next 赋值给 p->prior 的后继 /
p->next->prior = p->prior; / 把 p->prior 赋值给 p->next 的前驱 */
free§;