单向链表：http://blog.csdn.net/morixinguan/article/details/77756216

单向链表理解了，那双向就非常简单了，没什么好说的，看图：

双链表的引入是为了解决单链表的不足：

(1)双链表可以往前遍历，也可以往后遍历，具有两个方向双链表的节点 = 有效数据 + 两个指针(分别指向前一个节点和后一个节点)双向链表的图形结构描述:

可以用一个简单的数据结构来描述上面的这个图：

struct double_list					struct double_list{							{	数据域;                            ep :------->     int data ;	指针域(前向指针) ;  				    struct double_list *prev ;	指针域(后向指针) ;				    struct double_list *next ;};							};

2、双向链表的创建

struct list *create_node(int data) ;创建步骤(与单链表类似，就是多了一个指针):(1)给节点申请空间：   ep : struct double_list *p = malloc(sizeof(struct double_list));(2)初始化数据域   ep : p->data = data ;(3)初始化指针域   ep : p->prev = NULL ; 	    p->next = NULL ;

3、双向链表的尾插 双向链表尾插节点的函数可以定义如下： void double_list_tail_insert(struct double_list *header , struct double_list *new) ; 尾插图示操作：

尾插的步骤：

(1)找到链表的尾节点   ep : 和单链表差不多	    DL *p = header ;		while(NULL != p->next)			p = p->next ;(2)将新的节点连接到尾节点的后面成为新的节点   1.原来的next指针指向新节点的首地址。			p->next = new ;   2.新节点的prev指针指向原来的尾节点的首地址。 new->prev = p;

4、双向链表的头插 双向链表头插节点的函数可以定义如下： void double_list_top_insert(struct double_list *header , struct double_list *new) ;

5、双向链表的遍历

5.1 正向遍历	void double_list_for_each(DL *header)	步骤：和单链表完全一致，没什么好写的。		5.2 反向遍历	void double_list_for_each_nx(DL *header)	步骤：(1)和单链表一样，先循环找到最后一个节点的地址	      (2)再依靠prev指针循环往前移动			 2.1 先打印最后一个数据  ep : printf("%d ",p->data);			 2.2 向前循环遍历		 ep : p = p->prev ;			 			 判断条件：header->prev != p->prev,			 header保存的是头节点的地址,			 header->prev保存的是头节点的prev的地址,			 header->next保存的是头节点的next的地址,			 头节点在创建的时候:			 header->prev = NULL ;			 header->next = NULL ;			 所以这个条件这样写header->prev = NULL也是对的。

6、双向链表节点的删除

假设需要删除节点1：		首先:	(1)获取当前节点的地址： 		ep : p = header;	(2)遍历所有的节点，找到要删除的节点：		ep : 		while(NULL != p->next)		{			p = p->next ;			if(p->data == data)			{						}		}	(3)找到要删除的数据以后，需要做判断，判断两种情况，这和单链表差不多	3.1 如果找到当前节点的下一个节点不为空	3.1.1			那就把当前节点的prev节点指向要删除的这个节点的prev		因为当前的prev节点保存的是要删除的上一个节点的指针 		p->next->prev = p->prev ;	3.1.2			然后将当前节点的prev指针(也就是上一个节点的指针)指向当前节点(要删除的)的下一个节点:		p->prev->next = p->next ;	3.1.3			最后释放删除指针的空间：		free(p);			3.2 如果找到当前节点的下一个节点为空	3.2.1   	直接把当前指针(要删除的节点)的prev指针(保存着当前指针的上一个节点的地址)的下一个next指针设置为空。	p->prev->next = NULL ;	3.2.2	将删除的指针的空间释放:	free(p);

看来，双链表学起来比单链表容易多了！确实啊，多了一个方向，操作起来就更加容易了，但是多了一个方向，一维多了一个指针，相比增加了一定的复杂度，但是，只要牢记prev指针和next指针的指向，那么，手画一图，代码即可写出！

下面给一个案例实现一下双向链表：

#include 
    
     #include 
     
      #include 
      
       //创建一个双链表的数据结构typedef struct __double_list{	int data ;	struct __double_list *prev ;	struct __double_list *next ;}DL ; //创建双向链表并插入一个节点 DL *create_dl_node(int data){	DL *p = malloc(sizeof(DL));	if(NULL == p)	{		printf("create dl node fair!\n");		return NULL ;	}	//初始化数据 	p->data = data ;	//初始化指针 	p->next = NULL ;	p->prev = NULL ;}//双向链表的尾插 void double_list_tail_insert(DL *header , DL *new){	//取得当前节点的地址 	DL *p = header ;	//找到链表的尾节点 	while(NULL != p->next)	{		//找不到接着找 		p = p->next ;	}	//找到了尾节点，指向新节点的首地址 	p->next = new ;	//新节点的prev指针指向原来的尾节点的首地址。	new->prev = p;}//双向链表的头插(也就是插在两个节点之间的插入方式)void double_list_top_insert(DL *header , DL *new){	//新节点的next指针指向原来的节点一的地址	new->next = header->next ; 	//判断当前节点的下一个节点的地址是否为空	if(NULL != header->next) 		header->next->prev = new ; //节点1的prev指针指向新节点的地址 	header->next = new ;	new->prev = header ;}//双向链表的正向遍历 void double_list_for_each(DL *header){	DL *p = header ;	while(NULL != p->next)	{		p = p->next ;		printf("%d ",p->data);	}}//双向链表的反向遍历 void double_list_for_each_nx(DL *header){	DL *p = header ;	//先找到尾节点	while(NULL != p->next)	{		p = p->next ;		} 	//已经找到了尾节点，向前遍历，注意，遍历到头节点之前	//限制条件: != 头结点 	while(NULL != p->prev)	{		printf("%d ",p->data);		p = p->prev ;	}}//双向链表节点的删除int double_list_delete_node(DL *header , int data){	//取得当前节点 	DL *p = header;	//遍历所有的节点 	while(NULL != p->next)	{		p = p->next ;		//找到了对应要删除的数据了 		if(p->data == data)		{			//一样存在两种情况			//(1)当前节点的下一个节点不为空			if(p->next != NULL)			{				//那就把当前节点的prev节点指向要删除的这个节点的prev				//因为当前的prev节点保存的是要删除的上一个节点的指针 				p->next->prev = p->prev ;				//还要指定它的next节点 				p->prev->next = p->next ;				free(p);			}			//(2)当前节点的下一个节点为空 			else			{				//把 				p->prev->next = NULL ;				free(p); 			}			return 0 ;		}	}	printf("\n没有找到对应要删除的节点，或者节点已经被删除！\n");	return -1 ;	} int main(void){	int i ;	DL *header = create_dl_node(0);	for(i = 0 ; i < 10 ; i++)	{		//双向链表的尾插 		//double_list_tail_insert(header,create_dl_node(i));		//双向链表的头插 		double_list_top_insert(header,create_dl_node(i));	}	//双向链表的正向遍历 	printf("双向链表的正向遍历:");	double_list_delete_node(header,5);	double_list_for_each(header);//	double_list_delete_node(header,9);	double_list_delete_node(header,5);	putchar('\n');	printf("双向链表的反向遍历:");	double_list_for_each_nx(header);	return 0 ;}
      
     
    

运行结果：