链表

链表主要有以下几大特性：

1、解决数组无法存储多种数据类型的问题。

2、解决数组中，元素个数无法改变的限制(C99的变长数组，C++也有变长数组可以实现)。

3、数组移动元素的过程中，要对元素进行大范围的移动，很耗时间，效率也不高。

先来感性的认识一下链表,我们先来认识下简单的链表:

从这幅图我们得出以下信息:

这个简单链表的构成：

头指针(Header)，若干个节点(节点包括了数据域和指针域)，最后一个节点要指向空。

实现原理：头指针指向链表的第一个节点，然后第一个节点中的指针指向下一个节点，然后依次指到最后一个节点，这样就构成了一条链表。

接下来看看链表的数据结构:

struct  list_node
{
	int data ; //数据域，用于存储数据
	struct list_node *next ; //指针，可以用来访问节点数据，也可以遍历，指向下一个节点
};

那么如何来创建一个链表的一个节点呢？

我们写个程序演示一下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct  list_node
{
	int data ; 
	struct list_node *next ;
};

typedef struct list_node list_single ; 	

int main(void)
{
	list_single *node = NULL ;          //1、首先，当然是定义一个头指针
	node = (list_single *)malloc(sizeof(list_single)); //2、然后分配内存空间
	if(node == NULL){
		printf("malloc fair!\n");
	}
	memset(node,0,sizeof(list_single)); //3、清一下
	node->data = 100 ;		    		//4、给链表节点的数据赋值
	node->next = NULL ;                 //5、将链表的指针域指向空
	printf("%d\n",node->data);
	free(node);
	return 0 ;
}

那么，这仅仅只是创建一个链表中的一个节点，为了好看，我们把创建节点封装成函数，以后想创建多少个节点，我们就可以反复调用一个函数来创建，会很方便:

list_single *create_list_node(int data)
{
	list_single *node = NULL ;
	node = (list_single *)malloc(sizeof(list_single));
	if(node == NULL){
		printf("malloc fair!\n");
	}
	memset(node,0,sizeof(list_single));
	node->data = 100 ;
	node->next = NULL ;
	return node ;
}

接下来在程序上完成的程序:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct  list_node
{
	int data ; 
	struct list_node *next ;
};

typedef struct list_node list_single ; 	
list_single *create_list_node(int data)
{
	list_single *node = NULL ;
	node = (list_single *)malloc(sizeof(list_single));
	if(node == NULL){
		printf("malloc fair!\n");
	}
	memset(node,0,sizeof(list_single));
	node->data = data;
	node->next = NULL ;
	return node ;
}
int main(void)
{
	int data = 100 ;
	list_single *node_ptr = create_list_node(data); //创建一个节点
	printf("node_ptr->data=%d\n",node_ptr->data);   //打印节点里的数据
	printf("node_ptr->next=%d\n",node_ptr->next);  
	free(node_ptr);
	return 0 ;
}

执行结果 ：

这样我们就完成一个链表节点的创建了，那么它现在的样子如下图：

链表的结构里，数据存储了100，因为这个链表只有一个节点，所以它的指针域指向了NULL。

上面只是建立一个单链表的基本雏形，接下来咱们再来增加一点难度。如果创建多个单链表节点，实现单链表的增删改查？把单链表应用起来。

1、首先定义一个单链表的数据结构

创建节点函数原型可定义如下：
struct list *create_node(int data) ;
如何创建单链表的节点，主要分以下步骤:
(1)给当前的每个节点的数据结构配置定量的空间大小
ep : struct list *node = malloc(sizeof(struct list));
(2)清节点数据(由于结构体变量在未初始化的时候，数据是脏的)
ep : memset(node,0,sizeof(struct list));
(3)给节点初始化数据
ep : node->id = data ;
(4)将该节点的指针域设置为NULL
ep : node->next = NULL ;

2、单链表的尾插：

尾插节点函数原型可定义如下：

如何将当前链表和新的节点相连接？只要实现：
header->next = new
尾插流程如下：

(1)获取当前节点的位置，也就是访问头节点
ep : struct list *p = header ;
(2)判断是否为最后一个节点，如果不是，移动到下一个节点，如果是，将数据插入尾部。
ep : while(NULL != p->next) p = p->next ;
p->next = new ;

3、单链表的头插

很好理解，头插就是把新的节点插在原来的节点和原来节点的下一个节点之间的一个节点。如图，新的节点插在头节点和节点1。
所以可以推出头插流程如下：
(1)获取当前节点的位置，也就是访问头节点
ep : struct list *p = header ;
(2)新的节点的下一个节点设置为原来头节点的下一个节点(第一个节点)
ep : new->next = p->next ;
(3)原来的头节点的下一个节点设置为现在新插入的头节点
ep : p->next = new ;

4、单链表的遍历

如图为一条单向链表的模型，看图知道该链表由头节点和若干个节点组成，最后一个节点(尾节点)为NULL 。
从图中可以得出信息，如果我们要打印出各个节点的数据，要考虑以下问题：
(1)需要打印头节点吗？(头节点肯定是不用打印的，因为这是我们为了操作方便而设置的一个节点)。
(2)这条链表有多少个节点我们怎么知道？(通过判断该链表是否已经到达了尾节点，标志就是NULL)
那么可以得到流程如下：
(1)获取当前节点的位置，也就是访问头节点
ep : struct list *p = header ;
(2)由于头节点我们不需要去打印它，这时候，初始化打印的节点需要从第一个节点开始。
ep : p = p->next ;
(3)判断是否为最后一个节点，如果不是，先打印第一个节点的数据(1)，然后移动到下一个节点(2),重复这两个步骤。
如果是最后一个节点，直接打印数据即可。
while(NULL != p->next){ printf(“node:%d\n”,p->data) ; p = p->next ;}
printf(“node:%d\n”,p->data);
当然还可以一句代码解决，这样就达到了先偏移，后取数据。
while(NULL != p->next){ p = p->next ; printf(“node:%d\n”,p->data) ; }

5、单链表的删除

删除节点的函数原型可定义如下：
int detele_list_node(struct list *pH , int data);
单向链表的删除要考虑两种情况，一种的普通节点的删除(当然，头节点不能算)
还有一种是尾节点的前一个节点的删除情况，注意，删除完节点还需要释放对应节点的内存空间。

删除节点的设计流程：
(1)先定义两个指针，一个表示当前的节点，另一个表示当前节点的上一个节点。
ep : struct list *p = header ; //当前节点
struct list *prev = NULL ; //当前节点的上一个节点
(2)遍历整个链表，同时保存当前节点的前一个节点
ep : while(NULL != p->next)
{
//保存了当前的节点的前一个节点
prev = p ;
//保存当前偏移的节点
p = p->next ;
return 0 ;
}
(3)在遍历的过程中查找要删除的数据
ep : while(NULL != p->next)
{
//保存了当前的节点的前一个节点
prev = p ;
//保存当前偏移的节点
p = p->next ;
//查找到了数据
if(p->id == data)
{

}
return 0 ;
}
(4)查找到了数据后，分两种情况删除
ep : 普通节点的删除
if(p->id == data)
{
prev->next = p->next ;
free(p);
}
ep : 考虑尾节点的下一个节点为NULL的节点删除
if(p->id == data)
{
if(p->next == NULL)
{
prev->next = NULL ;
free(p);
}
}

6、单链表的逆序

逆序步骤：

单链表的基本操作流程咱们基本搞懂了，下面写一个程序，这将会变得非常非常的简单。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct slist
{
	int id ;
	struct slist *next ;			
}L;
 
//创建一个节点 
L *create_node(int data)
{
	//给每个节点分配结构体一样的空间大小 
	L *p = malloc(sizeof(L));
	if(NULL == p)
	{
		printf("malloc error!\n");
		return NULL ;
	}
	//由于结构体在未初始化的时候一样是脏数据，所以要清 
	memset(p,0,sizeof(L));
	//初始化第一个节点 
	p->id = data ; 
	//将节点的后继指针设置为NULL 
	p->next = NULL ;
}
 
//链表的尾插 
void tail_insert(L *pH , L *new)
{
	//获取当前的位置 
	L *p = pH ; 
	//如果当前位置的下一个节点不为空 
	while(NULL != p->next)
	{
		//移动到下一个节点 
		p = p->next ;
	}
	//如果跳出以上循环，所以已经到了NULL的这个位置
	//此时直接把新插入的节点赋值给NULL这个位置 
	p->next = new ;
}
 
//链表的头插 
void top_insert(L *pH , L *new)
{
	L *p = pH ;
	new->next = p->next ;
	p->next = new ;
}
 
//链表的遍历 
void Print_node(L *pH)
{
	//获取当前的位置 
	L *p = pH ;
	//获取第一个节点的位置 
	p = p->next ;
	//如果当前位置的下一个节点不为空 
	while(NULL != p->next)
	{
		//(1)打印节点的数据 
		printf("id:%d\n",p->id);
		//(2)移动到下一个节点,如果条件仍为真，则重复(1)，再(2) 
		p = p->next ;
	}
	//如果当前位置的下一个节点为空，则打印数据
	//说明只有一个节点 
	printf("id:%d\n",p->id);
}
 
//删除链表中的节点 
int detele_list_node(L * pH , int data)
{
	//获取当前头节点的位置 
	L *p = pH ;
	L *prev = NULL;
	while(NULL != p->next)
	{
		//保存当前节点的前一个节点的指针 
		prev = p ;
		//然后让当前的指针继续往后移动 
		p = p->next ; 	
		//判断，找到了要删除的数据  
		if(p->id == data)
		{
			//两种情况，一种是普通节点，还有一种是尾节点
			if(p->next != NULL)  //普通节点的情况 
			{
				prev->next = p->next ;
				free(p);
			}
			else //尾节点的情况 
			{
				prev->next = NULL ; //将这个尾节点的上一个节点的指针域指向空 
				free(p); 
			}
			return 0  ;
		}
	}
	printf("没有要删除的节点\n");
	return -1 ;
}
 
void trave_list(L * pH)
{
	//保存第一个节点的位置 
	L *p = pH->next;
	L *pBack;
	int i = 0 ;
	if(p->next == NULL || p == NULL)
		return ;
		
	while(NULL != p->next) //遍历链表 
	{
		//保存第一个节点的下一个节点 
		pBack = p->next ; 
		//找到第一个有效节点,其实就是头指针的下一个节点 
		if(p == pH->next) 
		{
			//第一个有效节点就是最后一个节点，所以要指向NULL 
			p->next = NULL ; 
		} 
		else
		{
			/*
			new->next = p->next ;
			p->next = new ;
			*/
			p->next = pH->next ; //尾部连接 
		}
		pH->next = p ; //头部连接 
		p = pBack ; //走下一个节点 
	}
	top_insert(pH,p); //插入最后一个节点 
}
 
int main(int argc , char **argv) 
{
	//创建第一个节点 
	int i ;
	L *header = create_node(0); 
	for(i = 1 ; i < 10 ; i++)
	{
		tail_insert(header,create_node(i));
	}
	Print_node(header);
	detele_list_node(header,5);
	putchar('\n');
	Print_node(header);
	putchar('\n');
	trave_list(header);
	Print_node(header);
	return 0 ;
}

运行结果：

当然，单链表存在一定的弊端，就是查找数据和删除数据的时候比较麻烦，而双链表的出现就是为了解决它的弊端：

双链表的引入是为了解决单链表的不足：
(1)双链表可以往前遍历，也可以往后遍历，具有两个方向
双链表的节点 = 有效数据 + 两个指针(分别指向前一个节点和后一个节点)
双向链表的图形结构描述:

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

1、双向链表的创建

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 ;

2、双向链表的尾插

双向链表尾插节点的函数可以定义如下：
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;

3、双向链表的头插

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

4、双向链表的遍历

4.1 正向遍历
void double_list_for_each(DL *header)
步骤：和单链表完全一致，没什么好写的。

4.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也是对的。

5、双向链表节点的删除

假设需要删除节点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 <stdio.h>
#include <stdlib.h>
#include <string.h>
//创建一个双链表的数据结构
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 ;
}

运行结果：