前面提到了数据结构中的顺序表，今天就来看看数据结构中的链表。

数据结构中的链表分为单向链表，双向链表，双向循环链表，以及内核链表

单向链表

单向链表由一个个节点组成，节点则由两个部分组成，分别是数据域和指针域。数据域存放的是该节点的数据，指针域存放的则是下一个节点的地址。下面是一个节点的示意图

​编辑

所以定义一个链表就非常的清晰明了。

typedef struct stu{	datatype data;	struct stu *next; 	}link_t;

链表定义之后，首先就是要对其进行初始化。开始定义的节点为头结点，此时没有下一个节点，故此时它的指针域指向空

link_t*link_init(void){	link_t *p = (link_t*)malloc(sizeof(link_t));	if(p == NULL);	{		perror("malloc error");		return NULL;	}		p-next = NULL;		return p;}

作为测试一下函数。

​编辑

链表的操作也是一样的

增删改查

增

链表需要增加，首先就需要创建一个新的节点，然后使头节点的指针域指向它即可。

​编辑

插入函数如下

void insert(link_t *p,link_t *node){	node->next = p->next;	p->next = node;	}

接下来做头插处理。

void insert_heard(link_t *p,datatype data){	//创建一个新的节点	link_t *node = link_init();	if(node == NULL)		return NULL;		node->data = data;		insert(p,node);	}

为了更好的测试，所以需要先做遍历函数。遍历的条件是当p->不为空是进行遍历

/*=====================================【函数名称】: display【函数功能】: 遍历=====================================*/void display(link_t *p){	printf("遍历结果为\n");	while(p->next != NULL)	{		p = p->next;		printf("%d ",p->data);	}printf("\n");	}

测试结果如下

​编辑

接下来就是尾插的操作，尾插的操作和头插类似。不过首先要找到尾巴。尾巴最后一个肯定是空，通过这个条件就可以判断了。

//找到尾巴，将数据插到尾巴上

while(p->next != NULL)

p = p->next;

void insert_tail(link_t *p,datatype data){	//创建一个新的节点	link_t *node = link_init();	if(node == NULL)		return;		node->data = data;	//找到尾巴，将数据插到尾巴上	while(p->next != NULL)		p = p->next;			insert(p,node);	}

结果如下；

删除操作，先遍历寻找我们需要更改的数据，新建一个节点，用旧节点替换新节点。再将旧节点释放

/*=====================================【函数名称】: del【函数功能】: 删除=====================================*/void del(link_t *p,datatype data){	link_t *node = NULL;	while(p->next != NULL)	{		node = p->next;		if(node->data == data)		{			// 将node 孤立出来 			p->next = node->next;						// 释放 node			node->next = NULL;			free(node);									continue;		}				p = p->next;	}}

结果如下

​编辑

更新操作

​编辑

void updata(link_t *p,datatype old,datatype new){		link_t *node = NULL;	link_t *new_node = NULL;	while(p->next != NULL)	{		node = p->next;		if(node->data == old)		{			// 通过 new 创建新的节点 			new_node = link_init();			if(new_node == NULL)				return;			new_node->data = new;			// 新的节点替换旧的节点 			new_node->next = node->next;			p->next = new_node;						// 释放旧节点 			node->next = NULL;			free(node);		}				p = p->next;	}}	

以上就是单向链表

​