数据结构·单链表

时间：2024-03-07 19:48:04

目录

1 链表简介

2 链表基本概念

3 链表的打印

4 创建一个结点

5 链表的头/尾插

6 链表的头/尾删

7 链表的查找

8 链表的指定位置前/后插入数据

9 删除pos（之后）的结点

10 销毁链表

前言：

学习单链表前，我们已经学习完了顺序表，线性表包括顺序表，链表等，按照顺序，我们今天就来学习链表，链表分为几大类，单向还是双向，带头还是不带头，循环还是不循环，所以链表一共有8种，最简单的是不带头单向不循环链表，难度较大的是带头双向循环链表，今天学习不带头单向不循环链表，学习了最简单的和最难的，中间难度的也就易如反掌了。

1 链表简介

链表链表，像链条一样把东西串起来，比如火车，每个车厢都是用链条连接起来的，在计算机中，顺序表以数组为基础，每个数据类型都是挨着的，也就是内存中的分布的紧凑的，链表就不一样了，每个数据类型所在的内存空间不一定是挨着的，因为前一个数据存储了下一个数据的地址。

那为什么要学习链表呢？链表相对于顺序表的优点在哪里呢？

顺序表存储的数据量大的时候，不免涉及到移动数据，数据一多，移动次数就多，浪费的时间越多，链表不一样，因为链表的数据是一个一个串联起来的，插入数据只需要连接就行，不存在移动数据的时间。

顺序表开辟空间常常以2倍开辟的，一般都会造成空间的浪费，链表不同，链表不会额外的申请空间，链表每插入一个元素就会申请那一个元素的空间，再插入到指定位置就行了。

2 链表基本概念

链表的每一个数据称为”结点“，可以是”结点“，也可以是”节点“，说法不一，意思一样，因为是串起来的，所以每个数据就是结点，如何通过一个个的结点找到下一个数据呢？

每个结点存储的数据占一定的空间，下一个数据的地址又占一定的空间，也就是说，结点的本质是结构体，一个成员变量（数据域）用来存储数据，一个成员变量（指针域）用来存储下一个结点的地址，这样就达到了链式访问的目的。

typedef struct SList
{
	int data;//结点数据
	struct SList* next;//下一个结点的地址
}SLTNode;
int main()
{
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	return 0;
}

这样，也就算是手动创建了一个链表，一般设链表的最后一个元素是NULL，作为结束标志，但是这样太麻烦了，我们一般不这样创建链表，这里是为了演示一下。

重命名也有一个小坑，重命名结构体为SLTNode，那么next的前面是不能写SLTnode的，因为重命名是在结构体创建完之后才重命名的，系统识别的时候会发现SLTNode未定义，就会报错。

typedef int DataType;

typedef struct SList
{
	DataType data;//结点数据
	struct SList* next;//下一个结点的地址
}SLTNode;

3 链表的打印

打印都是比较简单的，while循环遍历一下就打印出来了，结束的标志就是最后的NULL，

void SLTPrint(SLTNode* phead)//打印
{
	assert(phead);
	SLTNode* tem = phead;
	while (tem)
	{
		printf("%d->",tem->data);
		tem = tem->next;
	}
	printf("NULL\n");
}

打印完一个结点的数据之后，结点就应该移动到下一个结点的位置，所以有tem = tem->next，

那么为什么使用一个临时变量呢？因为链表的操作很多，我们为了下一个操作的方便使用，就使用临时变量，防止头结点发生改变。

4 创建一个结点

我们后续操作，如头插尾插，指定位置插入，都需要单独创建一个结点，那么我们不妨单独用一个函数创建一个结点：


SLTNode* SLTCreate(DataType x)//创建一个结点
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	assert(node);
	node->data = x;
	node->next = NULL;
	return node;
}

 值得注意的是链表的操作涉及大量的指针和结构体，访问结构体数据用到的都是指针，记住哦，都是指针哦（划重点）。

5 链表的头/尾插

上文写到创建链表的方式不用那么麻烦，因为我们只需要创建一个头结点，剩下的交给数据插入函数就行了。

头插函数，不同于顺序表移动数据，我们只需要让插入的数据的指针域指向最初的头结点就行。

void SLTPushHead(SLTNode** pphead, DataType x)//头插
{
	assert(pphead);
	SLTNode* newnode = SLTCreate(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

断言是必不可少的，我们使用的是二级指针，因为访问结构体的都是一级指针，为了修改真正的链表，就使用了二级指针，传参的时候也要记得传地址过去，连接好了之后也不要忘了头结点易主了，*pphead = newnode，更换头结点。

尾插函数，把数据接在链表的最后面，也就是原本next是NULL的数据的指针域连接到新节点，新结点的指针域连接到NULL就好了。

void SLTPushBack(SLTNode** pphead, DataType x)//尾插
{
	assert(pphead);
	SLTNode* newnode = SLTCreate(x);
	SLTNode* tem = *pphead;
	//链表为空
	if (tem->next == NULL)
	{
		*pphead = newnode;
		return;
	}
	//链表不为空
	while (tem->next)//找尾节点
	{
		tem = tem->next;
	}
	tem->next = newnode;
}

尾插的时候我们要考虑链表是否为空的情况，如果链表为空，就相当于头结点变为新的结点，如果链表不为空，就需要去找到尾结点，一个while就诞生了，找到尾节点之后进行连接，就完成了。

6 链表的头/尾删

头部删除，无非就是让第二个结点变成头结点，最初的头结点释放了就行：

void SLTPopHead(SLTNode** pphead)//头删
{
	assert(pphead);
	assert(*pphead);
	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = newhead;
}

这里考虑是否存在头结点的问题，没有头结点也就不存在删除头结点。

尾删操作，就是让倒数第二个结点的next指向NULL，然后释放掉最初的尾部结点就行，所以我们需要先找尾结点，同样需要判断头结点是否存在：

void SLTPopBack(SLTNode** pphead)//尾删
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		*pphead = NULL;
		return;
	}
	SLTNode* tem = *pphead;
	SLTNode* newback = NULL;
	while (tem->next)
	{
		newback = tem;
		tem = tem->next;
	}
	free(tem);
	newback->next = tem = NULL;
}

如果只有一个头结点，那么尾删就相当于头删，给头结点置为空就行了，然后就是寻找尾结点和倒数第二个结点了，找两个结点一个while就可以搞定，找到后释放，置为空，next置为空，尾删操作就算完成了。

7 链表的查找

查找我们利用的是存储的数据进行查找的，不同于顺序表有类似于下标的存在，链表只能返回一个指针用于访问查找的这个结点，所以返回值应是指针类型，找到了就返回结点，没找到就返回NULL：

SLTNode* SLTFind(SLTNode** pphead, DataType x)//查找
{
	assert(pphead);
	SLTNode* tem = *pphead;
	while (tem)
	{
		if (tem->data == x)
		{
			return tem;
		}
		tem = tem->next;
	}
	return NULL;
}

8 链表的指定位置前/后插入数据

指定位置前面插入数据，需要涉及到三个结点，指定位置的结点，指定位置之前的结点，插入的结点，为了找到指定位置之前的结点，我们就需要头结点，那么连接起来，就是指定位置之前的结点的next指向插入结点，插入结点的next指向指定位置结点：

void SLTInsert(SLTNode** pphead, SLTNode* pos, DataType x)//指定位置之前插入数据
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//pos是头结点
	if (pos->next == NULL)
	{
		SLTPushHead(pphead,x);
		return;
	}
	//pos不是头结点
	SLTNode* newnode = SLTCreate(x);
	assert(newnode);
	SLTNode* tem = *pphead;
	while (tem->next != pos)
	{
		tem = tem->next;
	}
	newnode->next = pos;
	tem->next = newnode;
}

如果pos是头结点的话，那么可以直接调用头插函数，就不用多写代码了，不是头结点的话就遍历整个链表，找到pos之前的那个结点，三个结点进行两两连接就行了。

指定位置之后插入数据，涉及到的同样是三个结点，指定位置的结点，插入结点，指定位置之后的结点，但是这里不用头结点，指定位置之前插入数据需要头结点是因为这个链表不是双向的，需要比前结点更往前的结点，这里已经有了指定位置的结点，所以之后的所有结点都可以访问了，找到结点，两两连接就行了：

void SLTInsertAfter(SLTNode* pos, DataType x)//指定位置之后插入数据
{
	assert(pos);
	SLTNode* newnode = SLTCreate(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

9 删除pos（之后）的结点

删除pos结点，如果是头结点，直接进行头删,其他情况就是删除之后再进行两两连接就行了：

void SLTDelete(SLTNode** pphead, SLTNode* pos)//指定位置删除数据
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (pos->next == NULL)
	{
		SLTPopHead(pphead);
		return;
	}
	SLTNode* tem = *pphead;
	while (tem->next != pos)
	{
		tem = tem->next;
	}
	tem->next = pos->next;
	free(pos);
	pos = NULL;
}

先判断是不是头结点，是头删 返回，不是就找pos之前的结点，找到了连接pos之后的结点就行，然后释放掉pos结点并且给上一个NULL。

删除pos之后的结点，同上，参数不需要头结点了，只需要一个pos就可以解决：

void SLTDeleteAfter(SLTNode* pos)//指定位置之后删除数据
{
	assert(pos);
	assert(pos->next);
	SLTNode* tem = pos->next;
	pos->next = pos->next->next;
	free(tem);
	tem = NULL;
}

既然是删除pos之后的数据，那么pos->next就不能为空，所以加断言，然后创建一个临时变量，用来释放pos->next空间的，如果直接用pos->next进行释放，指针域的赋值就会不成立，释放空间之后再置为空就行了。

10 销毁链表

销毁链表就是让头结点为空，并且释放每一个空间，这样就就销毁了：

void SLTDestroy(SLTNode** pphead)//销毁
{
	assert(pphead);
	SLTNode* tem = *pphead;
	while (tem)
	{
		SLTNode* next = tem->next;
		free(tem);
		tem = next;
	}
	*pphead = NULL;
}

创建临时变量的原因依然是为了方便释放空间，最后头结点置为NULL，销毁就完成了。

感谢阅读！

相关文章