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

双向链表

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

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

双向链表的结点有两个指针域：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个位置之前插入元素e
	DuLinkList 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;//再给后一个结点的前驱赋值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

双向链表的删除操作

将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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13