数据结构-双向链表创建

        我们常见的单链表能很好的表示元素间“一对一”的关系，也能根据指针的走向找到某个元素的后继结点，但是对于一些特殊问题，比如需要大量查找到一个元素的前驱结点，单链表总是通过从头向后遍历的方式无疑使运行速度和效率大大降低，为此，我们将引出一个新的链表数据结构，也就是双链表。

[单链表结构图]:

         双链表，也称双向链表，顾名思义，它是具有两个方向的链表，不像单链表形式那么单一，相比单链表多了一个指针域。

        生动点描述就是，双链表——“多给自己留后路”，而单链表——“一条路走到天黑”。所以双链表做事更灵活效率更高，单链表显得就有些轴。当然，单链表也有自己的优势，那就是比双链表更加节省空间，因为它只占一个指针域。

[双链表结构图]:

 从上图可知双向链表的节点结构包括：

（1）前指针域

（2）数据域

（3）后指针域

[双链表结点结构图]

双链表结点的代码实现：

 
typedef struct Line{
	struct Line*prior;//前指针域：指向直接前趋结点 
	int data;//数据域 
	struct Line*next;//后指针域：指向后继结点 
}line;

 双向链表的创建：

 
line*initLine(line*head){
	head=(line*)malloc(sizeof(line));//创建链表第一个结点
	head->prior=NULL;
	head->next=NULL;
	head->data=1;
	line*temp=head;
	for(int i=2;i<5;i++){
		line*body=(line*)malloc(sizeof(line));
		body->prior=NULL;
		body->next=NULL;
		body->data=i;
		
		temp->next=body;//前趋结点指向后继结点 
		body->prior=temp;//新结点指向前趋结点 
		temp=temp->next;//指针向后移动 
	} 
}

完整C语言代码：

#include
#include
 
typedef struct Line{
	struct Line*prior;//前指针域：指向直接前趋结点 
	int data;//数据域 
	struct Line*next;//后指针域：指向后继结点 
}line;
 
line*initLine(line*head){
	head=(line*)malloc(sizeof(line));//创建链表第一个结点
	head->prior=NULL;
	head->next=NULL;
	head->data=1;
	line*temp=head;
	for(int i=2;i<5;i++){
		line*body=(line*)malloc(sizeof(line));
		body->prior=NULL;
		body->next=NULL;
		body->data=i;
		
		temp->next=body;//前趋结点指向后继结点 
		body->prior=temp;//新结点指向前趋结点 
		temp=temp->next;//指针向后移动 
	} 
	return head;
}
 
void display(line*head){
	line*t=head;
	while(t){
		//如果该节点无后继节点，说明此节点是链表的最后一个节点
		if(t->next==NULL){
			printf("%d\n",t->data);
		}else{
			printf("%d<->",t->data);
		}
		t=t->next;
	}
}
int main()
{
	line*list=NULL;
	list=initLine(list);
	display(list);
	//显示双链表的优点
    printf("链表中第 4 个节点的直接前驱是：%d",list->next->next->next->prior->data);
	return 0;
} 

输出结果：