单链表详解

今天我们继续来学习我们的链表，今天我们来学习单链表，什么是单链表呢，我们逻辑结构上可以·认为是下面这个图。

然后我们结构体的定义就是下面这个

typedef int SLDateType;
typedef struct SList
{
	SLDateType x;
	struct SList* next;
}SL;
1
2
3
4
5
6

为什么是这样会定义，大家有没有想过，我们有一个指针叫next，顾名思义就是指向下一个节点，如果我们来完善上面的这张图就是

我们的这张内容就是来实现这样的一个链表，然后在这个基础上继续实现增删查改

那和顺序表是一样的，我们需要先来初始化我们的链表，我们这里可以采用两种方式，一种是直接先给一个事先开好的节点，然后进行增删查改，你也可以理解为有哨兵位的头节点，但是我们这里先不用这个方法，我们初始化的时候就是给个空指针，然后进行我们下一步的操作。

在这里我也先给出我们要写的几个函数的声明。

// slist.h
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);

// 在pos的前面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);
// 删除pos位置
void SLTErase(SLNode** pphead, SLNode* pos);
void SLTDestroy(SLNode** 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

后面的代码还是按照我自己习惯的定义风格，上面的只是给出一个大概来供大家参考

我们来按照上面的声明来一个一个实现他们的定义，我们先来实现如何让尾插，因为考虑到尾插肯定是要先创建新的节点，所以我们先来实现的函数时创造新节点的函数。

SL* BuySListNode(SLDateType x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	newnode->Date = x;
	newnode->next = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

创造新的节点出来我们现在先写一个尾插函数，尾插就是把新节点插入到尾节点的后面

上面的这个图里尾节点就是空指针的前一个节点

那我们要实现尾插的思路就是在tail的后面插入就行了，思路是很简单的，但是我们需要注意的一个点就是如果我们一开始的时候就是空指针的话，我们不能直接插入，这个时候head就是空，所以我们第一个节点是头节点也是尾节点。

尾插的实现

void SLPushBack(SL** ppHead, SLDateType x)
{
	assert(ppHead);
	SL* NewNode = BuySListNode(x);
	if (*ppHead == NULL)
	{
		*ppHead = NewNode;
	}
	else
	{
		SL* 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

我们再来分析头插是怎么个事，首先我们先要来分析一个节点都没有的时候，我们一开始就是我们的空指针，其实就是直接把我们创造出来的节点给我们的头指针就可以了，那如果是多个节点的话，就是newnode指向我们的ppHead，然后再继续更新头节点ppHead就可以解决问题了

下面是头插的代码

void SLPushFront(SL** ppHead, SLDateType x)
{
	assert(ppHead);
	SL* NewNode = BuySListNode(x);
	NewNode->next = *ppHead;
	*ppHead = NewNode;
}
1
2
3
4
5
6
7

我们可以看到头插的代码其实很简单，这也能说明单链表头插的效率是很高的，在我们后面学习stl中单链表也是只有头插，因为头插的时间复杂度就是O（1）。
因为我们要来看我们的的效果，其实我们这里可以写个打印的函数，打印函数很简单，直接遍历单链表就行。
打印函数代码

void SLPrint(SL* phead)
{
	SL* cur = phead;
	while (cur)
	{
		printf("%d->", cur->Date);
		cur = cur->next;
	}
	printf("NULL\n");
}

1
2
3
4
5
6
7
8
9
10
11

我们的节点因为都是malloc出来的，我们使用过程中需要对其释放，所以这里再写一个destory的函数

void SLDestory(SL** ppHead)
{
	assert(ppHead);
	assert(*ppHead);
	SL* cur = *ppHead;
	while (cur)
	{
		SL* next = cur->next;
		free(cur);
		cur = next;
	}

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

讲完头插和尾插，这里对写链表给出的建议，一个我们需要来断言，比如assert需要断言的是我们的ppHead不能为空，因为这是head的地址，它一定不能为空，下一个就是我们*ppHead，再头插和尾插的时候，单链表为空的时候我们也是可以进行插入的，所以这里不用写，但是我们的尾插需要分没有节点的时候和有节点的时候，这个需要我们来画图进行分析。

尾插实现好之后我们再来就是尾删和头删，这两个的断言就需要再三考虑，比如我们为空的时候就不能再删除了。。

尾删的时候我们需要有一个前指针来指向我们尾指针的前一个，这里我们就可以释放尾指针的时候，保持单链表的连续性，如果没有前指针就会出现找不到的现象。

尾删的代码

void SLPopBack(SL** ppHead)
{
	assert(ppHead);
	assert(*ppHead);
	//只有一个节点和多个节点的释放是不同的。
	SL* tail = *ppHead;
	if (tail->next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else
	{
		SL* prev = NULL;
		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

但是我们的头删代码就是很简单，我们来看看
代码

void SLPopFront(SL** ppHead)
{
	assert(ppHead);
	assert(*ppHead);
	SL* next = (*ppHead)->next;
	free(*ppHead);
	*ppHead = next;

}
1
2
3
4
5
6
7
8
9

只要free第一个节点再移动head就ok了

我们已经实现了增删，那肯定还有查找，我们再来补充一下我们在pos位置前面或者后面实现插入和删除，会了这些之后算是对单链表已经有了深入的理解了。

先是我们的查找是怎么个样子，遍历一遍就可以了

SL* SLFind(SL* ppHead, SLDateType x)
{
	assert(ppHead);
	SL* cur = ppHead;
	while (cur)
	{
		if (cur->Date == x)
		{
			return  cur;
		}
		cur = cur->next;
	}
	return NULL;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

我们这里给了一个断言，原因就是如果我们的链表为空，我们就不能进行查找，然后我们这里返回节点的位置，我们在后面的随机插入和删除有妙用。

首先我们先来对我们这个进行断言，要么都是空是什么意思和要么都不是空，首先是要么都是空的意思就是单链表一个节点都没有的时候，这个时候pos位置其实就是空，我们就相当于在空的位置前进行了插入，那其实就是相当于调用了头插，如果链表不是空，那理所当然，如果pos位置是空，也就相当于我们没有这个节点的位置，也就不能插入，所以这里的assert就是要确定要么都是空，要么都不是空。

//在pos前位置进行插入
void SLInsert(SL** ppHead, SL* pos, SLDateType x)
{
	
	assert(ppHead);
	//要么都是空，要么都不是空
	assert((pos && *ppHead) || (!pos && !(*ppHead)) );
	if (*ppHead == NULL)
	{
		SLPushFront(ppHead, x);
	}
	else
	{
		SL* NewNode = BuySListNode(x);
		SL* pre = *ppHead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		NewNode->next = pos;
		pre->next = NewNode;
	}
	


}
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

那我们上面的代码也不知道对不对，我们需要我们来进行测试看看。
测试代码也在下面

void test4()
{
	SL* head = NULL;
	SLInsert(&head, NULL, 10);
	SLPrint(head);
	SLPushBack(&head, 1);
	SLPushBack(&head, 2);
	SLPushBack(&head, 3);
	SLPushBack(&head, 4);
	SLPrint(head);
	SL* pos = SLFind(head, 3);
	SLInsert(&head, pos, 20);
	SLPrint(head);


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

可以看到我们的代码其实和预期结果是没有问题的，那我们马上写我们后面·的代码在pos位置进行删除。

先来看我们的断言环节，首先就是ppHead不能为空，因为这个是外面函数head的地址，如果这个也是空的话，就是对空指针的非法访问。
链表为空也不行，pos位置也不能为空，如果为空就是找不到了，我们也就不让他进入程序。

void SLErase(SL** ppHead, SL* pos)
{
	assert(ppHead);
	assert(*ppHead);
	assert(pos);
	if ((*ppHead)->next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else
	{
		SL* cur = *ppHead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		SL* tmp = pos->next;
		free(pos);
		pos = NULL;
		cur->next = tmp;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这里也是要分一个节点和多个节点，因为我们已经asser过，pos不可能为空，但是如果是只有一个节点的时候，那我们这里pos肯定是头节点，我们直接释放就行。当然还有其他方法，如果我们下面的代码不保存tmp位置，也可以不用写上面的了。

写完在pos之前添加，那我们继续写一个在pos位置之后删除和添加的代码，单链表的内容也就完善很多了。

这里断言只要断言这两个就行，一个是空进来就是找不到情况，还有一个就是指向节点的空位置，因为我们是在pos位置之后插入，所以这里确保必须得有一个节点。我们也可以继续断言assert（*ppHead），但是我觉得没有必要。

void SLInsertAfter(SL** ppHead, SL* pos, SLDateType x)
{
	assert(ppHead);
	assert(pos);
	if ((*ppHead)->next == NULL)
	{
		SLPushBack(ppHead, x);
	}
	else
	{
		SL* NewNode = BuySListNode(x);
		SL* next = pos->next;
		NewNode->next = next;
		pos->next = NewNode;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在继续写下一个随机删除的代码
也是在pos位置之后进行。

因为我们是在pos位置之后释放，所以这里其实至少也是得有两个节点以上，如果是一个节点的话我们pos的next就是我们的NULL，我们虽然是可以对空指针进行释放的，但是我觉得没有意义，那我们干脆就是考虑有两个节点以上的。

void SLEraseAfter(SL** ppHead, SL* pos)
{
	assert(ppHead);
	assert(*ppHead);
	assert(pos);
	SL* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

1
2
3
4
5
6
7
8
9
10
11

而且上面其实还有一个问题就是我们的pos位置其实不能是为节点，因为pos->next不能为空，我们才能访问pos->next->next，所以单链表还有好多细节，但是单链表有很多的写法，这里就不一一举列子，下面分享整个代码

SList.h

#pragma once
#include
#include
#include
typedef int SLDateType;
typedef struct SListNode
{
	SLDateType Date;
	struct SListNode* next;
}SL;



SL* BuySListNode(SLDateType x);

void SLPushBack(SL** ppHead, SLDateType x);

void SLPrint(SL* phead);

void SLDestory(SL** ppHead);

void SLPushFront(SL** ppHead, SLDateType x);


void SLPopBack(SL** ppHead);


void SLPopFront(SL** ppHead);


SL* SLFind(SL* ppHead, SLDateType x);

void SLInsert(SL** ppHead, SL* pos, SLDateType x);

void SLErase(SL** ppHead, SL* pos);


void SLInsertAfter(SL** ppHead, SL* pos, SLDateType x);


void SLEraseAfter(SL** ppHead, SL* 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

SList.c

#include"SL.h"


SL* BuySListNode(SLDateType x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	newnode->Date = x;
	newnode->next = NULL;
	return newnode;
}


void SLPushBack(SL** ppHead, SLDateType x)
{
	assert(ppHead);
	SL* NewNode = BuySListNode(x);
	if (*ppHead == NULL)
	{
		*ppHead = NewNode;
	}
	else
	{
		SL* tail = *ppHead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = NewNode;
	}
}

void SLPrint(SL* phead)
{
	SL* cur = phead;
	while (cur)
	{
		printf("%d->", cur->Date);
		cur = cur->next;
	}
	printf("NULL\n");
}


void SLDestory(SL** ppHead)
{
	assert(ppHead);
	assert(*ppHead);
	SL* cur = *ppHead;
	while (cur)
	{
		SL* next = cur->next;
		free(cur);
		cur = next;
	}

}

void SLPushFront(SL** ppHead, SLDateType x)
{
	assert(ppHead);
	SL* NewNode = BuySListNode(x);
	NewNode->next = *ppHead;
	*ppHead = NewNode;
}

void SLPopBack(SL** ppHead)
{
	assert(ppHead);
	assert(*ppHead);
	//只有一个节点和多个节点的释放是不同的。
	SL* tail = *ppHead;
	if (tail->next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else
	{
		SL* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}

}


void SLPopFront(SL** ppHead)
{
	assert(ppHead);
	assert(*ppHead);
	SL* next = (*ppHead)->next;
	free(*ppHead);
	*ppHead = next;

}

SL* SLFind(SL* ppHead, SLDateType x)
{
	assert(ppHead);
	SL* cur = ppHead;
	while (cur)
	{
		if (cur->Date == x)
		{
			return  cur;
		}
		cur = cur->next;
	}
	return NULL;

}

//在pos前位置进行插入
void SLInsert(SL** ppHead, SL* pos, SLDateType x)
{
	
	assert(ppHead);
	//要么都是空，要么都不是空
	assert((pos && *ppHead) || (!pos && !(*ppHead)) );
	if (*ppHead == NULL)
	{
		SLPushFront(ppHead, x);
	}
	else
	{
		SL* NewNode = BuySListNode(x);
		SL* pre = *ppHead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		NewNode->next = pos;
		pre->next = NewNode;
	}
	


}

void SLErase(SL** ppHead, SL* pos)
{
	assert(ppHead);
	assert(*ppHead);
	assert(pos);
	if ((*ppHead)->next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else
	{
		SL* cur = *ppHead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		SL* tmp = pos->next;
		free(pos);
		pos = NULL;
		cur->next = tmp;
	}
	
}


void SLInsertAfter(SL** ppHead, SL* pos, SLDateType x)
{
	assert(ppHead);
	assert(pos);
	if ((*ppHead)->next == NULL)
	{
		SLPushBack(ppHead, x);
	}
	else
	{
		SL* NewNode = BuySListNode(x);
		SL* next = pos->next;
		NewNode->next = next;
		pos->next = NewNode;
	}
}



void SLEraseAfter(SL** ppHead, SL* pos)
{
	assert(ppHead);
	assert(*ppHead);
	assert(pos);
	SL* del = pos->next;
	pos->next = pos->next->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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

那今天的分享就到这里，我们下次再见。