【双向链表的插入和删除】

双向链表的插入和删除】"/>

【双向链表的插入和删除】

文章目录

• 双向链表
• • 双向链表的插入
  • 双向链表的删除操作

双向链表

双向链表的结构定义如下：

//双向链表的结构定义
typedef struct DuLNode {ElemType data;struct DuLNode* prior, * next;
}DuLNode,*DuLinkList;

双向链表的结点有两个指针域：prior，next。

双向循环链表

• 让头结点的前驱指针指向链表的最后一个结点。
• 让最后一个结点的后继指向头结点。
  
  双向链表的对称性（设指针p指向某一结点）：
  p->prior->next = p = p->next->prior

双向链表的插入

将新结点s插入到p指针指向结点的前面。

①修改a结点的后继，a结点变成x的前驱。将x结点的前驱赋值a结点的地址，a结点的地址是b结点的前驱：p->prior。
s->prior = p->prior；
这个时候a结点就变成x结点的前驱结点了。

② 将x结点变成x结点的后继，这里是将a结点的next域由结点x的地址给出， p->prior->next = s；

③这里是将x的后继结点赋值，赋的b结点。
s->next = p；

④这里是将b结点的前驱结点赋值，赋的是s结点的地址。
p->prior = s；

【算法】双向链表的插入

//双链表的插入
int ListInsert(DuLinkList& L, int i, ElemType e) {//在带头结点的双向循环链表L中的第i个位置之前插入元素eDuLinkList p;if (L = NULL) {return 0;}DuLinkList s = new DuLNode;s->data = e;s->prior = p->prior;//s的前驱赋值p->prior->next = s;//前一个结点的后继也要赋值s->next = p;//再给s的后继赋值p->prior = s;//再给后一个结点的前驱赋值
}

双向链表的删除操作

将b节点删除，则a结点的后继就是c结点。c结点的前驱就是a结点。

①将a结点的后继改为c结点。需要给a结点的后继重新赋值。
p->prior->next = p->next.
②将c结点的前驱修改成a结点
p->next->prior = p->prior.

//双链表的删除
int ListDelete(DuLinkList& L, ElemType& e) {//删除带头结点的双向循环链表L的第i个元素，并用e返回。DuLinkList p;if (!(p == GetElem_Dul(L, i))) {return 0;}e = p->data;p->prior->next = p->next;//给前一个结点的后继赋值，赋的是后一个结点p->next->prior = p->prior;//给后一个结点的前驱赋值，赋的是前一个结点。free(p);return 1;
}