本篇介绍线性表链表中的单链表，链表由一系列节点组成，每个节点包含数据和指向下一个节点（对于单链表）或前后节点（对于双向链表）的指针

1.链表

1.1 概念及结构

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

链式结构的逻辑一般是连续的，但是在物理存储上不一定是连续的，因为每个节点都是从堆上申请来的，从堆上申请的空间要根据实际情况分配空间，两次申请可能是连续的也有可能不是连续的

简单来说，每个节点都存储了下一个节点的地址，即能找到下一个节点，就形成了链表

我们还需要了解几个概念：

?头结点

图中的plist就是头结点，位于链表的起始位置，但不存储实际的有效数据(有效数据指的是结构体的内的数据，而不是结构体地址)，主要作用是作为链表的入口，通过它的指针域来指向链表中的第一个实际存储数据的节点

?首节点

首节点就是跟在头节点后的链表中第一个存储实际有效数据的节点

?哨兵位

哨兵位和头结点类似，通常不存储实际数据，存储地址，哨兵位可以看成一个灵活的节点，可以在链表任何位置方便进行增删查改操作

每个节点的结构体：

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

• 1
• 2
• 3
• 4
• 5
• 6
• 7

1.2 分类

链表有三种分类方式
?⑴单向或双向

?⑵带头或不带头

?⑶循环或者非循环

这三种情况能组合出8种链表，这里我们只介绍两种常用的链表

无头单向非循环链表： 结构简单，实现麻烦，通常在面试笔试中以题目形式出现比较多(因为其他出成题目太难了)，单链表也更多的作为底层结构来进行算法应用

带头双向循环链表： 结构复杂，实现简单，这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了

2.单链表接口实现

2.1 单链表节点创建

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

顺序表中我们空间不够时需要不断扩容，链表中的节点申请函数就是这种类似的效果，但是顺序表是对它底层的数组进行二倍扩容，而节点申请函数一次性只能申请一个节点，用一个给一个，间接避免了空间浪费，注意返回的是新节点的地址

2.2 单链表打印

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	//while(cur->next != NULL)会遗漏最后一个数据
	//while(cur != NULL)也可以这样写
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
		//cur++只有数组才这么写
	}
	printf("NULL\n");
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

先传入头结点，然后我们需要一个cur指针作为移动指针来遍历单链表中的数据，每个节点的next都存储了下一个节点的地址，所以循环赋值就可以实现单链表的移动，最后一个节点指向的是空指针

?值得注意的是： 顺序表的打印需要断言传入的结构体指针是因为该指针涉及到访问，万一传入的空指针，会造成非法访问；链表的打印有可能该链表本来就是空的，空链表也是能打印的，而且也不涉及指针访问，所以加断言反而不合理

2.3 单链表尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);

	//分没有节点，和有节点的情况
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	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
• 20
• 21

凡是涉及增加删除节点的操作，都要考虑是否为空的情况要不要特别考虑，因此这里为空时直接将头指针和新节点链接即可；不为空时循环遍历找到最后一个节点，将最后一个节点和新节点连接

?值得注意的是： 循环判断条件为tail->next != NULL，因为为空时可能要修改头指针存的地址，所以应该传二级指针

2.4 单链表头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7

头指针中存储的是第一个节点的地址，所以newnode->next = *pphead，然后newnode就成了第一个节点，那么当前头指针存的就是当前第一个节点newnode的地址

2.5 单链表尾删

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);//*phead要指针访问所以要断言
	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);
		tail = NULL;
		prev->next = NULL;//free之后可以赋值但不能指针访问
	}
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24

当没有节点时，删除的就是头指针，直接释放即可；当有节点时，我们要给最后一个节点和倒数第二个节点做标记，因为最后一个节点要释放，倒数第二个节点需要把他的next置为NULL

2.6 单链表头删

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

先存储首节点的地址，便于把首节点的下一个节点传给头节点，注意不要先释放节点，避免非法访问

2.7单链表查找

SLTNode* SListFind(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

这个和顺序表一样，通过简单的遍历链表 一 一 对比值即可

2.8 单链表在pos位置插入x

2.8.1 pos前

void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLTNode* newnode = BuySLTNode(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

同样是分为链表为空和链表不为空的情况，当链表为空时，相当于头插；当链表不为空时，prev找到pos的前一个位置，然后进行链接操作即可

2.8.2 pos后

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7

从代码形式上来看，pos后的插入明显是比pos前插入更简单的，pos前需要多传一个头指针参数，找到pos前一个数的位置；pos后只需要在pos后直接链接即可

2.9单链表在pos位置删除x

2.9.1 pos前

void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* 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

和在pos位置删除其实是一样的，分为空和不空的链表，但是一般我们不在函数内将要删除的节点置为空，习惯性在函数外进行此操作

2.9.2 pos后

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	//del = NULL;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

直接释放pos位置之后的节点即可，但是要注意需要断言pos->next，万一是最后一个节点的话，在其后删除会报错

2.2.10 单链表销毁

void SLTDestroy(SLTNode** pphead)
{
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* del = pcur;
		pcur = pcur->next;
		free(del);
	}
	*pphead = NULL;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

销毁的方法也不难，就是遍历链表，只要链表不为空就循环释放节点，关键是我们在释放前要把下一个节点记录下来，如果直接释放了当前节点，那么就找不到下一个节点了，所以我们要把下一个节点保存下来才释放当前节点

3.代码展示

传送门：Gitee单链表代码

3.1 SList.h

#pragma once

#include 
#include 
#include 

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);

SLTNode* BuySLTNode(SLTDataType x);

void SLTPushBack(SLTNode** pphead, SLTDataType x);

void SLTPushFront(SLTNode** pphead, SLTDataType x);

void SLTPopBack(SLTNode** pphead);

void SLTPopFront(SLTNode** pphead);

SLTNode* SListFind(SLTNode* phead, SLTDataType x);

void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);

void SLTEraseBefore(SLTNode** pphead, SLTNode* pos);

void SLTInsertAfter(SLTNode* pos, SLTDataType x);

void SLTEraseAfter(SLTNode* pos);

void SLTDestroy(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
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37

3.2 SList.c

#include "SList.h"

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

//创建节点
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(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);
		tail = NULL;
		prev->next = NULL;
	}
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

//查找节点
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//pos前插入
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushBack(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

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

//pos前删除
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL;
	}
}

//pos后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//pos后删除
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = 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

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！