单链表创建·c语言版

链表结构作为数据结构的开头，让数据结构的初学者感到十分头疼。

 我们先简单看一下链表的结构，其实只有两个东西：一个节点和一个链接。

在c语言学习过指针后，我们都知道指针可以存放地址，所以我们用一个指针保存下一个节点的地址作为链接。

再来看一下链表和顺序表的对比

1.顺序表在使用前要先知道数据的大小，或者开辟额外足够大的空间。链表克服了顺序表需要提前开辟空间的缺点，充分利用计算机的内存空间。

2.顺序表支持通过下标进行随机访问，而链表失去了这个优点，在寻找节点是只能遍历寻找。

3.顺序表在进行插入或删除操作时往往需要对插入点后的元素进行移动，而链表只需改变指针存放的节点地址而已。

接下来看一下链表各种功能的实现吧 

 链表的初始化

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef struct SList
{
	int data;
	struct SL* next;
}SL;
void SLinit(SL* p, int x)
{
	p->data = x;
	p->next = NULL;
}

 链表的尾插

void SLpushback(SL** phead, int x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	newnode->data = x;
	newnode->next = NULL;
	if (!*phead)//判断链表的头节点是否为空，如果为空就把新节点给它
	{
		*phead = newnode;
	}
	else {
		SL* cur = *phead;//链表的头节点不能改变所以我们用一个临时变量指向头节点
		while (cur->next != NULL)//当next为空时表示走到了尾部
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

 链表的头插

void SLpushfront(SL** phead, int x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	newnode->next = *phead;//将新节点的nexr指针指向当前头节点
	newnode->data = x;
	*phead = newnode;//将头节点变为新节点
}

 链表的中间插入

void SLinsert(SL** phead, SL* pos, int x)
{
	if (pos == *phead)//如果插入的位置是头节点的位置，那就是头插
	{
		SL* newnode = (SL*)malloc(sizeof(SL));
		newnode->next = *phead;
		newnode->data = x;
		*phead = newnode;
	}
	else
	{
		SL* pre = NULL;//记录cur的前一个位置
		SL* cur = *phead;//往后移动寻找插入点
		while (cur)
		{
			if (cur == pos)
				break;//如果找到就跳出循环，否则就继续走
			pre = cur;
			cur = cur->next;
		}
		SL* newnode = (SL*)malloc(sizeof(SL));
		newnode->data = x;
		pre->next = newnode;//将插入点的位置变为新节点
		newnode->next = cur;//新节点的next指向插入位置
	}
}

链表的删除

void SLpopfront(SL** phead)//头删
{
	assert(*phead);//判断头节点不能为空
	SL* next = (*phead)->next;//记录当前头节点的下一个节点
	free(*phead);//释放头节点
	*phead = next;//将next变为头节点
}
void SLpopback(SL** phead)//尾删
{
	assert(*phead != NULL);
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SL* tail = *phead;
		SL* pre = NULL;//记录尾节点的前一个节点
		while (tail->next)
		{
			pre = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		if (pre)
		{
			pre->next = NULL;//将尾节点的前一个结点置空
		}
	}
}

void SLerase(SL** phead, SL* pos)
{
	if (*phead == pos)//如果删除位置为头节点，就是头删
	{
		SLpopfront(phead);
	}
	else {
		SL* pre =*pphead;
		while (pre->next!=pos)
		{
			pre = pre->next;
		}
		pre->next = pos->next;//将要删除的节点的前一个节点的next指向删除位置的next
		free(pos);
		pos = NULL;
	}
}

 链表的查找

SL* SLfind(SL* phead, int x)
{
	SL* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

最后向大家推荐一个网站，可以在这上面看链表操作的动态展示。 

链表的动态演示