双向链表

凌阳教育

循环链表的链式存储结构的结点只有一个指示直接后继的指针域，由此，从某个结点只能顺指针往后寻常其他结点。若要寻查结点的直接前驱，则需要从表头指针出发。换句话说，在单链表中，NextElem的执行时间为O（1），而PriorElem的执行时间为O（n）。为克服单链表这种单向性的缺点，可利用双向链表。

顾名思义，在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱，在C语言中可描述如下：

//---------------------线性表的双向链表存储结构------------------------

typedef struct        DuLNode{

       ElemType                     data;

       structDuLNode             *prior;

       structDuLNode             *next;

}DuLNode, *DuLinkList

和单链表的循环表类似，双向链表也可以有循环表，如图c所示，链表中存有两个环，图b所示为只有一个表头结点的空表。

在双向链表中，若d为指向表中某一结点的指针（若d为DuLinkList型变量），则显然有

d—>next->prior=d->prior->next=d

这个表示式恰当地反应了这种结构的特性。

在双向链表中，有些操作如：ListLength、GetElem和LocalElem等仅需涉及一个方向的指针，则它们的算法描述和线性链表的操作相同，但在插入、删除时有很大的不同，在双向链表中需同时修改两个方向上的指针，图分别显示了删除和插入结点指针修改的情况。它们的算法分别如算法所示，两者的时间复杂度均为O（n）。

Status ListInsert_DuL(DuLinkList &L,inti,ElemType e){

//在带头结点的双链循环线性表L中第i个位置之前插入元素e，

//i的合法值为1≤i≤表长+1.

if(!(p=GetElemP_DuL(L,i))) //在L中确定插入位置指针p

return ERROR;                         //i等于表长加1时，p指向头结点；i大于表长加1时，

                                                 //p=NULL

if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))returnERROR;

s->data =e;

s->prior =p->prior ;p->prior->next=s;

s->next=p;      p->prior =s;

return OK;

}//ListInsert_DuL

Status ListDelete_DuL(DuLinkList &L,inti,ElemType e){

//删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长

if(!(p=GetElemP_DuL(L,i))) //在L中确定第i个元素的位置指针p

return ERROR;                         //p=NULL，即第i个元素不存在

if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))returnERROR;

e=p->data;

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);return OK;

}//ListDelete_DuL

凌阳教育，全国唯一一家原厂式嵌入式培训机构，专业从事嵌入式人才培训13年，最近新开课程信息安全工程师培训，想了解更多嵌入式资料下载或者是凌阳教育的动态，请访问凌阳教育官网www.sunplusedu.com。