数据结构之链表（单链表）

---

前言

数据结构之顺序表中我们有讲到顺序表有一些问题和缺点，为了能解决顺序表的问题，我们引入一个新的线性表——链表

一、链表

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

链表与顺序表的不同
1.链表是按需申请空间的
2.链式结构在逻辑上是连续的但是在物理结构上不一定是连续的；两次申请的空间可能是连续的，也可能是不连续的。
注意：链表和顺序表所申请的空间都是在堆上申请的。（动态开辟的空间都是在堆上申请的）

二、链表的八种结构

1.单向或者双向

2.带头或者不带头（头：哨兵位）

3.循环或者不循环

以上三种类型，两两组合就能得到链表的八种结构，虽然有这么多种链表，但是我们最常用的还是两种：
1.无头单向非循环链表；

2.有头双向循环链表。

1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。

我们今天主要介绍的是无头单向非循环链表（单链表）。

三、单链表

1.单链表的声明及接口的声明

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
//动态申请一个新的节点
SLTNode* BuySLTNode(SLTDataType x);
//打印单链表中的数据
void SLTPrint(SLTNode* phead);
//单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//单链表的头删
void SLTPopFront(SLTNode** pphead);
//单链表的尾删
void SLTPopBack(SLTNode** pphead);
//单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 单链表在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 单链表在pos位置之后插入x
void SLTInsertAfter(SLTNode* pphead, SLTNode* pos, SLTDataType x);
// 单链表删除pos位置的节点
void SLTEarse(SLTNode** pphead, SLTNode* pos);
// 单链表删除pos位置之后的节点
void SLTEarseAfter(SLTNode* 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
26
27
28

2.接口的实现

1.开辟一个新的节点

（单链表是由一个节点一个节点链接起来的）

//开辟一个新的节点
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* p = (SLTNode*)malloc(sizeof(SLTNode));
	p->data = x;
	p->next = NULL;
	return p;
1
2
3
4
5
6
7

1.打印单链表

（方便调试观察）

//打印单链表中的数据
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while(cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11

2.头插

//单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* NewNode = BuySLTNode(x);
	NewNode->next = *pphead;
	*pphead = NewNode;
}
1
2
3
4
5
6
7

3.尾插

//单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* NewNode = BuySLTNode(x);
	//单链表为空
	if ((*pphead) == NULL)
	{
		NewNode->next = *pphead;
		*pphead = NewNode;
	}
	//单链表不为空
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			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
20
21

4.头删

//单链表的头删
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);//如果链表为空再继续删除就会报警告
	SLTNode* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
}
1
2
3
4
5
6
7
8

5.尾删

//单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);//如果链表为空再继续删除就会报警告
	SLTNode* cur = *pphead;
	if ((cur->next) != NULL)
	{
		SLTNode* prev = cur->next;
		while (prev->next != NULL)
		{
			prev = prev->next;
			cur = cur->next;
		}
		free(prev);
		cur->next = NULL;
	}
	else
	{
		free(cur);
		*pphead = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

6.单链表的查找

//单链表的查找（找到了返回该节点的地址）
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* p = phead;
	while (p)
	{
		if (p->data == x)
		{
			return p;
		}
		p = p->next;
	}
	assert(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

7.在pos位置之前插入数据

// 单链表在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	SLTNode* prev = *pphead;
	SLTNode* NewNode = BuySLTNode(x);
	if (prev == pos)
	{
		NewNode->next = prev;
		*pphead = NewNode;

	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		NewNode->next = prev->next;
		prev->next = NewNode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

8.在pos位置之后插入数据

// 单链表在pos位置之后插入x
void SLTInsertAfter(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
	SLTNode* prev = phead;
	SLTNode* NewNode = BuySLTNode(x);
	while (prev)
	{
		if (prev == pos)
		{
			NewNode->next = prev->next;
			prev->next = NewNode;
			break;
		}
		prev = prev->next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

9.删除pos位置的数据

// 单链表删除pos位置的节点
void SLTEarse(SLTNode** pphead, SLTNode* pos)
{
	SLTNode* prev = *pphead;
	if (prev == pos)
	{
		*pphead = prev->next;
		free(prev);
		prev = *pphead;
	}
	else
	{
		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
20

10.删除pos位置之后的数据

// 单链表删除pos位置之后的节点
void SLTEarseAfter( SLTNode* pos)
{
	SLTNode* cur = pos;
	assert(cur->next);//当pos指向链表最后一个节点时，不能删除pos后的值
	cur = cur->next;
	pos->next = cur->next;
	free(cur);
}
1
2
3
4
5
6
7
8
9

3.主函数（测试）

主要用于测试单链表实现的接口，大家也可以自行调整，代码如下：

void test1()//测试：头插
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 6);//注意是传plist的地址过去（要改变plist的值就要传plist的地址，因为形参只是实参的一份临时拷贝，如果只是传plist过去就只是将phead这个plist的临时拷贝值进行改变，)
	SLTPushFront(&plist, 16);
	SLTPushFront(&plist, 62);
	SLTPushFront(&plist, 63);
	SLTPushFront(&plist, 46);
	SLTPushFront(&plist, 67);
	SLTPrint(plist);
}
void test2()//测试：尾插
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 62);
	SLTPushBack(&plist, 63);
	SLTPushBack(&plist, 46);
	SLTPushBack(&plist, 67);
	SLTPrint(plist);
}
void test3()//测试：头删
{

	SLTNode* plist = NULL;
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 62);
	SLTPushBack(&plist, 63);
	SLTPushBack(&plist, 46);
	SLTPushBack(&plist, 67);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
}
void test4()//测试：尾删
{

	SLTNode* plist = NULL;
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 18);
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 56);
	SLTPushBack(&plist, 78);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
}
void test5()//测试：查找
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 26);
	SLTPushBack(&plist, 18);
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 56);
	SLTPushBack(&plist, 78);
	SLTNode* ret = SLTFind(plist, 56);
	if (ret)
	{
		printf("%p\n",ret);
	}
}
void test6()//测试:在pos位置之前插入数据
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 26);
	SLTPushBack(&plist, 18);
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 56);
	SLTPushBack(&plist, 78);
	SLTPrint(plist);
	//SLTNode* pos = SLTFind(plist, 26);
	//SLTInsert(&plist, pos, 55);//相当于头插
	//SLTNode* pos = SLTFind(plist, 16);
	//SLTInsert(&plist, pos, 55);//正常插入
	//SLTNode* pos = SLTFind(plist, 88);//pos不是链表中的数据，会被SLTFind检测出来不会进行插入
	//SLTInsert(&plist, pos, 98);//正常插入
	SLTInsert(&plist,NULL, 55);//相当于尾插
	SLTPrint(plist);
}
void test7()//测试:插入（在pos位置之后插入）//不可能进行头插
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 26);
	SLTPushBack(&plist, 18);
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 56);
	SLTPushBack(&plist, 78);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 78);//相当于尾插
	SLTInsertAfter(plist, pos, 55);
	SLTInsertAfter(plist, plist, 55);
	SLTPrint(plist);
}
void test8()//测试:删除pos位置的数据
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 26);
	SLTPushBack(&plist, 18);
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 56);
	SLTPushBack(&plist, 78);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 78);//相当于尾删
	SLTEarse(&plist, pos);
	SLTPrint(plist);
}
void test9()//测试:删除pos位置之后的数据
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 26);
	SLTPushBack(&plist, 18);
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 56);
	SLTPushBack(&plist, 78);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 56);
	SLTEarseAfter(pos);
	SLTPrint(plist);
}

int main()
{
	//test1();
	//test2();
	//test3();
	//test4();
	//test5();
	//test6();
	//test7();
	//test8();
	test9();
	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
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

总结

以上就是今天要讲的内容，本文介绍了线性表中的链表，主要实现了单链表（无头不循环单链表），大家感兴趣的也可以根据作者所写思路（注释）自行实现单链表。
本文作者也是一个正在学习编程的萌新，目前也只是刚开始接触数据结构这方面的内容，如果有什么内容方面的错误或者不严谨，欢迎大家在评论区指出。
最后，如果本篇文章对你有所启发的话，也希望可以支持支持作者，谢谢大家！