【数据结构】单链表（一）

上一篇【数据结构】顺序表-CSDN博客  我们了解了顺序表，但是呢顺序表涉及到了一些问题，比如，中间/头部的插入/删除，时间复杂度为O(N);增容申请空间、拷贝、释放旧空间会有不小的消耗；增容所浪费的空间... 我们如何去解决这些问题？本篇介绍另一个数据结构——链表

1. 链表的概念及结构

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

链表大概是什么样的呢？看下图

链表是由一个一个的节点组成，再顺序表中，数据是连续存放的，我们想找到下一个数据顺着前一个数据找就行了，而链表中数据存放空间是不连续的，所以我们就需要一个指针来保存下一个节点的地址，所以，我们如果要定义链表，只需要定义链表的节点结构就行了

(在【C语言】结构体详解-CSDN博客 的1.3 结构体的自引用 中介绍过)

struct SListNode
{
	int data;//数据
	struct SListNode* next;//下一个数据的地址
};

和上一篇一样，创建一个头文件，两个源文件

 也是一样，在头文件SList.h中定义单链表的结构，并对类型和结构体改名

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int Type; 
//定义节点结构
typedef struct SListNode
{
	Type data;
	struct SListNode* next;
}SLNode;

我们先创建几个节点，在test.c中实现

#include "SList.h" //包含头文件
void SListtest1()
{
	SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));//创建节点1
	node1->data = 1;//赋值
 
	SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));//创建节点2
	node2->data = 2;//赋值
 
	SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));//创建节点3
	node3->data = 3;//赋值
 
	SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));//创建节点4
	node4->data = 4;//赋值
}
int main()
{
	SListtest1();
	return 0;
}

虽然我们创建好了节点，但是这几个节点现在还不能互相找到，所以我们接下来要将这几个节点连接起来，怎么连接？存下一个节点的地址

void SListtest1()
{
	SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));//创建节点1
	node1->data = 1;//赋值
	SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));//创建节点2
	node2->data = 2;//赋值
	SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));//创建节点3
	node3->data = 3;//赋值
	SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));//创建节点4
	node4->data = 4;//赋值
	//将四个节点连接起来
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
}

现在就构成了一个链表，有了这个简单的链表，我们来写一个函数打印一下里面的数据

链表的打印

在SList.h中进行函数的声明

void SLPrint(SLNode* ps);//打印

参数是链表的节点的地址 

在SList.c中进行函数的实现

#include "SList.h"
void SLPrint(SLNode* ps) //打印
{
	SLNode* pcur = ps;//pcur指向当前链表的第一个节点
}

要打印当然就要循环遍历，写一个while循环，判断条件为pcur，不为NULL进入循环 

void SLPrint(SLNode* ps) //打印
{
	SLNode* pcur = ps;//pcur指向当前链表的第一个节点
	while (pcur) //判断第一个节点是否为NULL
	{
     //....
	}
}

 进入循环后打印内容

void SLPrint(SLNode* ps) //打印
{
	SLNode* pcur = ps;//pcur指向当前链表的第一个节点
	while (pcur)
	{
		printf("%d->", pcur->data);//打印内容
	}
}

打印完一个数据后，要把下一个节点值部分的地址给pcur ，也就是pcur要存node2中2的地址，此时pcur不再指向node1，指向了node2

void SLPrint(SLNode* ps) //打印
{
	SLNode* pcur = ps;//pcur指向当前链表的第一个节点
	while (pcur)
	{
		printf("%d->", pcur->data);//打印内容
		pcur = pcur->next;//指向下一个节点
	}
	printf("NULL\n");
}

在test.c中测试

测试时我们不直接传链表的第一个节点node1，而是再定义一个结构体指针plist去指向node1，让plist作为参数传过去

    SLNode* plist = node1;
	SLPrint(plist);

虽然有点多此一举，但这样会让我们的代码更完善 

运行结果

 2.链表的插入

实际使用链表的时候我们不会像上面那样一个一个创建，初始时候是一个空链表，会跟顺序表类似进行空间开辟然后插入数据

2.1空间申请创建节点

插入数据前依旧是要判断空间够不够

在SList.h中进行函数的声明

SLNode* SLBuyNode(Type x);//申请空间创建节点

返回值是节点的地址，参数就是要插入的数据

在SList.c中进行函数的实现

SLNode* SLBuyNode(Type x)//申请空间创建节点
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL) //空间申请失败
	{
		perror("malloc");
		return 1;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

2.2 尾插

在SList.h中进行函数的声明

void SLPushBack(SLNode** ps, Type x);//尾插

参数是链表的节点地址，是一个二级指针，和要插入的数据

我们要给函数传地址，这样形参的改变才能影响实参，对参数的理解如下，这很重要，这里提前展示将要在test.c中测试用的部分代码 

在SList.c中进行函数的实现

尾插要先找到尾节点，再将尾节点和新节点连接起来 ，此时node4的地址部分就不再是NULL 而是新节点的地址

代码如何实现呢 ？先找尾节点

void SLPushBack(SLNode* ps, Type x)//尾插
{
	SLNode* ptail = ps;//定义尾节点，开始时指向头节点
	while (ptail->next != NULL)//遍历链表数据，找尾节点
	{
		ptail = ptail->next;
	}
	//跳出循环后ptail指向尾节点
}

然后我们直接调用创建节点的函数，放在找尾节点前面，最后赋值

void SLPushBack(SLNode* ps, Type x)//尾插
{
	SLNode* newnode = SLBuyNode(x);//申请空间创建节点
	SLNode* ptail = ps;//定义尾节点，开始时指向头节点
	while (ptail->next != NULL)//遍历链表数据，找尾节点
	{
		ptail = ptail->next;
	}
	//跳出循环后ptail指向尾节点
	ptail->next = newnode;//直接赋值
}

 但是呢，链表在没有赋值的时候是空链表，所以我们要讨论空链表的情况，如果是空链表，直接让ps指向新节点newnode，所以最终的代码如下

void SLPushBack(SLNode** pps, Type x)//尾插
{
	assert(pps);//pps不可以为NULL
	SLNode* newnode = SLBuyNode(x);//申请空间创建节点
	if (*pps == NULL) //*pps可以为NULL，表示空链表
	{
		*pps = newnode;
	}
	else //非空链表
	{
		SLNode* ptail = *pps;//定义尾节点，开始时指向头节点
		while (ptail->next)//遍历链表数据，找尾节点
		{
			ptail = ptail->next;
		}
		//跳出循环后ptail指向尾节点
		ptail->next = newnode;//直接赋值
	}
}

我们再来看test.c中测试的代码

void SListtest2()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLPrint(plist);//打印
}
int main()
{
	//SListtest1();
	SListtest2();
	return 0;
}

多插入几个数据，运行看结果，插入成功

2.3 头插

 在SList.h中进行函数的声明

void SLPushHead(SLNode** pps, Type x);//头插

同样的，参数也是一个二级指针，还有要插入的数据

在SList.c中进行函数的实现

我们需要做两件事，一个是将newnode和原本的首节点连接在一起，另一件事是*pps要指向新的首节点 

 链表不为NULL时，代码如下

void SLPushHead(SLNode** pps, Type x)//头插
{
	assert(pps);//pps不能为NULL
	SLNode* newnode = SLBuyNode(x);//申请空间创建节点
	newnode->next = *pps;
	*pps = newnode;
}

当链表为NULL时，分析一下

当前代码也可以实现

在test.c中测试

void SListtest2()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLPrint(plist);//打印
	SLPushHead(&plist, 6);//头插
	SLPushHead(&plist, 7);
	SLPushHead(&plist, 8);
	SLPrint(plist);//打印
}

看一下运行结果

3.链表的删除

删除数据，链表就不能为空，不然删啥呢?

 3.1 尾删

在SList.h中进行函数的声明

void SLPopBack(SLNode** pps);//尾删

在SList.c中进行函数的实现

很显然，首先就是找尾节点，找到尾节点之后直接释放吗？node4释放后node3->next里面依然存放着node4的地址，但此时指向的空间已经没了，此时的指针就成了一个野指针 ，所以我们还要将被释放节点的前一个节点的指针置空

所以我们还要找尾节点的前一个节点

void SLPopBack(SLNode** pps)//尾删
{
	assert(pps && *pps);//pps和链表都不能为空
	SLNode* prev = *pps;//定义尾节点前一个节点
	SLNode* ptail = *pps;//定义尾节点
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	//此时找到了尾节点和尾节点前一个节点
	free(ptail);//释放尾节点
	ptail = NULL;//置空
	prev->next = NULL;//置空尾节点前一个节点
}

如果这个链表只有一个节点呢，这个代码可行吗？来分析一下

我们把节点释放并置空后，prev->next就不存在了，函数最后一句代码就不能实现，所以，当链表里只有一个节点时，直接释放就行了

void SLPopBack(SLNode** pps)//尾删
{
	assert(pps && *pps);//pps和链表都不能为空
	if ((*pps)->next == NULL)//链表只有一个节点
	{
		free(*pps);//释放节点
		*pps = NULL;//置空
	}
	else //链表不止一个节点
	{
		SLNode* prev = *pps;//定义尾节点前一个节点
		SLNode* ptail = *pps;//定义尾节点
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//此时找到了尾节点和尾节点前一个节点
		free(ptail);//释放尾节点
		ptail = NULL;//置空
		prev->next = NULL;//置空尾节点前一个节点
	}
}

在test.c中测试

void SListtest2()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPrint(plist);//打印
	SLPushHead(&plist, 6);//头插
	SLPushHead(&plist, 7);
	SLPrint(plist);//打印
	SLPopBack(&plist);//尾删
	SLPrint(plist);//打印
}

看下结果，尾删成功

3.2 头删

在SList.h中进行函数的声明

void SLPopHead(SLNode** pps);//头删

在SList.c中进行函数的实现

我们要删除头节点，跟删除尾节点不一样，如果我们把首节点释放掉，还能找到首节点里的next吗？不能，不能的话就找不到第二个节点以及剩下的节点

我们应该先把下一个节点的信息存储起来

SLNode* Next = (*pps)->next;//存节点

 然后把原头节点释放

free(*pps);

最后让*pps指向新的头节点

*pps = Next;

所以代码如下

void SLPopHead(SLNode** pps)//头删
{
	assert(pps && *pps);//pps和链表都不能为空
	SLNode* Next = (*pps)->next;//存节点
	free(*pps);
	*pps = Next;
}

当链表只有一个节点时，分析一下，上面的代码也是可以完成的

我们在test.c中测试一下

void SListtest2()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPrint(plist);//打印
	SLPushHead(&plist, 6);//头插
	SLPushHead(&plist, 7);
	SLPrint(plist);//打印
	SLPopBack(&plist);//尾删
	SLPrint(plist);//打印
	SLPopHead(&plist);//头删
	SLPrint(plist);//打印
}

下篇我们再继续介绍更多内容，拜拜~