【数据结构】链表详解网站首页 技术教程

【数据结构】链表详解

王笃笃 2023-06-13 16:00:02

简介【数据结构】链表详解

本片要分享的内容是链表，为方便阅读以下为本片目录

1.顺序表的问题及思考

上一篇中讲解了顺序表中增删查改的操作，但是如果在非常庞大的项目中只用顺序表来解决问题局限性还是多了一点，我们不妨想想顺序表是否有以下这些问题

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到
200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

随意要如何解这些问题呢？

1.不需要扩容；

2.按需申请释放空间；

3.解决插入和删除需要挪动数据的问题；

顺序表的根源就是一块数组一样的连续的物理空间，所以我们可以再申请时一个一个的申请一小块空间来储存他的信息，不像顺序表申请空间时申请一大块空间。

所以就可以使用链表来解决这样的问题。

前面的文章中我们题到过顺序表的空间是连续的，通过访问下标就可查找到数据，而单链表的空间是一块一块的不是连续的，所以我们无法通过下标来访问这些数据

所以我们依旧可以通过指针来访问他们的信息。

在链表的下一个空间中存放上一个空间的指针，就像穿串一样将他们全都串联起来；这样就可以访问一个空间的同时也能知道下一个空间的地址。

我们不妨定义结构体来完成链表的操作

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

先简单的对我们想要操作的数据类型重命名，方便以后修改数据类型；

定义一个结构体，为讲解时操作简便只存放了一个数据，同时要存放上一个空间的地址，所以需要使用结构体指针；

接下来对使用链表进行操作；

1.链表的遍历

对单链表内容的遍历展现是非常简单的操作，代码如下：

void SLPrint(SLTNode* phead)
{
	SLTNode* cur = phead;//将phead的内容拷贝一份给cur
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL
");
}

在这里我们先定义一个结构体类型的指针，将phead的内容拷贝一份给cur，就相当于有了两个相同内容的指针；

（方框内的地址只是随机赋值，无其他意义）

接下来就要使用结构体类型的指针去操作内容，cur->指向了结构体的内容便可以访问其内容，再用打印函数将其输出；

也就是说cur->next就是下一个节点的位置，每访问一次下一个节点，他的位置就会被保存到cur中去，循环往复

2.头部插入

头部插入需要主义的是只需要在链表的起始位置做文章即可，代码如下(注意代码有误)

//头部插入
void SLPushFront(SLTNode* phead, SLDatatype x)
{
    //开辟空间
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

    //赋值
	newnode->data = x;
	newnode->next = NULL;

    //链接
	newnode->next = phead;
	phead = newnode;
}

参数有两个，一个是地址，另一个是像添加的数据的内容；

既然是要添加，那必须使用malloc来扩容，同时要给malloc扩容的空间进行判断，分享过很多次这里不再过多赘述；

再通过结构体指针访问结构体内容改变值；

最后的newnode是一个指针变量，通过这个指针变量给next赋值，既然是头部插入所以原先链表的第一个数据就变成了第二个，所以next的值就是原先链表数据的地址。这里不难看出phead就是原先链表中第一个数据的地址，所以将其赋给next；

同时newnode又成为了插入数据后链表的第一个数据，所以又要将newnode的值赋给phead，以便于下一次使用头部插入；

我们将代码使用到main函数中运行一下

我们发现并没有按我们预期的那样输出值

原因是在逻辑上还存在一些问题

SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));

我们发现newnode是一个局部变量，出了作用域后会自动销毁，同样的phead是一个形参，使用后也会被销毁掉，所以无法找到链表的第一个节点，所以我们在运行时还得在main函数中保留一个指针

SLTNode* list = NULL;

来确保链表可以找到第一个节点

那既然在main函数中的局部变量是一个指针

我们不妨从之前的两数交换的函数来入手观察以上代码的问题

我们将两数交换写成代码的形式时会将形式参数写成实参的地址，在函数中解应用从而达到两数交换的功能，由此我们可以得到的结论是想要操作某个内容，就用函数传这个内容的地址。

当我们想要改变指针所指向的内容时，我们发现调用函数无法改变内容，

所以这里还是用上面所说的结论，想要操作某个内容，就用函数传这个内容的地址；

这里我们想要操作两个指针，就要传这个指针的地址，注意是指针的地址，所以我们必须使用二级指针来解决问题。

以下为正确代码

void SLPushFront(SLTNode** pphead, SLDatatype x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;


	newnode->next = *pphead;
	*pphead = newnode;
}

这样我们再带入到主函数中使用我们所写的函数

这样就可以达到我们预期中的效果了

2.1开辟空间函数分装

我们发现在之前所写的代码中都需要使用malloc开辟空间、判断开辟成功、最后将节点置空这些操作，所以我们不妨将这些操作总写成一个函数以便于我们使用

SLTNode* BuyLTNode(SLDatatype x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
}

可以看到在这个函数中有开辟空间，检查空间，将空间置空的操作，在接下来的插入操作中我们使用以上函数；

3.尾部插入

尾部插入相对头部插入相对有一点麻烦，因为需要找上一个节点的尾巴，在理解上可能会有一些难度，代码如下（以下代码有误）

void SLPuchBack(SLTNode* phead, SLDatatype x)
{
	SLTNode* tail = phead;
	while (tail->next != NULL)
	{
		tail = tail->next;

	}
	SLTNode* newnode = BuyLTNode(x);
	tail->next = newnode;
}

首先我们要再定义一个结构体变量的指针，将phead的值赋给tail，我们只需要操作tail就等于操作了phead；

接下来我们需要查找整个链表的尾部，所以可以看到以上代码的判断条件，当tail中的next变量不为空时，tail就指向下一个节点，也就是说next为空时，循环就结束；

在接下来再重新创建一个结构体指针newnode，他是我们尾插所要存放数据的空间，我们使用BuyLTNode函数对他进行初始化；

因为newnode是一个新的结构体指针，next也是我们最初所创建的结构体指针，所以最后将newnode结构体指针再赋给tail中的next即可，这样就将新的空间和之前尾部的空间连接起来；

要注意的是我们想要和链表中的上一个节点和下一个节点形成链接的时候，就必须要操作结构体指针变量中的next，因为next也是结构体指针变量，他存放的是的下一个节点的地址，这样才能和下一个节点连接起来。

纠正

我们还需要考虑的一点就是当这个链表一开始就没有数据该怎么办呢？很显然上面的代码没有考虑到这种情况；当链表为空的时候，以上代码就不能插入数据了；

我们会发现程序会崩溃掉

所以我们继续来解决这种情况

我们发现plist是一个指针变量，还是之前所说过的，我们想要改变数据，就操作这个数据的地址；

很显然我们传参传的是指针的地址，所以我们就要操作指针的地址，所以在编写函数时就要使用二级指针来操作指针的地址；

代码如下

//尾部插入
void SLPuchBack(SLTNode** pphead, SLDatatype x)
{
	SLTNode* newnode = BuyLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;

		}
		tail->next = newnode;
	}
}

这次我们考虑的情况是如果链表中一个数据都没有时，我们就需要先申请一个空间来存放我们的数据，如以上代码的if语句所示；

接下来如果不是空链表就依旧按照原来的代码进行插入然后链接，应该不难看懂；

这里还需要注意的是我们只有在第一次，也就是链表中为空时运用了二级指针来添加第一块空间，后面的添加都只需要操作指针中的next指针即可，当链表为空时也就只使用一次二级指针，再向后添加数据时都是用一级指针；

4.尾部删除

删除操作要注意的还是两个指针的问题，从如果操作不当可能就会出现野指针从而使程序报错；

我们先观察以下错误的写法

void SLPopBack(SLTNode** pphead, SLDatatype x)
{
	SLTNode* tail = *pphead;
	while (tail->next !=NULL)
	{
		tail = tail->next;
	}
	free(tail);
	tail = NULL;
}

这串代码代码看上去没什么问题，判断，free释放基本上没什么问题

但是要深入研究就会发现和正常的代码简直就是天差地别；

之前说到过删除就是将这个节点置空即可，但是我们要注意，当我们将节点置空的时候，指向这个节点的指针就会成为一个野指针，所以我们要想办法规避野指针。

我们不妨再创建一个指针变量prev

SLTNode* prev = NULL;

我们可以再上面看到tail = tail->next;这串代码的意思就是让tail存放下一个指针的地址，所以我们不妨让prev来存放tail，让tail每走一步就让prev存放一次tail的值

tail和prev一前一后，tail每走一步就让prev存放一次tail的值；

当tail是我们想要删除的数据时我们就可以让prev中的next置空，从而达到删除的效果，也规避了上述野指针的出现。

但是还要注意的是如果链表中只有一个数据该怎么办呢？链表为空该怎么办呢？只有一个节点我们就无法找到前一个节点的next并将其置空；所以我们还是用判断条件和二级指针来解决问题。

那代码如下

//尾部删除
void SLPopBack(SLTNode** pphead)
{
	//暴力检查指针是否为空
	assert(*pphead); 

	//判断是否只有一个数据
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//判断多个数据 
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}

}

我们可以带到主函数中应用

可以看到末尾的4被删除掉了

我们再试试链表中没有数据的情况下

可以看到指向链表中第一个数据的指针为空时，assert断言就发挥了作用，程序出现错误。

5.头部删除

同样的删除还需要添加上对空链表的判断和链表中是否只有一个数据的判断；

具体代码如下

//头部删除
void SLPopFront(SLTNode** pphead)
{
	//暴力检查指针是否为空
	assert(*pphead);

	//判断是否只有一个数据
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//判断多个数据 
	else
	{
		SLTNode* del = *pphead;
		*pphead = del->next;
		free(del);
	}
}

判断多个数据的时候我们只需要在创建一个新的结构体变量将*pphead保存，也就是将plist保存，然后将下一个节点的地址赋值给*pphead，让下一个节点成为最开始的节点，最后再释放掉没有操作前的del即可完成头部删除的操作；

6.数据查找

链表数据的查找不算太难，我们只需要遍历链表中的数据即可

//数据查找
SLTNode* SLTFind(SLTNode* phead, SLDatatype x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL; 
}

重新定义一个结构体指针cur，将phead的值赋给cur，我们对cur操作即可；

利用while循环对结构体进行遍历，如果结构体中data等于我们想要找的数x，返回x即可；

找不到就返回空；

当我们要在主函数中使用它时要注意他的返回类型是一个指针类型，所以要在主函数中定义一个指针类型来接受它；

既然是找到了这个数并且返回了他的指针，那么我可以通过这个函数对他的值进行修改（如上图），

运行的效果如下

可以看到我们将3查找到后将3改成了30；

7.任意位置插入

这里需要和顺序表中插入保持一致，需要在输入的数前一个位置插入；

同样我们还要使用assert来断言pos的位置和phead位置是否为空；

具体代码如下

//任意位置插入
void SLInsert(SLTNode** pphead, SLTNode* pos,SLDatatype x)
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLPuchBack(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}


		SLTNode* newnode= BuyLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

当我们想要插入数字的位置等于链表起始位置的时候，我们就尾插来实现插入数据；

其他的情况时我们需要重新定义一个结构体指针将plist的地址拷贝给新定义的指针；

接下来就都使用插入时的常规操作，通过条件判断能否使prev和下一个结点进行连接；

最后就是将指针的内容交换，实现链表中添加数据的操作