一、链表的定义

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

为了往后使用数据类型的变换，这里通过typedef 给int换了一个名字，后面我们要换其他的数据类型可以直接吧第一行的int换成你想要的类型。

结构体内data储存数据，next储存下一个节点的地址。

我们接下来创建一个节点。

二、创建一个节点

SLTNode* BuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)//当内存申请失败了需要报错并停止运行
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	return newnode;
}

我们需要用到一个SLTNode *类型的函数，因为我们要返回创建节点的地址。

这样我们就可以创建一个链表并在里面插入数据了

int main()
{
	SLTNode* plist = NULL;
	phead = BuyNode(1);
}

phead表示为头结点。

三、对链表进行头插

void PushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode *newnode=BuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

这里要注意的是，用到了二级指针，之所以要用二级指针是因为：我们需要改变phead的值，所以我们必须要把plist的地址传进来。

四、对链表进行头插

这里需要分情况讨论：1、链表非空。2、链表为空。

当链表非空的时候，我们只需要找到尾节点，然后接上新节点就可以了。

但当链表为空的时候，我们就要让头指针指向新节点（需要改变头指针phead），所以还是需要用到二级指针。

void SlistPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuyNode(x);
	if (*pphead == NULL)
		*pphead = newnode;
	else
	{
		//找到尾节点
		SLTNode* tail=*pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

五、对链表进行头删

这里我们设置了一个del变量储存将要删除的节点，每次删除节点我们都要free掉这个节点，不然会有内存泄露的风险。

void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
	del = NULL;
}

六、对链表进行尾删

void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
		return;
	//一个节点
	//多个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;

	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
		tail = NULL;
	}
}

因为尾结点需要找到为节点的前一个节点，并将其next值设置为NULL，所以需要分情况讨论。

七、对链表的打印

void SLTPrint(SLTNode* phead)
{
	if (phead = NULL)
		return;
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

八、对链表的销毁

与上面的删除同理，链表的节点都是malloc出来的，养成好习惯，把每个malloc的空间的返回给系统避免资源浪费。

void SLTistDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

最后记得把phead指向NULL（也就是*pphead），避免野指针的产生。

九、对链表的查找

注意它的返回类型是节点的指针型，在没找到节点时返回NULL。

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	if (phead == NULL)
		return;
	SLTNode* cur=phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

十、对链表某个数据前插入

我们需要通过上面的find函数，找到我们想在哪个元素前插入的位置（pos）。我们需要找到pos亲一个节点prev，然后再把新节点插入prev节点与pos节点之间。

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assrtt(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SListPopFront(x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
			prev = prev->next;
		SLTNode* newnode = BuyNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}

十一、对链表某个数据后插入

因为单向链表只能从前往后查找，所以我们需要从头结点一个个往下找，才能找到插入的位置。

但是如果你想在某个元素后面插入数据的话，只需要往下找一个就行了。

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* next = pos->next;
	SLTNode* newnode = BuyNode(x);
	newnode->next = next;
	pos->next = newnode;

}

十二、对链表某个位置删除

需要分情况讨论，我这里用了两个指针，当链表只有一个元素的时候不需要两个指针，所以需要分情况讨论。

void SListErase(SLTNode **pphead,SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	SLTNode* prev=*pphead;
	if (pos == prev)
	{
		*pphead = pphead->next;
		free(pos);
		pos = NULL;
	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}

}

思路就是把要删除位置的前一个（prev）找到，然后吧prev的next改成pos的next，最后释放pos

给你这样一个链表，你如何在3节点前插入一个节点并且不遍历这个链表。

你如何在把3节点删除不遍历这个链表。

十三、不遍历插入节点

给出思路，在3节点后面插入一个节点：

并将其赋予3节点的值：

最后将三节点的值改为要插入的值：

大功告成，贴上代码：

void SListInsertBefore(SLTNode* pos,SLTDataType x)
{
	assert(pos);
	SLTNode *newnode=(SLTNode *)malloc(sizeof(SLTNode));
	newnode->data = pos->data;
	newnode->next = pos->next;
	pos->next = newnode;
}

十四、不遍历删除一个节点

上思路：先把4节点的值赋予3节点。

然后将3节点的next指向4节点的下一个。

最后再将4节点销毁。

上代码：

void SListErasePos(SLTNode* pos)
{
	assert(pos&&pos->next);
	SLTNode* next = pos->next;
	pos->data = next->data;
	pos->next = pos->next->next;
	free(next);
	next = NULL;//养成好习惯，吧malloc的空间释放掉
}

这个方法还是有一个缺陷，就是pos不能指向最后一个节点。而上一个方法就没有这个烦恼。

对于这些方法也不用太纠结，因为日常使用中双向链表才是最实用的。