🍉博客主页：阿博历练记
📗文章专栏：数据结构与算法
🚚代码仓库：阿博编程日记
🌹欢迎关注：欢迎友友们订阅收藏+关注哦

🍌前言

友友们，上期给大家介绍完顺序表功能实现之后，我们知道了它的一个绝对优势就是下标的随机访问，但是顺序表也有以下几个不优的特点：
1.中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3.增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
顺序表的一切根源就是：需要一块连续的物理空间。这时候我们就会想有没有什么好的解决方案可以做到空间可以按需申请释放，插入删除数据的时候时间复杂度能够变成O(1),这时候就要引入链表了，链表的空间是不连续的.
1.带头或者不带头

2.循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是无头单向非循环链表.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多.

💻无头单向非循环链表

🔍1.链表的定义

typedef  int  SLTDataType;
typedef struct  SListNode
{
SLTDataType  data;
struct SListNode* next;
}SLTNode;
1
2
3
4
5
6

⭐指针类型

友友们注意了，因为我们的结点是用结构体定义的，所以结点是一个结构体类型的变量，而这个next指针是下一个结点的地址，它指向了下一个结点，所以它的类型要和我们结点类型保持一致.

🔍2.链表的遍历（打印）

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

⭐代码理解

1.逻辑结构

2.物理结构

🔍3.链表的头插

SLTNode* BuyLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
return  NULL;
}
newnode->data = x;
newnode->next = NULL;
return  newnode;
}
void  SLPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);            //链表为空，pphead也不能为空，因为它是头指针plist的地址，如果它为空，就会出现对空指针的解引用，所以我们需要断言一下
//assert(*pphead);        //不能断言，链表即使为空，也需要插入
//SLTNode  node;        这是一个局部的结点，在栈区上存放着，出了作用域就销毁了
SLTNode* newnode = BuyLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

⭐误区（为什么传指针改变不了实参）

❌错误案例

SLTNode* BuyLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
return  NULL;
}
newnode->data = x;
newnode->next = NULL;
return  newnode;
}
void  SLPushFront(SLTNode* phead, SLTDataType x)
{
SLTNode* newnode = BuyLTNode(x);
newnode->next = phead;
phead = newnode;
}
void  TestSList1()
{
SLTNode* plist = NULL;
SLPushFront(plist, 1);
SLPushFront(plist, 2);
SLPushFront(plist, 3);
SLPushFront(plist, 4);
SLTPrint(plist);
}
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
26
27

这里阿博再给友友们举例解释一下
❌错误案例

void swap(int* p1, int* p2)
{
int *temp = p1;
p1 = p2;   
p2 = temp;
}
int  main()
{
int a = 0;
    int b = 1;
int* px = &a, * py = &b;
swap(px, py);
return  0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

友友们注意，这里我们p1和p2的改变并不能影响px和py，因为我们传的是px和py，用p1和p2分别接收，这本质上就是整形指针变量的赋值，形参只是实参的一份临时拷贝，形参的改变并不会影响实参.我们如果要想改变，就必须传地址，然后解引用改变它，要改变int，就要传int的地址，要改变int*,就要传int*的地址.我们要改变谁，就要传谁的地址.

✔正确案例

void swap(int** pp1, int** pp2)
{
int *temp = *pp1;
*pp1 = *pp2;   
*pp2 = temp;
}
int  main()
{
int a = 0;
    int b = 1;
int* px = &a, * py = &b;
swap(&px, &py);
return  0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

所以友友们如果我们要改变plist，就要传plist的地址.

🔍4.链表的尾插

void  SLPushBack(SLTNode** pphead, SLTDataType x)
{
//assert(*pphead);    //链表为空，可以尾插
assert(pphead);   //链表为空，pphead也不能为空，因为它是头指针plist的地址，如果它为空，就会出现对空指针的解引用，所以我们需要断言一下
SLTNode* newnode = BuyLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;      //改变结构的指针plist
}
else
{
SLTNode* 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

友友们，这里我们尾插就需要找到尾结点.

⭐误区1.找尾结点错误

❌错误案例

void  SLPushBack(SLTNode* phead, SLTDataType x)
{
SLTNode* tail = phead;
while (tail != NULL)
{
tail = tail->next;              
}
SLTNode* newnode = BuyTLNode(x);    
tail = newnode;
}
1
2
3
4
5
6
7
8
9
10

友友们，让上一个结点存放下一个结点的地址才是我们尾插的实质，所以我们要找尾就要修改一下循环条件，因为尾结点的next指针为空，所以我们把循环条件改为tail->next!=NULL,这样tail就指向了尾结点.⛳友友们这里还有一个关键点就是tail和newnode都是局部变量，出完作用域就销毁了，但是结点的next指针是不会销毁的，因为它属于结点，而我们结点是malloc开辟出来的，在堆区上存放，程序运行结束或者free掉才会销毁.

⭐误区2.为什么不用一级指针

案例1


这里友友们可能有疑问，这里用一级指针不是也可以尾插成功吗，那我们为什么还用二级指针呢，我们这里再换一种情况就会有一种意想不到的结果.🙉🙉🙉

案例二

友友们这里我们都会迷惑，为什么这里一级指针就不行了呢，下面和阿博一起来探索它.


所以友友们这里如果我们要想改变plist，就要传plist的地址.友友们注意如果plist为空时，我们要改变plist，就要传plist的地址，就要用二级指针，但是当plist不为空时，我们尾插其实就是让tail->next=BUYLTNode(x),我们此时改变的是tail的next指针，它是结构体里面的内容，这时候我们用结构体指针就可以改变，就是一级指针就可以尾插.要改变谁，我们就要传谁的地址.

1.*pphead=newnode 改变的是结构的指针plist，所以用二级指针.
2.tail->next=newnode 改变的是结构体的尾结点，用一级指针就可以.

⛳友友们注意，头插和尾插是不一样的，头插每一次都需要传结构体指针plist地址，因为头插的时候，需要赋值（*pphead=newnode），*pphead就是就是plist，就相当于我们每一次都要改变plist，所以我们每一次都需要传plist的地址，而尾插只需要第一次传就可以了，因为第一次改变的是plist（结构体的地址），其它都是改变的是tail->next（结构体的尾结点）.

🔍5.链表的尾删

void  SLPopBack(SLTNode** pphead)
{
//没有结点
//一个结点
//多个结点
assert(pphead) //链表为空，pphead也不能为空，因为它是头指针plist的地址，如果它为空，就会出现对空指针的解引用，所以我们需要断言一下
assert(*pphead);   //声明一下如果链表为空就不能尾删了
if ((*pphead)->next== NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);     //指向被释放的空间，野指针问题
//tail = NULL;
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
25
26

🔍6.链表的头删

友友们，这里我们头删的时候，有两种方法，第一种就是保留旧头结点的地址，然后让新头结点往后走，释放旧的头结点第二种就是保留头结点下一结点的地址，然后释放头结点，把头结点下一结点的地址给新的头结点.
1.保留头结点下一结点的地址

void  SLPopFront(SLTNode** pphead)
{
assert(*pphead);   //链表为空，不能头删
assert(pphead);     //链表为空，pphead也不能为空，因为它是头指针plist的地址，如果它为空，就会出现对空指针的解引用，所以我们需要断言一下
if ((*pphead)->next == NULL)      //一个结点
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* del = (*pphead)->next;
free(*pphead);
*pphead = del;
/**pphead = (*pphead)->next;
free(del);*/
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.保留头结点的地址

void  SLPopFront(SLTNode** pphead)
{
assert(*pphead);   //链表为空，不能头删
assert(pphead);     //链表为空，pphead也不能为空，因为它是头指针plist的地址，如果它为空，就会出现对空指针的解引用，所以我们需要断言一下
if ((*pphead)->next == NULL)      //一个结点
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

🔍7.链表的查找

SLTNode* STFind(SLTNode* phead, SLTDataType  x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return  cur;
}
cur = cur->next;
}
return  NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

友友们注意，这里while循环里面不能是cur->next，因为这样的话虽然cur指到尾结点了，但是while循环没进去，if语句没有执行，所以尾结点的data就没有和x比较，就相当于少遍历一个结点.

⭐assert断言

友友们并不是所有的指针都需要断言，我们要判断，比如说：链表的查找，链表的打印，这里我们就不需要再去进行 assert(phead)，因为链表为空，循环就没有进去，只不过找不到返回空，打印为空.比如链表的头插，我们就需要断言（pphead）,因为pphead是plist的地址，如果它为空，newnode->next =*pphead;这一句就会出现对空指针的解引用，所以我们需要断言一下，但是assert(*pphead)这个就不需要断言了，因为(*pphead)是plist，它为空就相当于plist为空，链表为空不影响我们头插，所以这里就不需要断言.但是头删和尾删的时候我们就需要进行断言一下(*pphead)，因为它就是plist，如果链表为空，就不要再头删或者尾删了.

🔍8.链表的任意位置的插入

void  SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SLPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuyLTNode(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

友友们，我们假设这个位置是pos，我们要在pos位置上插入数据，pos之后的数据就要往后挪动，就相当于我们在pos之前插入数据.

这里我们的二级指针就是为头插那个地方准备的，因为如果不是头插的话，我们改变的都是结构体的next指针，它们都属于结构体，我们只需要一个结构体指针就可以了，就不需要用二级指针了.

🔍9.链表的任意位置之后的插入

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

友友们注意这里newnode->next和pos->next先后顺序不能弄反，如果我们先改变pds->next的话，这样newnode->next=newnode，它就自己指向自己了，就成了一个环.

🔍10.链表的任意位置的删除(pos位置）

void  SLErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

🔍11.链表的删除(pos位置后的结点）

void  SLEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);   //防止它是最后一个，这样它后面就没有节点了
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
1
2
3
4
5
6
7
8

友友们这里要注意我们要提前保存好我们我们要删除位置之后的结点，否则我们改变pos->next之后，就找不到它起初的位置了，还有一定要注意如果是尾结点，就不能再用这个函数了，因为尾结点的下一结点为空，我们就不需要删了，所以这里需要断言一下.

🔍12.链表的销毁

void   SLDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

友友们注意这里我们先要保存下一结点，否则我们free掉头结点后我们就找不到下一结点了.

👻SList.h代码

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef  int  SLTDataType;
typedef struct  SListNode
{
SLTDataType  data;
struct SListNode* next;
}SLTNode;
void  SLTPrint(SLTNode* phead);
void  SLPushFront(SLTNode** phead,SLTDataType x);
void  SLPushBack(SLTNode** pphead, SLTDataType x);
void  SLPopFront(SLTNode** pphead);
void  SLPopBack(SLTNode** pphead);
//单链表查找
SLTNode* STFind(SLTNode* phead, SLTDataType  x);
//在pos之前插入
void  SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入
void   SLInsertAfter(SLTNode* pos, SLTDataType  x);
//删除pos位置的值
void  SLErase(SLTNode** pphead, SLTNode*pos);
//删除pos位置后面的值
void   SLEraseAfter(SLTNode* pos);
void   SLDestory(SLTNode** pphead);
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
26

👻SList.c代码

#define  _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void  SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur!=NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SLTNode* BuyLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
return  NULL;
}
newnode->data = x;
newnode->next = NULL;
return  newnode;
}
void  SLPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);            //链表为空，pphead也不能为空，因为它是头指针plist的地址，如果它为空，就会出现对空指针的解引用，所以我们需要断言一下
//assert(*pphead);        //不能断言，链表即使为空，也需要插入
//SLTNode  node;        这是一个局部的结点，在栈区上存放着，出了作用域就销毁了
SLTNode* newnode = BuyLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void  SLPushBack(SLTNode** pphead, SLTDataType x)
{
//SLTNode* tail = phead;
//while (tail->next != NULL)
//{
//tail = tail->next;              
//}
//SLTNode* newnode = BuyLTNode(x);       //这里并没有把链表链接起来，因为tail和newnode都是局部变量，出了作用域就销毁了，而且内存存在泄露，链表链接的实质是尾部的next指针指向下个结点的地址
//tail->next = newnode;
//1.空链表
//2.非空链表
//assert(*pphead);    //链表为空，可以尾插
assert(pphead);   //链表为空，pphead也不能为空，因为它是头指针plist的地址，如果它为空，就会出现对空指针的解引用，所以我们需要断言一下
SLTNode* newnode = BuyLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;      //改变结构的指针plist
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{ 
tail = tail->next;
}
tail->next = newnode;    //改变结构体的尾结点
}
}
void  SLPopBack(SLTNode** pphead)
{
//没有结点
//一个结点
//多个结点
/*if (*pphead == NULL)
{
return;
}*/
assert(pphead);
assert(*pphead);
if ((*pphead)->next== NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);     //指向被释放的空间，野指针问题
//tail = NULL;
prev->next = NULL;
}
}
void  SLPopFront(SLTNode** pphead)
{
assert(*pphead);   //链表为空，不能头删
assert(pphead);     //链表为空，pphead也不能为空，因为它是头指针plist的地址，如果它为空，就会出现对空指针的解引用，所以我们需要断言一下
if ((*pphead)->next == NULL)      //一个结点
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
}
}
SLTNode* STFind(SLTNode* phead, SLTDataType  x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return  cur;
}
cur = cur->next;
}
return  NULL;
}
void  SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SLPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuyLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
void  SLInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuyLTNode(x);
newnode->next = pos->next;
pos->next = newnode; 
}
void  SLErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
void  SLEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);   //防止它是最后一个，这样它后面就没有节点了
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
void   SLDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

👻test.c代码

#define  _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void  TestSList1()
{
SLTNode* plist = NULL;
SLPushFront(&plist, 1);
SLPushFront(&plist, 2);
SLPushFront(&plist, 3);
SLPushFront(&plist, 4);
SLPopFront(&plist);

SLTPrint(plist);
SLPushBack(&plist, 5);

SLTPrint(plist);

}
void  TestSList2()
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);

SLTPrint(plist);
SLTNode* pos = STFind(plist, 3);
if (pos)
{
SLInsert(&plist, pos, 30);
}
SLTPrint(plist);
pos = STFind(plist, 2);
SLInsertAfter(pos, 20);
pos = STFind(plist, 2);
if (pos)
{
SLErase(&plist, pos);
}
SLTPrint(plist);
SLDestory(&plist);
}
int  main()
{
TestSList1();
TestSList2();
return  0;
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

🧋代码效果展示