前面向大家介绍了顺序表以及它的实现，今天我们再来向大家介绍链表中的单链表。

1.链表的概念和结构

1.1 链表的概念

链表是一种在物理结构上非连续，非顺序的一种存储结构。链表中的数据的逻辑结构是由链表中的指针链接起来的。

1.2 链表的结构

链表的结构与火车相似。

火车是由一节一节的车厢构成的，并且各个车厢之间是相互独立的，且每个车厢都有属于自己的锁。假设火车上车厢的门都是锁上的状态，每个门都要对应的锁来开门，那我们如何快速的从第一个车厢走到最后一个车箱呢？

答案很简单，我们只要把下一节的车厢的钥匙放在上一节车厢就行了。

链表也是如此，车厢对应到链表中就是节点。

所以链表是由一个个节点组成的，每个节点由存储的数据和指向下一个节点的指针组成的。

为什么需要指针呢？

因为链表在物理结构上是不连续的，由于连表中的节点的地址是由计算机随机分配的，我们并不能清楚的知道各个节点的具体位置，这时候就需要指针了。通过指针我们就能知道每个节点的位置。

上图就是一个单链表的结构，plist是一个指向第一个节点的指针，往后看会发现，每一个节点都会包含了下一个节点的指针。

2.单链表的实现 

单链表的实现，我们依然通过三个文件来实现，为SList.h，SList.c和test.c

2.1 单链表的创建

我们通过前面顺序表就可以很快写出以下代码

typedef int SLDataType;
struct SListNode
{
	SLDataType data;
	struct SListNode* next;
}SList;

2.2 单链表的初始化

链表是由一个一个的节点组成的，所以我们要为节点申请空间，会用到malloc函数。

void test01()
{
	//手动初始化
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 1;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 1;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 1;
	
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	SLTNode* plist = node1;
}

为了方便观察，我们先写一个打印链表的函数。

SLPrint(SLTNode* phead)
{
	SLTNode* pur = phead;
	while (pur)
	{
		printf("%d->", pur->data);
		pur = pur->next;
	}
	printf("NULL\n");
}

解释以上代码

pur是一个指向第一个节点的指针，我们知道最后一个节点中的指针为NULL，pur在不断的变换为next的值，直到pur的值为NULL就跳出循环。

运行代码

我们就发现单链表初始化成功了。

但是上面的代码是我们动手来实现链表的初始化的，但这样写代码的效率就会降低，我们一般都会通过函数来实现，这就涉及到了链表数据的插入。

2.3 数据的插入

数据的插入方式我们分为尾插和头插的两种。

2.3.1 尾插

尾插，顾名思义就是从链表中的尾部插入一个新的节点。

上图就是尾插的形式。

思路分析

既然我们要插入一个新的节点，我们就要为新的节点申请空间，为了方便，我们同样把申请空间的操作包装成一个函数。

//申请空间
SLTNode* SLBuySpace(SLDataType x)
{
	SLTNode* new = (SLTNode*)malloc(sizeof(SLTNode));
	//判断空间是否申请成功
	if (new == NULL)
	{
		perror("malloc fail");
		exit(1);//退出程序
	}
	//到这空间申请成功
	new->data = x;
	new->next = NULL;
	return new;
}

接着，既然要实现尾插，我们就要找到链表的尾巴，然后才能插上新的节点。

//找尾巴
SLTNode* ptail = *pphead;
while (ptail->next)
{
	ptail = ptail->next;
}
ptail->next = newnode;

尾插的总代码

//尾插
void SLPushBack(SLTNode** pphead, SLDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLBuySpace(x);
	if (*pphead == NULL)
	{
		//链表为空
		*pphead = newnode;
	}
	else
	{
		//链表不为空
		//找尾巴
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
	

}

需要注意的是，我们这里的形参是一个二级指针，因为我们要将原来phead指针指向的内容进行改变，如果我们单独将指针的值传过来，通过前面的学习，我们传值时，形参的改变是不会影响实参的，所以我们要将指针的地址传过来，通过地址修改实参的值。 

运行代码

还需注意的是，我们要将链表为空和不为空分为两种情况处理，如果我们只考虑到链表不为空的情况，则当我们一开始处理的链表为空时，就不会进入循环，为空，ptial->next就无法进行解引用。 

2.3.1 头插 

头插，也就是将一个新的节点插入链表的头部，使新的节点称为第一个节点。

代码实现

//头插
void SLPushHead(SLTNode** pphead, SLDataType x)
{
	assert(pphead);
	//为新节点申请空间
	SLTNode* newnode = SLBuySpace(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头插的代码很简单，但是最后要让newnode成为新的phead，不要漏掉*pphead=newnode。

运行代码

2.4 数据的删除

2.4.1  尾删

尾删就是将链表中的最后一个节点删除掉。

思路分析

尾删我们就要找到链表的尾巴，并将其释放掉，但注意的是，当我们将最后一个节点释放掉之后，前一个节点中的next就会变成野指针，所以我们也要找到最后一个节点的前一个节点，并将其next指针赋值为NULL。

尾删前如下图

尾删后如下图

代码实现

void SLPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//链表不能为空
	SLTNode* prev = *pphead;
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	//这里，prev和ptail找到
	free(ptail);
	prev->next = NULL;
}

运行代码

2.4.2 头删

 头删就是将链表中的第一个节点删点。

代码实现

//头删
void SLPopHead(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;//将下个节点变为新的节点
}

我们需要把下一个节点变为新的头节点，所以我们创建一个next先将下一个节点的地址存储起来。 

2.5 查找数据

查找数据很简单，只需遍历链表，并返回存储要查询数据节点的地址，如没由，就返回NULL。

代码实现

SLTNode* SLDataFind(SLTNode* phead, SLDataType x)
{
	assert(phead);
	SLTNode* pcur = phead;
    //遍历链表
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

运行代码

2.6  在指定位置之前插入数据

在指定位置之前插入数据，会影响到插入数据前一个节点的·指针，所以我们要找到插入位置的前一个节点。如下图

代码实现

void SLAddPos(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	assert(pphead);
	assert(pos);
	SLTNode* newnode = SLBuySpace(x);
	if (*pphead == pos)
	{
		//链表为空
		//头插
		SLPushHead(pphead, x);
	}
	else
	{
		//链表不为空
		//找位置pos前面的节点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}	
}

2.7 在指定位置之后插入数据 

 在指定位置之后插入数据就很简单，这个操作会影响插入位置的后一个指针，因为我们可以通过插入位置来找到插入位置的后一个节点，不在需要遍历链表。

我们只需将pos->next指向newnode，让newnode->next指向pos->next。

代码实现

void SLAddBack(SLTNode* pos, SLDataType x)
{
	assert(pos);
	//为插入节点申请空间
	SLTNode* newnode = SLBuySpace(x);
	SLTNode* next = pos->next;
	pos->next = newnode;
	newnode->next = next;
}

这里我们要先将pos->next保存下来，因为后面的pos->next会发生改变，而我们要让newnode->next指向原来的pos->next;

2.8 删除pos节点的数据 

当我们删除pos节点时，会影响到pos前后两个节点的指针，所以，我们首先要找到pos前后的两个节点。

代码实现

void SLErasePos(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		//只有一个节点
		//头删
		SLPopHead(pphead);
	}
	else
	{
		SLTNode* next = pos->next;
		//找prev
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		free(pos);
		pos = NULL;
		prev->next = next;
	}

}

注意事项：我们要先将pos->next的值先存储起来，因为前面的pos就会被释放掉了，最后就找不到pos->next了。

我们还要分情况讨论，当链表中只有一个节点时，那就是头删操作了，直接调用头删的函数就行了。

运行代码

2.9 删除pos后的节点

思路分析

既然要删除pos后的节点，首先链表就不能为空，pos->next也不能为空。

注意，将pos后面的节点释放掉了之后，此时pos->next就是野指针来，要注意将pos->next置为空。

代码实现

void SLEraseAfter(SLTNode* pos) //pos->data==1
{
	assert(pos && pos->next);
	//要删除的节点
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

2.10 销毁链表

销毁链表就一个一个销毁就行了。

代码实现

void SLBreak(SLTNode** pphead)
{
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

感谢观看。