数据结构-双向链表_给定双向链表的一个节点的饿指针,以此节点开始将链表按节点数值由大到小重新排序

简介：

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

图示：

C语法实现：

#include<bits/stdc++.h>
using namespace std;

typedef struct Node{
 	int data;
 	Node *next;
 	Node *prior;
}*List;

void init_list(List &hed){
 	hed = new Node;
 	hed->next = NULL;
 	hed->prior = NULL;
}
void insert_node(List &hed, List temp){
 	temp->next = hed->next;
 	if(temp->next != NULL)//溢出 
  		hed->next->prior = temp;
 	hed->next = temp;
 	temp->prior = hed; 
}
void insert_value(List &hed, int e){
 	List temp = new Node;
 	temp->data = e;
 	insert(hed, temp);
}
void print_list(List &hed){
 	for(List i = hed->next; i; i = i->next)
  		cout << i->data << " ";  
}

int main(){
 	List hed;
 	init_list(hed);
 	for(int i = 1; i < 10; i++)
  		insert(hed, rand()%100);
 	print_list(hed);
 	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

实现很简单，但是有一点需要注意，即代码示例中注释部分。因为初始化时设置的头节点前后指针皆置空。 当第一次插入节点的时候，hed->next指向NULL，NULL不是一个节点，自然其没有前后指针域。指向的时候也自然会报错。

双链表优点：

查找：

因为前后指针的存在，查找指定节点前后节点便不需要再通过遍历整个链表而实现，即将原来的O(n)时间复杂度，降低到O(1)。

int search_prior(List hed, List n){
 	if(n->prior != hed)
  		return n->prior->data;
 	else 
  		return -1;
}
int search_next(List n){
 	if(n->next != NULL)
  		return n->next->data;
 	else 
  		return -1; 
}
1
2
3
4
5
6
7
8
9
10
11

因为数据采用的是头插法，可能会出现指定节点的前一个节点是头节点，因此逻辑上加上判断。查询后一个节点时同上。

删除：

这里删除只实现删除指定节点的前后节点。删除指定数值的实现可参考单链表，二者类似。

bool delete_prior(List hed, List n){
 	if(n->prior != hed){
  		List temp = n->prior;
  		temp->prior->next = n;
  		n->prior = temp->prior;
  		delete temp;
 	} else
  		return false;
} 
bool delete_next(List n){
 	if(n->next != NULL){
  		List temp = n->next;
  		if(temp->next != NULL){//删除倒数第一个节点 
   			temp->next->prior = n;
   			n->next = temp->next;
  		} else{
   			delete temp;
   			n->next = NULL;
  		}
  		delete temp;
 	} else 
  		return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

注意：特殊节点的删除。