2.7双向链表

循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前趋结点，但时间耗费是 O (n) 。

如果希望从表中快速确定某一个结点的前趋，另一个解决方法就是在单链表 的每个结点里再增加一个指向其前趋的指针域 prior。

这样形成的链表中就有 两条方向不同的链，我们称之为双向链表。

双向链表的结构定义如下：

typedef struct DNode 
{ ElemType data; struct DNode *prior，*next; 
}DNode, * DoubleList；

双向链表的结点结构如图所示:

• 双向链表也是由头指针唯一确定的，
• 增加头结点能使双链表的某些运算变得方便
• 由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。
• 设指针 p指向双链表中某一结点，则有下式成立： p->prior->next = p = p->next->prior
• 在双向链表中，那些只涉及后继指针的算法，如求表长度、取元素、元素定位等，与单链表中相应的算法相同，
• 但对于前插和删除操作则涉及到前驱和后继两个方向的指针变化，因此与单链表中的算法不同。

双向链表的前插操作

【算法思想】
欲在双向链表第 i 个结点之前插入一个的新的结点，则指针的变化情况如图所示：

s->prior=p->prior;         ① 
p->prior->next=s;          ② 
s->next=p;                 ③ 
p->prior=s;                ④ 

【算法描述】

int DlinkIns(DoubleList L,int i,ElemType e) 
{ DNode  *s,*p; /*先检查待插入的位置 i 是否合法（实现方法同单链表的前插操作）*/ /*若位置 i 合法，则找到第 i 个结点并让指针 p 指向它*/ s=(DNode*)malloc(sizeof(DNode)); if (s) 
{ s->data=e;   s->prior=p->prior;  ① p->prior->next=s;  ② s->next=p;   ③ p->prior=s;   ④ return TRUE; 
} else return FALSE; 
} 

双向链表的删除操作

【算法思想】
欲删除双向链表中的第 i 个结点，则指针的变化情况如图所示：

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

【算法描述】

int DlinkDel(DoubleList L,int i,ElemType *e) 
{   DNode  *p;  /*先检查待插入的位置 i 是否合法（实现方法同单链表的删除操作）*/ /*若位置 i 合法，则找到第 i 个结点并让指针 p 指向它*/    *e=p->data;    			p->prior->next=p->next;   ①    p->next->prior=p->prior;  ②    free(p);     return TRUE; 
} 

双向循环链表

双向链表可以有循环表,称为双向循环链表。

应用举例

编写算法：将一个循环双链表 L=（a,b,c,d）转换为 L=（b,a,c,d）。
算法思想：实际上是改变表中两个元素的链接。在修改有关链域之前，注意做必 要的备份。