双向循环链表的存储结构

在单向链表中，从某一个结点出发可以访问到它的后继结点，但是不能访问到它的前驱结点，而在单向循环链表中，可从某一个结点出发访问到表中任意一个结点，但在访问它的前驱结点时必须通过头结点。为了克服上述两种链表的缺点，以下引入双向循环链表(Double Linked List)的概念。双向循环链表结点的数据类型为：

	struct node	{	int data;	struct node *next;	struct node *prior;	}

在双向循环链表的每个结点中包含两个指针域（上述结构体类型中的next和prior），其中next指向它的直接后继，prior指向它的直接前驱，而头结点的prior指向尾结点，尾结点的next指向头结点。为叙述方便分别称prior和next为结点的左、右指针，图2-15是双向循环链表的示意图。在双向循环链表的操作中，可以方便地从任何一个结点出发访问到它的前驱和后继结点，而在进行删除和插入操作时则需修改两个方向的指针。

双向循环链表的示意图

双向循环链表的插入操作

在p所指结点之后插入q所指的数据元素为x的新结点的算法可描述如下，

双向循环链表的插入

q=(NODE *)malloc(sizeof(NODE)); /*产生新结点，q指向新结点*/q->data=x;　 /*为新结点赋值*/q->next=p->next;　 /*新结点的右指针指向p的右结点（直接后继）*/(p->next)->prior=q;　 /*p结点的右结点的左指针指向新结点*/q->prior=p; /*新结点的左指针指向p*/p->next=q;　 /*p的右指针指向新结点*/

删除p所指的结点的过程如下：

	(p->prior)->next=p->next;/*p所指结点的直接前驱的右指针指向p所指结点的直接后继*/	(p->next)->prior=p->prior;/*p所指结点的直接后继的左指针指向p所指结点的直接前驱*/