单链表的创建，插入，删除以及查找

1.1 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 。

下面是数据结构中的链表

注意:
1.链式结构在逻辑上是连续的，但是物理上不是连续的
2.现实中的结点一般是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策略分配，但是两次申请的空间可能连续，也可能不连续

1.2 链表的分类

1.2.1 链表的结构分类

1.2.1.1单向或者双向

1.2.1.2带头或者不带头

1.2.1.3循环或者非循环

1.2.1.4 无头单向非循环链表

1.2.1.5 带头双向循环链表

1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

2.链表的实现

List.h

#pragma once
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);

// 单链表打印
void SListPrint(SListNode* plist);

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);

// 单链表的尾删
void SListPopBack(SListNode** pplist);

// 单链表头删
void SListPopFront(SListNode** pplist);

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);

void SListInsertAfter(SListNode* pos, SLTDateType x);

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);
void SLTDestroy(SListNode** pphead);

动态申请结点

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));

	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

单链表的打印

void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

单链表的尾插

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);

	SListNode* newnode = BuySListNode(x);

	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

单链表的头插

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

单链表的尾删

void SListPopBack(SListNode** pplist)
{
	assert(*pplist);
	assert(pplist);
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* tail = *pplist;

		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = NULL;
		free(tail);

	}
}

单链表头删

void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	SListNode* tmp = *pplist;
	*pplist = (*pplist)->next;
	free(tmp);
}

单链表查找

SListNode* SListFind(SListNode* plist, SLTDateType x)
{


	SListNode* cur = plist;

	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

在pos的前面插入

void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);

	//assert((!pos && !(*pphead)) || (pos && *pphead));//要么都是空要么都不是空
	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SListNode* newnode = BuySListNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}

删除pos位置

void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);

	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

指定位置后面插入

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);

	SListNode* newnode = BuySListNode(x);;
	newnode->next = pos->next;
	pos->next = newnode;
}

删除指定位置后面的结点

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* tmp = pos->next;

	pos->next = pos->next->next;

	free(tmp);
	tmp = NULL;
}

删除指定位置后面的结点

void SLTDestroy(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;

	}
	*pphead = NULL;
}