链表入门（单链表讲）

1.链表

1.1 链表概念及其结构

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

• 链表结构如图所示：
  

1.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向
   

2. 带头或者不带头
   

3. 循环或者非循环
   

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

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

2.单链表代码实现

2.1 单链表的定义

我们在了解线性结构最重要的就是明白这个结构是如何定义的，是怎样的一种结构。这里单链表的定义，我们考虑的是我们需要这个结构中包含什么，这里我们需要的是一个数据域和一个指针域，数据域用于存储数据，指针域用于链接每个单链表节点。行，我们来rua一下：

typedef int SLTDateType;//typedef 一下，方便我们更改所需存储的类型
typedef struct SListNode
{
	SLTDateType data;//数据域，用于存储数据
	struct SListNode* next;//指针域，用于链接下一个结点
}SLTNode;

2.2 单链表的初始化

单链表一般不直接提供初始化接口，是因为单链表的初始化不需要额外的方法来完成，可以通过其他操作来实现。

一般而言，单链表的初始化可以分为两种方式：

1. 首先创建一个空链表，然后逐个插入节点，直到构建完整的链表。

SLTNode* plist = NULL;//后续只需要不断插入新的结点就可以

2. 直接在创建链表的过程中完成节点的插入操作，不需要单独的初始化方法。

因此，为了简化接口设计和操作复杂度，单链表通常不提供单独的初始化接口，而是通过其他操作来实现链表的构建和初始化。

2.3 单链表的新增结点

这里就可以看到我们在为一个指针开辟空间后就立马初始化了，和上述第二种初始化的方法相同。

SLTNode* SLTNewNode(SLTDateType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	//开辟一个链表结点大小的空间
	if (node == NULL)//检测是否开辟成功
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->next = NULL;
	return node;
}

2.4 单链表的打印

为了方便测试一般我们会使用链表打印接口来查看检测。

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

2.4 单链表的插入

这里涉及到单链表的一个难点，就是这里需要二级指针，我们需要更改一级指针内的元素数据，所以需要用二级指针来更改。就例如我们要改变一个数据类型的值，需要一级指针一样。

2.4.1 头插

在链表第一个结点前插入。

void SLTPushFront(SLTNode** ppa, SLTDateType x)
{
	assert(ppa);//&plist(ppa)不可能为空，所以需要检测
	SLTNode* newnode = SLTNewNode(x);
	newnode->next = *ppa;//新节点的next指针指向链表开头（*ppa）
	*ppa = newnode;//更新头指针
}

2.4.2 尾插

在链表最后结点后插入

void SLTPushBack(SLTNode** ppa, SLTDateType x)
{
	assert(ppa);	
	SLTNode* newnode = SLTNewNode(x);

	if (*ppa == NULL) //判断链表是否为空
	{
		*ppa = newnode;
	}
	else
	{
		//找尾操作，这里单链表我们只能使用遍历来实现，当找到一个节点的next指针指向null时，就代表找到尾了。
		SLTNode* tail = *ppa;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

2.4.3 任意位置插入

pos前位置插入，我们知道了尾插，这里就相当于把pos位置当做尾，去找pos位置，然后再用头插的思路完成。

//任意位置插入(pos前插入)
void SLTInsertF(SLTNode** ppa, SLTNode* pos, SLTDateType x)
{
	assert(ppa);
	assert(pos);
	if (pos == *ppa)
	{
		SLTPushFront(ppa, x);
	}
	else 
	{
		SLTNode* tmp = SLTNewNode(x);
		SLTNode* prev = *ppa;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = tmp;
		tmp->next = pos;
	}
}

pos位置后插入：学习了任意位置插入，我们其实可以把头插和尾插的实现过程改成调用任意位置插入接口

void SLTInsertB(SLTNode** ppa, SLTNode* pos, SLTDateType x)
{
	assert(ppa);

	if (pos == NULL)
	{
		SLTPushBack(ppa, x);
	}
	else
	{
		SLTNode* newnode = SLTNewNode(x);
		SLTNode* cur = *ppa;
		while (cur != pos->next)
		{
			cur = cur->next;
		}
		pos->next = newnode;
		newnode->next = cur;
	}
}

2.5 单链表的删除

2.5.1 头删

头删的思路就是把头指针指向下一个结点，然后释放开始的结点。

void SLTPopFront(SLTNode** ppa)
{
	assert(ppa);
	assert(*ppa);
	
	SLTNode* tmp = *ppa;
	*ppa = tmp->next;
	free(tmp);
	tmp = NULL;
}

2.5.2 尾删

尾删道理是相通的，找到尾指针，但也要保留尾指针的前一个指针，因为需要在删除尾指针后，把前一个尾指针的next指向空。

void SLTPopBack(SLTNode** ppa)
{
	assert(ppa);
	assert(*ppa);

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

2.5.3 任意位置删除

意思相近与尾删。

void SLTEraser(SLTNode** ppa, SLTNode* pos)
{
	assert(ppa);
	assert(*ppa);
	if ((*ppa)->next == NULL||pos==*ppa) 
	{
		SLTPopFront(ppa);
	}
	else
	{
		SLTNode* prev = *ppa;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

2.6 单链表的查找及其修改

链表查找就是对应data，然后遍历返回比较简单，修改的话就是根据返回访问data进行赋值修改文章来源地址https://uudwc.com/A/XkDMP

SLTNode* SLTFind(SLTNode* pa, SLTDateType x)
{
	SLTNode* cur = pa;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}