1.概述：

C语言中一种更复杂的链表是“双向链表”或“双面链表”。其表中的每个节点有两个连接：一个指向前一个节点，（当这个“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当这个“连接”为最后一个“连接”时，指向空值或者空列表）

一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接

在一些低级语言中, XOR-linking 提供一种在双向链表中通过用一个词来表示两个链接（前后），我们通常不提倡这种做法。

双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。

由于另外储存了指向链表内容的指针，并且可能会修改相邻的节点，有的时候第一个节点可能会被删除或者在之前添加一个新的节点。这时候就要修改指向首个节点的指针。有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会被删除或者移动的虚拟节点，形成一个下面说的循环链表。这个虚拟节点之后的节点就是真正的第一个节点。这种情况通常可以用这个虚拟节点直接表示这个链表，对于把链表单独的存在数组里的情况，也可以直接用这个数组表示链表并用第0个或者第-1个（如果编译器支持）节点固定的表示这个虚拟节点。

2.程序实现：

typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;

Status InitList(DuLinkList *L)
{
*L=(DuLinkList)malloc(sizeof(DuLNode));
if(*L)
{
(*L)->next=(*L)->prior=*L;
return OK;
}
else
return OVERFLOW;
}
Status DestroyList(DuLinkList *L)
{
DuLinkList q,p=(*L)->next;
while(p!=*L)
{
q=p->next;
free(p);
p=q;
}
free(*L);
*L=NULL;
return OK;
}
Status ClearList(DuLinkList L)
{
DuLinkList q,p=L->next;
while(p!=L)
{
q=p->next;
free(p);
p=q;
}
L->next=L->prior=L;
return OK;
}
Status ListEmpty(DuLinkList L)
{
if(L->next==L&&L->prior==L)
return TRUE;
else
return FALSE;
}
int ListLength(DuLinkList L)
{
int i=0;
DuLinkList p=L->next;
while(p!=L)
{
i++;
p=p->next;
}
return i;
}
Status GetElem(DuLinkList L,int i,ElemType *e)
{
int j=1;
DuLinkList p=L->next;
while(p!=L&&j<i)
{
p=p->next;
j++;
}
if(p==L||j>i)
return ERROR;
*e=p->data;
return OK;
}
int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{


int i=0;
DuLinkList p=L->next;
while(p!=L)
{
i++;
if(compare(p->data,e))
return i;
p=p->next;
}
return 0;
}
Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)
{

DuLinkList p=L->next->next;
while(p!=L)
{
if(p->data==cur_e)
{
*pre_e=p->prior->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)
{

DuLinkList p=L->next->next;
while(p!=L)
{
if(p->prior->data==cur_e)
{
*next_e=p->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
DuLinkList GetElemP(DuLinkList L,int i)
{
int j;
DuLinkList p=L;
for(j=1;j<=i;j++)
p=p->next;
return p;
}
Status ListInsert(DuLinkList L,int i,ElemType e)
{
DuLinkList p,s;
if(i<1||i>ListLength(L)+1)
return ERROR;
p=GetElemP(L,i-1);
if(!p)
return ERROR;
s=(DuLinkList)malloc(sizeof(DuLNode));
if(!s)
return OVERFLOW;
s->data=e;
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
return OK;
}
Status ListDelete(DuLinkList L,int i,ElemType *e)
{
DuLinkList p;
if(i<1||i>ListLength(L))
return ERROR;
p=GetElemP(L,i);
if(!p)
return ERROR;
*e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return OK;
}
void ListTraverse(DuLinkList L,void(*visit)(ElemType))
{
DuLinkList p=L->next;
while(p!=L)
{
visit(p->data);
p=p->next;
}
printf("\n");
}
void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))
{
DuLinkList p=L->prior;
while(p!=L)
{
visit(p->data);
p=p->prior;
}
printf("\n");
}