【数据结构】单链表详解

当我们学完顺序表的时候，我们发现了好多问题如下：

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们
   再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

如何解决上面的问题呢？？今天就跟着小张一起学习单链表吧！！

链表的概念及结构

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

注意：1.链式结构在逻辑上是连续的，但是在物理上不一定连续
2.结点一般都是在堆上申请出来的（malloc）
3.从堆上申请的空间，是按照一定策略来分配的，两次申请的空间可能连续，也可能不连续

单链表

单链表的接口实现

void  printdata(info* phead)//打印单链表
info* BuySListNode(int x)//创建新结点
void pushback(info** pphead, int x)//尾插
void pushFront(info** pphead, int x)//头插
void popFront(info** pphead)//头删
void popBack(info** pphead)//尾删
info* SListFind(info* pphead, int x)//单链表查找
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
void SeqListErase(info** pphead, info* pos)//删除pos位置的值
void SListInsertAfter(info* pos, int x)//单链表在pos位置之后插入x
void SListEraseAfter(info* pos)//删除pos的后一个位置

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

0.结构体定义单个结点

typedef struct info {
	int data;//data存数据
	struct info* next;//info*next存放下一个结点的地址

}info;
1
2
3
4
5

1.创建新结点

info* BuySListNode(int x)
{
	info* newnode = (info*)malloc(sizeof(info));//空间申请
	assert(newnode);//断言，新结点是否申请到了
	newnode->data = x;//数据赋值
	newnode->next = NULL;//指向的地址赋值
	return newnode;//将申请好的空间首地址返回回去



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

断言，如果没申请到空间，mallo返回空指针，断言newnode就会报错

为什么要用二级指针传参在尾插，头插，尾删，头删中

分析：

2.尾插

void pushback(info** pphead, int x)//尾插
{
	info* newnode = BuySListNode(x);//将创建好的新结点的地址保存在newnode变量中
	

	if (*pphead == NULL)//链表无结点
	{
		*pphead = newnode;// 将创建好的头节点的地址给给*pphead，作为新头节点的地址
	}
	else
	{
		info* tail = *pphead;//定义一个指针，先指向头结点的地址
		while (tail->next != NULL)//循环遍历找尾结点
		{
			tail = tail->next;//指针指向下一个结点

		}
		tail->next = newnode;//找到尾结点，将尾结点的next存放新接结点的地址

	}

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

分析：

文字解释：大体上就是直接将最后一个结点的next存入新结点的地址，然后将新结点的next存入空（NULL)。
申请新的结点，如果pphead为空地址，链表还没有结点，将新结点的地址传给pphead,新结点的地址就是头结点的地址，如果该链表中已经存在结点，定义一个指针先存放头节点的地址，然后遍历整个链表，循环寻找哪个结点的next为NULL，不是的话就将tail指向下一个结点，对应操作为tail = tail->next;结点的next为NULL，那个结点就是尾结点，找到尾结点之后将尾结点的next存入要插入新结点的地址，新结点的next已经在 BuySListNode(int x)置为空地址

3.打印链表

void  printdata(info* phead)
{
	info* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");


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

分析
文字描述：定义一个指针cur指向头结点，使用这个指针循环遍历，这个指针指向的不为空的话就继续循环，在循环中打印cur->data，对应的操作是printf(“%d->”, cur->data);打印%d后面加->是为了方便观察;然后将cur指针移动到下一个结点的位置对应操作是cur = cur->next;，继续打印。

4.头插

void pushFront(info** pphead, int x)//头插
{
	info* newnode = BuySListNode(x);//创建新结点，将新结点的地址存放在newnode指针变量中
	newnode->next = *pphead;//新结点的下一个结点应该为旧头结点的地址
	*pphead = newnode;//新头结点的地址更新为newnode指针所指向的地址


}
1
2
3
4
5
6
7
8

分析

文字描述：将创建的新结点的地址存放在newnode指针变量中，pphead为原先头结点的地址，头插一个新结点后，应该将新结点的next存放原先头结点的地址，对应操作为newnode->next = pphead;然后保存在pphead应该为新的头结点的地址，也就是newnode所指向的地址，对应操作为pphead = newnode;

5.头删

void popFront(info** pphead)
{
	info* p =(*pphead)->next;//定义指针存放头结点的下一个结点的地址
	free(*pphead);//释放头结点
	*pphead = p;//头结点地址更新为原先头结点的下一个结点的地址
}
1
2
3
4
5
6

分析：

6.尾删

void popBack(info** pphead)
{
	info* tailprev = NULL;
	info* tail = *pphead;


	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
    }
	else
	{while (tail->next != NULL)
		{
			tailprev = tail;
			tail = tail->next;
       }
		free(tail);
		tailprev->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

分析：

7.修改

info* SListFind(info* pphead, int x)
{
	info* cur = pphead;//cur指针保存pphead指针接收的地址
	while (cur)
	{
		if (cur->data == x)
		{  //cur->data==y可以将查找出来的值修改为y,不用单独写修改函数，传参也要多一个y
			return cur;//找到的话返回该结点的地址
		}
		cur = cur->next;//cur指向下一个结点的地址
    }
	return NULL;

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

分析：

8.pos指针指向结点的地址的前一个位置前插插入（随便插）

SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
{
	assert(pphead);//头结点地址不能为空
	if (pos == *pphead)//pos指针指向结点的地址为头结点，相当于头插
	{
		pushFront(*pphead, x);//调用头插函数

	}
	else
	{
		info* prev = *pphead;//定义一个prev指针，先让他保存头结点的地址
		while (prev->next != pos)//循环遍历找pos指针指向结点的前一个结点
		{
			prev = prev->next;

        }
		info* newnode=BuySListNode(x);//申请新结点，将申请好的结点地址存放在newnode指针变量里面
		prev->next = newnode;//使之前pos指针指向的结点的前一个结点的next存入插入新结点的地址，
		newnode->next = pos;//然后新结点的next存入pos指向结点的地址
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

分析：

9.删除pos位置的值

void SeqListErase(info** pphead, info* pos)
{
	if (pos == *pphead)//删除结点是否为头结点
	{
		popFront(*pphead);//头删
    }
	else
	{
		info* prev = *pphead;//定义一个prev指针，先让他存放头结点的地址
		while (prev->next != pos)//循环遍历寻找哪个结点的next存放的是pos指针指向的结点的地址
		{
			prev = prev->next;//prev指针指向下一个结点
        }
		prev->next = pos->next;//pos指针指向的结点的上一个结点的next存放pos指针指向的结点的下一个结点的地址
		free(pos);//释放掉pos指针指向的那块空间

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

分析：

10.单链表在pos位置之后插入x

void SListInsertAfter(info* pos, int x)
{
	assert(pos);//防止在空指针
	info* newnode=BuySListNode(x);//申请新结点
	newnode->next = pos->next;
	pos->next = newnode;

}
1
2
3
4
5
6
7
8

分析：
那么1，2是否可以反过来

	pos->next = newnode;
	newnode->next = pos->next;
	
1
2
3

不行，d3的地址会丢失
出现下图的情况：

11.删除pos的后一个位置

void SListEraseAfter(info* pos)
{
	assert(pos);//防止pos指向空地址
	if (pos->next == NULL)//如果pos指针指向最后一个结点
		return;//直接退出，不往下执行
	info* del = pos->next;//保存pos指针指向结点的下一个结点的地址
	pos->next = del->next;//更新pos指针指向的结点的下一个结点为pos指针指向结点下下一个结点的地址
	free(del);//释放掉保存pos指针指向结点的下一个结点的地址的空间。

}
1
2
3
4
5
6
7
8
9
10

分析：

12.完整源码

#include
#include 
#include 
typedef struct info {
	int data;
	struct info* next;

}info;
void  printdata(info* phead)
{
	info* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");


}
info* BuySListNode(int x)
{
	info* newnode = (info*)malloc(sizeof(info));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	return newnode;



}
void pushback(info** pphead, int x)//尾插
{
	info* newnode = BuySListNode(x);
	

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

		}
		tail->next = newnode;

	}













}
void pushFront(info** pphead, int x)//头插
{
	info* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;


}
void popFront(info** pphead)//头删
{
	info* p =(*pphead)->next;
	free(*pphead);
	*pphead = p;







}
void popBack(info** pphead)//尾删
{
	info* tailprev = NULL;
	info* tail = *pphead;


	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;





	}
	else
	{

		while (tail->next != NULL)
		{
			tailprev = tail;
			tail = tail->next;


		}
		free(tail);
		tailprev->next = NULL;
	}
}
info* SListFind(info* pphead, int x)//查找
{
	info* cur = pphead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;





	}
	return NULL;
}
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
{
	assert(*pphead);
	if (pos == *pphead)
	{
		pushFront(*pphead, x);

	}
	else
	{
		info* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;

        }
		info* newnode=BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;








	}










}
void SeqListErase(info** pphead, info* pos)
{
	if (pos == *pphead)
	{
		popFront(*pphead);

    
	}
	else
	{
		info* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;



		}
		prev->next = pos->next;
		free(pos);

    }





}
void SListInsertAfter(info* pos, int x)
{
	assert(pos);
	info* newnode=BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SListEraseAfter(info* pos)
{
	assert(pos);
	if (pos->next == NULL)
		return;
	info* del = pos->next;
	pos->next = del->next;
	free(del);

}

int main()
{

	info* n1 = (info*)malloc(sizeof(info));
	info* n2 = (info*)malloc(sizeof(info));
	info* n3 = (info*)malloc(sizeof(info));
	info* n4 = (info*)malloc(sizeof(info));
	assert(n1 && n2 && n3 && n4);

	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;



	printf("原链表:");
	printdata(n1);
	printf("\n");
	printf("尾插:");
	pushback(&n1, 5);
	pushback(&n1, 6);
	pushback(&n1, 7);
	pushback(&n1, 8);
	printdata(n1);
	printf("\n");
	printf("头插:");
    pushFront(&n1, 10);
	pushFront(&n1, 20);
	printdata(n1);
	printf("\n");
	printf("头删:");
	popFront(&n1);
	printdata(n1);
	printf("\n");
	printf("尾删:");
	popBack(&n1);
	popBack(&n1);
	printdata(n1);
	printf("\n");
	printf("查找到并修改:");
	SListFind(n1, 3)->data = 80;
	printdata(n1);
	printf("\n");
	printf("pos指针指向结点的地址的前一个位置前插插入:");
	SeqListInsert(&n1, n4, 100);
	printdata(n1);
	printf("\n");
	printf("删除pos位置的值:");
	SeqListErase(&n1, n4);
	printdata(n1);
	printf("\n");
	printf("单链表在pos位置之后插入x:");
	SListInsertAfter(n2, 1000);
	printdata(n1);
	printf("\n");
	printf("删除pos的后一个位置:");
	SListEraseAfter(n1);
	printdata(n1);
	printf("\n");

}
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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286

13.代码编译运行