线性表的应用 —— 双向链表 && 循环链表

线性表的应用 —— 双向链表

在单链表中，每个元素都附加了一个指针域，指向下一个元素的存储位置。在双向链表中，每个元素都附加了两个指针域，分别指向前驱节点和后继节点。

单链表只能向后操作，不能向前操作。为了向前、向后操作方便，可以给每个元素都附加两个指针域，一个存储前一个元素的地址，一个存储下一个元素的地址。这种链表被称为双向链表：

可以看出，双向链表的每个节点都包含三个域：数据域和两个指针域。两个指针域分别存储前后两个元素的地址，即指向前驱节点和后继节点。

双向链表的节点结构体定义：

【插入】

单链表只有一个指针域，是向后操作的，不可以向前处理，因此单链表如果要在第i 个节点之前插入一个元素，则必须先找到第i -1个节点。在第i 个节点之前插入一个元素相当于把新节点放在第i -1个节点之后。而双向链表不需要，因为有两个指针，所以可以向前、后两个方向操作，直接找到第i 个节点，就可以把新节点插入第i个节点之前。

这里假设第i 个节点是存在的，如果第i 个节点不存在，而第i -1个节点存在，则还是需要找到第i -1个节点，将新节点插在第i -1个节点之后

① ：将节点s 的地址赋值给p 的前驱节点的next指针域，即p 的前驱的next指针指向s ；

② ：将p 的前驱节点的地址赋值给节点s 的prior指针域，即节点s 的prior指针指向p的前驱节点；

③ ：将节点p 的地址赋值给节点s 的next指针域，即节点s 的next指针指向节点p ；

④ ：将节点s 的地址赋值给节点p 的prior指针域，即节点p 的prior指针指向节点s 。

因为p 的前驱节点无标记，一旦修改了节点p 的prior指针，p 的前驱节点就找不到了，因此最后修改这个指针。
修改指针顺序的原则：先修改没有指针标记的那一端。

[算法实现]

bool ListInsert_L(DuLinkList &L , int i,int e){ // 在第i个位置之前插入e
	int j;
	DuLinkList p , s;
	p = L;
	j = 0;
	while(p && j < i){ // 查找第i个节点，p 指向该节点
		p = p->next;
		j ++;
	}
	if(!p || j > i){ // i > n + 1 或者 i < 1 ,不能进行插入
		return false; //插入失败
	}
	s = new DuLnode; //生成新节点
	s->data = e;  //将新节点的数据域置为e
	p->prior->next = s;
	s->prior = p->prior;
	s->next = p;
	p->prior = s;
	return true; //插入成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

【删除】

删除一个节点，实际上是把这个节点跳过去。在单链表中必须先找到第i -1个节点，才能把第i 个节点跳过去。
双向链表则不必如此，直接找到第i 个节点，然后修改指针即可。

“p ->prior->next=p ->next”指将p 的后继节点的地址赋值给p的前驱节点的next指针域。即p 的前驱节点的next指针指向p 的后继节点。

等号的右侧是节点的地址，等号的左侧是节点的指针域。

“p ->next->prior=p ->prior”指将p 的前驱节点的地址赋值给p的后继节点的prior指针域。即p 的后继节点的prior指针指向p 的前驱节点。此项修改的前提是p 的后继节点是存在的，如果不存在，则不需要修改此项。

这样，就把节点p 跳过去了。然后用delete p 释放被删除节点的空间。
删除节点修改指针没有顺序，先修改哪个都可以。

[算法实现]

bool ListDelete_L(DuLinkList &L , int i){ //删除第 i 个元素
	DuLinkList p;
	int j;
	p = L;
	j = 0;
	while(p && (j < i)){  // 查找第i个节点，p指向该节点
		p = p->next;
		j ++;
	}
	if(!p || (j > i)){ //当 i > n 或 i < 1时，说明删除位置不合理
		return false; //直接删除失败
	}
	if(p->next){ //如果p 的后继节点存在
		p->next-prior = p->prior;
	}
	p->prior->next = p->next;
	delete p;  //释放被删除节点的空间
	return true; //删除成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

线性表的应用 —— 循环链表

在单链表中，只能向后操作，不能向前操作，如果从当前节点开始，则无法访问该节点前面的节点；如果最后一个节点的指针指向头节点，形成一个环，就可以从任何一个节点出发，访问所有节点，这就是循环链表。
循环链表和普通链表的区别就是最后一个节点的后继指向了头节点。

【单链表】

单向循环链表最后一个节点的next域不为空，而是指向了头节点

单链表和单向循环链表判断空表的条件也发生了变化，
单链表为空表时，L ->next=NULL；

单向循环链表为空表时，L ->next=L

双向循环链表除了要让最后一个节点的后继指向第1个节点，还要让头节点的前驱指向最后一个节点

双向循环链表为空表时，L ->next=L ->prior=L

【链表的优缺点】

• 优点：
  链表是动态存储的，不需要预先分配最大空间。进行插入、删除时不需要移动元素。
• 缺点：
  每次都动态分配一个节点，每个节点的地址是不连续的，需要有指针域记录下一个节点的地址，指针域需要占用一个int的空间，因此存储密度低（数据所占空间/节点所占总空间）。存取元素必须从头到尾按顺序查找，属于顺序存取。