链表（一）----关于单链表的一切细节这里都有

一.链表

1 链表的概念及结构

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

• 现实中的链表结构
  

• 数据结构中的链表结构
  

1.链式结构在逻辑上是连续的，但在物理上不一定是连续的。
2.现实中的节点一般是在堆上申请出来的。
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，可能不连续。

---

链表的分类

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

二.实现单向链表

记住这个图，一会链表的逻辑会用到

我们创建三个文件：
头文件LList.h用于调用库函数、声明结构体和函数。
源文件LList.c存储函数。
源文件text.c进行测试。
每个源文件都必须包含LList.h。

---

1.声明链表结构体

//以下声明在头文件LList.h当中
#include 
#include 
#include 
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType val;
	struct SListNode* next;
}SLNode;
1
2
3
4
5
6
7
8
9
10

---

2.打印链表

声明

void SLTPrint(SLNode* phead);
1

SList.c

void SLTPrint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	 {
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10

---

3.创建新节点

当我们进行插入节点等一系列操作时，都需要创建新的节点，用到这个函数

声明

SLNode* SLCreateNode(SLNDataType x);
1

SList.c

 SLNode* CreateNode(SLNDataType x)
 {
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode = NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
 }
1
2
3
4
5
6
7
8
9
10
11
12

• 为新节点开辟空间，返回值为新节点的地址，所以函数类型为 SLNode* 结构体指针类型。
• malloc函数为newnode开辟结构体大小个字节。
• 判断是否开辟成功，失败则打印错误信息，结束函数运行。
• 将新节点的数据val赋值为传入参数 x。
• next赋值为空。

---

4.尾插

如果参数为一级指针，尾插传值只是临时拷贝，必须传地址

• 声明

void SLTPushBack(SLNode** phead, SLNDataType x);
1

对结构体指针修改，要传地址，用二级指针接收
我们第一反应可能想当然敲出这样的经典错误：

• 尾插的本质是上一个节点存下一个节点的地址
• 而这里的tail是局部变量，出了作用域还会销毁，存在newnode内存泄漏的问题
• tail和新节点确实在此刻取得了联系，但是并没有和上一个节点链接起来哦

---

• SList.c

void SLTPushBack (SLNode ** pphead ,SLNDataType x)
{
	SLNode* newnode = CreateNode(x);
   //没有节点的情况
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else//有节点的情况
	{
		//找尾
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• assert判断传入头节点指针的地址是否合法，为空则报错。
• 为新节点newnode开辟空间并将x储存其中。
• 插入时分两种情况：空链表 非空链表

1. 如果链表为空则直接将*pphead 指向新节点 newnode，使其成为新的链表的头节点。
2. 如果链表不为空，则创建变量tail指向头结点，循环遍历链表使tail指向尾节点，将新节点地址赋值给tail的next，成功将新节点添加到链表尾部。
   
   plist、pphead和newnode的新空间关系如下

• plist和phead都是在函数栈帧里面开辟的
• newnode是借助于malloc在堆上开辟的，是一个结构体指针，在开辟时数值域上放的其实就是尾插函数的第二个参数
  

---

5.头插

• 声明

void SLTPushFront(SLNode** pphead, SLNDataType x);
1

• SList.c

void SLTPushFront(SLNode** pphead, SLNDataType x)
{
	SLNode* newnode = CreateNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
1
2
3
4
5
6

• 注意:头插的这段代码对于没有节点的情况，既（*pphead）为空的情况也适用，所以不需要分类讨论
• 创造出新节点的指针后，赋给newnode，此时newnode的数值域存放的也就是头插函数的第二个参数x，指针域存放的是NULL
• 紧接着将*pphead，也就是plist，也就是原来第一个第一个节点的地址赋给newnode，这样，newnode就和原链表的节点取得了联系
• 最后将newnode地址赋给*pphead，链表就顺利头插了！
  单链表的头插是非常方便的，这也是一个单链表的优点

---

6.尾删

• 声明

void SLTPopBack(SLNode** pphead);
1

• 当节点数量大于1的时候，用一级指针也可以，而头删的参数选择二级指针是因为当节点数只剩一个的时候，既是头也是尾，删除后要将*pphead置空，这样考虑的话就要对指针进行修改，所以索性传成二级指针了。

分析一波：

• 尾删注意：

• 在删除前必须保存一下即将删除节点的地址，这样的话才能free掉对应的内存空间，避免内存泄露的问题出现，所以我们还需要定义一个结构体指针prev，用来记录即将删除节点的地址

• 当只有一个节点直接释放掉即可

• 逻辑图如下：

• 只有一个节点时，对应的代码这样写正确吗？
  

这段代码的问题在于当只有一个节点的时候，prev和tail指向的是同一块空间，free掉tail之后，prev就变成了野指针
一定要理解free掉的是指针指向的内存空间，并不是把指针销毁了
而perv->next相当于对野指针访问了，所以是存在问题的

还存在一个问题，当节点都被删除完后，只剩一个NULL，如果继续删除，此时*pphead就为空，所以在删除前要对指针进行检查（断言 或者 if判断后提前return）。

• SList.c

void SLTPopBack(SLNode** pphead)
{
	assert(*pphead);
	//1.一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//一个以上的节点
	{
		//找尾
		SLNode* prev = NULL;
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;//可有可无，因为出了tail作用域，tail也会自动销毁
		prev->next = NULL;//必须置空，否则内存泄漏
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

或者也可以这样写（只有else后的部分修改了）

void SLTPopBack(SLNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 逻辑图如下：
  

• assert判断链表头节点是否为空，为空则报错。

• 链表只有一个节点时，直接释放头节点空间，然后置空。

• 链表有多个节点时，通过循环使变量 tail->next 找到尾节点，然后释放tail后一个节点的空间，也就是尾节点的空间，同时将其置空。

---

7.头删

• 声明

void SLTPopFront(SLNode** pphead);
1

直接free掉头节点可以吗？

不行，当存在多个节点时，如果直接free第一个，后续的所有链表都访问不到了，内存也就随之泄漏了

先看看这个代码错哪里了？

tmp和*pphead指向的是同一块空间，free（tmp）后，*pphead成为了野指针
不要误认为free 掉 tmp后对 * pphead没有影响
但是上述代码的后两行换一下位置就对了

• SList.c

void SLTPopFront(SLNode** pphead)
{
	assert(*pphead);
	
	SLNode* tmp = *pphead;
	
	*pphead = (*pphead)->next;
	
	free(tmp);
}
1
2
3
4
5
6
7
8
9
10

---

8.查找元素

• 声明

SLNode* SLTFind( SLNode*phead,SLNDataType x);
1

查找不需要修改指针，传一级指针就可以了，遍历链表即可

• SList.c

SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->val == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 函数在单链表中查找包含特定数据值 x 的节点。
• 变量cur通过循环找到数据 val 等于x的节点。
• 找到则返回指向当前节点的指针 cur，否则返回值为空。

---

9.在pos位置前插入一个元素

这个操作是单链表的一个劣势，因为单链表不支持随机访问，找下一个节点方便，但上一个节点并不好找

• 声明

void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)；
1

如果pos为第一个节点，相当于头插
直接调用头插函数 SLTPushFront(SLNode** pphead, SLNDataType x);

分析：

• 需要找到pos的前一个节点地址，也就是pos前一个节点的指针，保存赋给prev，
• 再在堆区上创建新的节点，将prev的指针域赋成新节点的地址，再将新节点的指针域赋成pos的地址，pos地址不需要提前保存，因为pos地址是参数提供好的。
  逻辑图如下：
  

void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
	// 严格限定pos一定是链表里面的一个有效节点
	assert(pphead);
	assert(pos);
	assert(*pphead);

	if (*pphead == pos)
	{
		// 头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLNode* newnode = CreateNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• 第一个assert判断传入头节点指针的地址是否合法，为空则报错。

• 第二个assert判断传入指向链表中某个节点的指针pos是否合法，不存在则报错。

• 如果在头节点位置之前插入，则调用头插解决。

• 如果不是头节点位置，则创建一个指向链表头节点的指针 prev，然后使用循环找到要插入位置 pos 前面的节点。

• 创建一个新的节点 newnode 并将数据值 x 存储在其中。

• 修改 prev 节点的 next 指针，使其指向新节点 newnode，从而将新节点插入到 pos 前面

---

10.指定位置之后插入

• 声明

void SLTInsertAfter(SLNode** pphead, SLNode* pos, SLNDataType x);
1

逻辑图如下：

• SList.c

void SLInsertAfter(SLNode* pos, SLNDataType x)
{
	assert(pos);
	SLNode* newnode = BuyLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7

• 先创建好新的节点newnode
• 将newnode的指针域赋成下一节点的地址，也就是原来pos的指针域
• 将pos指针域赋值为newnode地址，完美插入。

---

11.删除pos位置的值

• 声明

void SLTErase(SLNode** pphead, SLNode* pos);
1

逻辑图如下：

• SList.c

void SLTErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (*pphead == pos)
	{
		// 头删
		SLTPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

分析：

• 第一个assert判断传入头节点指针的地址是否合法，为空则报错。
• 第二个assert判断链表头节点是否为空，为空则报错。
• pos节点为头节点，则调用头删解决。
• pos不为头节点，则创建变量prev指向头节点，通过循环找到pos节点的前一个节点。
• 将prev的next指向要删除的pos节点的下一个节点。
• 释放pos空间

---

12.删除pos位置之后的值

• 声明

void SLTEraseAfter(SLNode* pos);
1

逻辑图如下:

• Slist.c

void SLTEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);

	SLNode* tmp = pos->next;
	pos->next = pos->next->next;
-
	free(tmp);
	tmp = NULL;
}
1
2
3
4
5
6
7
8
9
10
11

---

13.销毁链表

• 声明

void SLTDestroy(SLNode** pphead);
1

逻辑图如下：

• SList.c

void SLTDestroy(SLNode** pphead)
{
	assert(pphead);

	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}

	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 定义了两个指针，cur 和 tmp，用于遍历链表并释放内存。开始时，cur 被初始化为链表的头节点指针 pphead。

• 这是一个循环，它会一直执行，直到 cur 变为 NULL，遍历到链表的末尾。

• 在循环中，首先将 cur 赋值给 tmp，以便稍后释放 cur 指向的节点的内存。
  然后，将 cur 移动到下一个节点，即 cur = cur->next;

• 最后，使用 free 函数释放 tmp 指向的节点的内存，即释放链表中的一个节点，接着进行循环依次释放节点直到链表最后。

所有完整版已经上传至我的gitte账户，

链接在这：gitee单链表