线性链表 — 双向链表

悠悠 2022-04-16 04:23 324阅读 0赞

循环链表：特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。从表中任一结点出发均可找到表中其他结点。

双向链表：特点是结点有两个指针域（一个指向直接前驱，一个指向直接后继），一个数据域组成。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70][]

显然，结点d的指针由d->next->prior = d->prior->next = d

双向链表的插入与删除算法：

双向链表插入算法：

![20181116175945531.png][]

Status ListInsert_DuL(DuLinkList &L, int i,ElemType e){
    	//在带头结点的双链循环线性表L中第i个位置插入元素e
    	//i的合法值1≤i≤表长+1
    	if(!(p=GetElmeP_DuL(L,i))) //在L中确认插入的位置
    		return ERROR;//p=NULL，即插入的位置不合法
    
    	if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
    
    	s->data = e;
    	s->prior = p->prior; p->prior->next=s;
    	s->next=p;
    	p->prior=s;
    
    	return OK;
    }//ListInsert_DuL

双向链表删除算法：

![20181116180009711.png][]

Status ListDelete_DuL(DuLinkList &L, int i,ElemType e){
    	//在带头结点的双链循环线性表L中删除第i个元素的位置，并返回其值e
    	//i的合法值1≤i≤表长+1
    	if(!(p=GetElmeP_DuL(L,i))) //在L中确认插入第i个元素的位置指针p
    		return ERROR;//p=NULL，即第i个元素不存在
    	
    	e = p->data ;
    	p->prior->next=p->next;
    	p->next->prior=p->prior;
    
    	free(p);//释放空间
    	return OK;
    }//ListDelete_DuL

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70]: /images/20220416/02fd7ee5139c4b349729162466e12f85.png
[20181116175945531.png]: /images/20220416/ee073b3a4f6044379a5d88fbede3eae7.png
[20181116180009711.png]: /images/20220416/38795ee5084341d691bfa2b9afc3d163.png