双向链表

双向链表:在单链表的每个结点里再增加一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表。

双向链表的结构可定义如下:

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

双向循环链表

和单链的循环表类似，双向链表也可以有循环表

• 让头结点的前驱指针指向链表的最后一个结点
• 让最后一个结点的后继指针指向头结点。

双向链表结构的对称性（设指针p指向某一结点)

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

双向链表的插入

1. s->prior=p->prior;
2. p->prior->next=s;
3. s->next=p;
4. p->prior=s;

void Listlnsert_DuL(DuLinkList &L, Int i，ElemType e) {//在带头结点的双向循环链表L中第i个位置之前插入元素eif(!(p=GetElemP_DuL(Li))) return ERROR;s=new DuLNode;s ->date = e;s ->prior = p ->prior;p->prior ->next = s;s ->next = p;p->prior = s;return OK;}// Listlnsert_DuL

双向链表的删除

1. p->prior->next=p->next;
2. p->next->prior=p->prior;

void ListDelete_DuL(DuLink &L, Int i, ElemType &e) {//删除带头结点的双向循环链表L的第i个元素，并用e返回。if(!(p=GetElemP_DuL(Li)))return ERROR;e = p -> data;p-> prior -> next = p -> next;p -> next -> prior = p-> prior;free(p);return OK;}// ListDelete_DuL

开发者涨薪指南 48位大咖的思考法则、工作方式、逻辑体系