C语言实现单链表，主要功能为空链表创建，链表初始化（头插法），链表元素读取，按位置插入，（有序链表）按值插入，按位置删除，按值删除，清空链表，销毁链表。
关键思路：（1）将结点创建结构体；（2）链表中添加头结点，以便统一操作；（3）使用结点一级指针和二级指针的异同点；（4）链表的最小操作单位是结点；（5）操作的起始位置是头结点还是第一个结点，及起始索引是0还是1.
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <time.h>
4
5 //涉及到结构体自引用
6 typedef struct Node{
7 int data;
8 struct Node *next;
9 }Node;
10
11 //创建空链表
12 //必须用二级指针，涉及到头指针的创建
13 int iniList(Node **List){
14 *List = (Node *)malloc(sizeof(Node));
15 if (NULL == *List){
16 return 0;
17 }
18
19 (*List)->next = NULL; //创建头结点
20 return 1;
21 }
22
23 //初始化链表(头插法)
24 //必须二级指针
25 int iniListHead(Node **List, int n){
26 *List = (Node *)malloc(sizeof(Node));
27 if (NULL == *List){
28 return 0;
29 }
30 (*List)->next = NULL;
31 srand(time(0));
32
33 int i = 0;
34 while (i < n){
35 Node *tmpNode = (Node *)malloc(sizeof(Node));
36 if (NULL == tmpNode){
37 return 0;
38 }
39 tmpNode->data = rand() % 100 + 1;
40 tmpNode->next = (*List)->next;
41 (*List)->next = tmpNode;
42
43
44 ++i;
45 }
46 return 1;
47 }
48
49 //初始化链表(尾插法)
50 //必须二级指针
51 //需要借助辅助变量pCurrent，将每次尾插的新元素当做当前元素
52 int iniListTail(Node **List, int n){
53 *List = (Node *)malloc(sizeof(Node));
54 if (NULL == *List){
55 return 0;
56 }
57 (*List)->next = NULL;
58 srand(time(0));
59
60 Node *pCurrent = *List;
61
62 int i = 0;
63 while (i < n){
64 Node *tmpNode = (Node *)malloc(sizeof(Node));
65 if (NULL == tmpNode){
66 return 0;
67 }
68 tmpNode->data = rand() % 100 + 1;
69 tmpNode->next = NULL;
70 pCurrent->next = tmpNode;
71 pCurrent = tmpNode;
72
73 ++i;
74 }
75 return 1;
76 }
77
78 //清空链表(不删除头结点)
79 //一级，二级指针均可
80 //首先找到链表地址，然后移动至表尾
81 //判断条件为指针域是否为空，即到达结尾
82 int deleteList(Node *List){
83
84 //这种方法无法删除尾结点
85 //Node *p= List;
86 //Node *q = NULL;
87 //
88 //while (p->next){
89 // q = p;
90 // free(p);
91 // p = q->next;
92 //}
93
94 Node *p = List->next;
95 Node *q = NULL;
96
97 while (p){
98 q = p->next;
99 free(p);
100 p = q;
101 }
102
103 List->next = NULL;
104 return 1;
105 }
106
107 //销毁链表
108 //必须使用二级指针，销毁头结点和头指针
109 //最后将链表头指针置空
110 int desrotyList(Node **List){
111
112 Node *p = *List;
113 Node *q = NULL;
114
115 //如果为空链表，直接删除头结点
116 //如果不是空链表，从头结点开始删除
117 while (p){
118 q = p->next;
119 free(p);
120 p = q;
121 }
122 (*List) = NULL;
123
124 //下面是从第一个结点开始删除
125 //最后释放掉头结点
126 //Node *p = (*List)->next;
127 //Node *q = NULL;
128 //
129 //while (p){
130 // q = p->next;
131 // free(p);
132 // p = q;
133 //}
134 //free(*List);
135 //(*List) = NULL;
136
137 return 1;
138 }
139
140 //链表获取元素
141 //一级，二级指针均可
142 //头结点无意义，从第一个结点开始遍历，i从1开始
143 //每次都指向下一结点，到pos-1即可
144 int getList(Node *List, int pos, int *element){
145 Node *p = List->next;
146
147 int i = 1;
148 while (p && i < pos){
149 p = p->next;
150 ++i;
151 }
152 *element = p->data;
153 return 1;
154 }
155
156 //链表按位置插入
157 //一级，二级指针均可
158 //从头结点开始，有可能插入在第一个位置,遍历从1开始
159 int insertListPos(Node *List, int pos, int value){
160 Node *p = List;
161
162 int i = 1;
163 while (p && i < pos){
164 p = p->next;
165 ++i;
166 }
167 Node *tmpNode = (Node *)malloc(sizeof(Node));
168 tmpNode->data = value;
169 tmpNode->next = p->next;
170 p->next = tmpNode;
171 return 1;
172 }
173
174 //有序链表，按值插入
175 //一二级指针均可
176 int insertListValue(Node *List, int value){
177 Node *pCur = List->next;
178 Node *pPer = List;
179 while (pCur && pCur->data < value){
180 pPer = pCur;
181 pCur = pCur->next;
182 }
183
184 Node *tmpNode = (Node *)malloc(sizeof(Node));
185 if (NULL == tmpNode){
186 return 0;
187 }
188 tmpNode->data = value;
189 tmpNode->next = pPer->next;
190 pPer->next = tmpNode;
191 return 1;
192 }
193
194 //链表按位置删除
195 //一二级指针均可
196 //记得释放结点内存
197 //如果删除第一个结点，需要操纵头结点
198 int deleteListPos(Node *List, int pos){
199 Node *p = List;
200
201 int i = 1;
202 while (p && i < pos){
203 p = p->next;
204 ++i;
205 }
206 if (NULL == p->next)
207 return 0;
208
209 Node *tmpNode = p->next;
210 p->next = p->next->next;
211
212 free(tmpNode);
213 return 1;
214 }
215
216 //链表按值删除元素
217 //一二级指针均可
218 //从第一个结点开始
219 int deleteListValue(Node *List, int value){
220 Node *pCur = List->next;
221 Node *pPer = List;
222
223 while (pCur && pCur->data != value){
224 pPer = pCur;
225 pCur = pCur->next;
226 }
227 if (pCur == NULL){ //空链表不删除任何结点
228 return 0;
229 }
230 else{
231 pPer->next = pCur->next;
232 free(pCur);
233 }
234 return 1;
235 }
236
237 int main(){
238
239 Node *testList = NULL;
240 iniList(&testList);
241 //iniListHead(&testList, 3);
242 //iniListTail(&testList, 3);
243
244
245 insertListPos(testList, 1, 2);
246 insertListPos(testList, 2, 4);
247 insertListPos(testList, 3, 5);
248 insertListPos(testList, 4, 10);
249 //insertListPos(testList, 1, 1);
250 insertListValue(testList, 1);
251
252 //deleteListPos(testList, 1);
253 //deleteListValue(testList, 4);
254
255 //deleteList(testList);
256
257 //printf("%d\n", testList);
258 //desrotyList(&testList);
259 //printf("%d\n", testList);
260
261 Node * tmpNode = testList->next;
262 while (tmpNode){
263 printf("%d\n", tmpNode->data);
264 tmpNode = tmpNode->next;
265 }
266
267 printf("----------------------\n");
268
269 int a = 0;
270 getList(testList, 2, &a);
271 printf("%d\n", a);
272
273 system("pause");
274
275 return 0;
276 }通过C++实现C语言的链表，主要区别：（1）struct可以不通过typedef，直接使用Node；（2）将malloc和free更换为new和delete
1 #include<iostream>
2 #include<ctime>
3
4 using namespace std;
5
6 struct Node{
7 int data;
8 Node *next;
9 };
10
11 //创建空链表
12 //必须用二级指针，涉及到头指针的创建
13 int iniList(Node **List){
14 *List = new Node;
15
16 (*List)->next = NULL; //创建头结点
17 return 1;
18 }
19
20 //初始化链表(头插法)
21 //必须二级指针
22 int iniListHead(Node **List, int n){
23 *List = new Node;
24
25 (*List)->next = NULL;
26 srand(time(0));
27
28 int i = 0;
29 while (i < n){
30 Node *tmpNode = new Node;
31
32 tmpNode->data = rand() % 100 + 1;
33 tmpNode->next = (*List)->next;
34 (*List)->next = tmpNode;
35
36 ++i;
37 }
38 return 1;
39 }
40
41 //初始化链表(尾插法)
42 //必须二级指针
43 //需要借助辅助变量pCurrent，将每次尾插的新元素当做当前元素
44 int iniListTail(Node **List, int n){
45 *List = new Node;
46
47 (*List)->next = NULL;
48 srand(time(0));
49
50 Node *pCurrent = *List;
51
52 int i = 0;
53 while (i < n){
54 Node *tmpNode = new Node;
55
56 tmpNode->data = rand() % 100 + 1;
57 tmpNode->next = NULL;
58 pCurrent->next = tmpNode;
59 pCurrent = tmpNode;
60
61 ++i;
62 }
63 return 1;
64 }
65
66 //清空链表(不删除头结点)
67 //一级，二级指针均可
68 //首先找到链表地址，然后移动至表尾
69 //判断条件为指针域是否为空，即到达结尾
70 int deleteList(Node *List){
71
72 //这种方法无法删除尾结点
73 //Node *p= List;
74 //Node *q = NULL;
75 //
76 //while (p->next){
77 // q = p;
78 // free(p);
79 // p = q->next;
80 //}
81
82 Node *p = List->next;
83 Node *q = NULL;
84
85 while (p){
86 q = p->next;
87 delete p;
88 p = q;
89 }
90
91 List->next = NULL;
92 return 1;
93 }
94
95 //销毁链表
96 //必须使用二级指针，销毁头结点和头指针
97 //最后将链表头指针置空
98 int desrotyList(Node **List){
99
100 Node *p = *List;
101 Node *q = NULL;
102
103 //如果为空链表，直接删除头结点
104 //如果不是空链表，从头结点开始删除
105 while (p){
106 q = p->next;
107 delete p;
108 p = q;
109 }
110 (*List) = NULL;
111
112 //下面是从第一个结点开始删除
113 //最后释放掉头结点
114 //Node *p = (*List)->next;
115 //Node *q = NULL;
116 //
117 //while (p){
118 // q = p->next;
119 // free(p);
120 // p = q;
121 //}
122 //free(*List);
123 //(*List) = NULL;
124
125 return 1;
126 }
127
128 //链表获取元素
129 //一级，二级指针均可
130 //头结点无意义，从第一个结点开始遍历，i从1开始
131 //每次都指向下一结点，到pos-1即可
132 int getList(Node *List, int pos, int *element){
133 Node *p = List->next;
134
135 int i = 1;
136 while (p && i < pos){
137 p = p->next;
138 ++i;
139 }
140 *element = p->data;
141 return 1;
142 }
143
144 //链表按位置插入
145 //一级，二级指针均可
146 //从头结点开始，有可能插入在第一个位置,遍历从1开始
147 int insertListPos(Node *List, int pos, int value){
148 Node *p = List;
149
150 int i = 1;
151 while (p && i < pos){
152 p = p->next;
153 ++i;
154 }
155 Node *tmpNode = new Node;
156 tmpNode->data = value;
157 tmpNode->next = p->next;
158 p->next = tmpNode;
159 return 1;
160 }
161
162 //有序链表，按值插入
163 //一二级指针均可
164 int insertListValue(Node *List, int value){
165 Node *pCur = List->next;
166 Node *pPer = NULL;
167 while (pCur && pCur->data < value){
168 pPer = pCur;
169 pCur = pCur->next;
170 }
171
172 Node *tmpNode = new Node;
173 if (NULL == tmpNode){
174 return 0;
175 }
176 tmpNode->data = value;
177 tmpNode->next = pPer->next;
178 pPer->next = tmpNode;
179 return 1;
180 }
181
182 //链表按位置删除
183 //一二级指针均可
184 //记得释放结点内存
185 //如果删除第一个结点，需要操纵头结点
186 int deleteListPos(Node *List, int pos){
187 Node *p = List;
188
189 int i = 1;
190 while (p && i < pos){
191 p = p->next;
192 ++i;
193 }
194 Node *tmpNode = p->next;
195 p->next = p->next->next;
196
197 delete tmpNode;
198 return 1;
199 }
200
201 //链表按值删除元素
202 //一二级指针均可
203 //从第一个结点开始
204 int deleteListValue(Node *List, int value){
205 Node *pCur = List->next;
206 Node *pPer = List;
207
208 while (pCur && pCur->data != value){
209 pPer = pCur;
210 pCur = pCur->next;
211 }
212 if (pCur == NULL){
213 return 0;
214 }
215 else{
216 pPer->next = pCur->next;
217 delete pCur;
218 }
219 return 1;
220 }结点结构体
将结点创建为结构体，其中包含数据域和指针域成员，指针域涉及结构体自引用。指针域成员之所以为结点类指针，一是为了编译时能明确结构体大小，二是为了指向下一个结点，因此初始化时不用开辟内存，只需要赋值为NULL即可。当然了，开辟内存也是可以的，这样在删除结点，及清空链表时需要记得将其释放，多此一举，不提倡。
1 //涉及到结构体自引用
2 typedef struct Node{
3 int data;
4 struct Node *next;
5 }Node;
空链表创建（二级指针）
空链表创建时，建议创建头结点。在插入和删除第一个位置的元素时，需要用结点的二级指针移动头指针，但普通结点的插入和删除并不需要移动头指针。为了便于操作的统一（指插入和删除操作），这里先创建头结点。
另外，在创建空链表时，需要传入二级指针，主要是为了操作头指针，只要涉及操作头指针的都需要使用二级指针。
1 //创建空链表
2 //必须用二级指针，涉及到头指针的创建
3 int iniList(Node **List){
4 *List = (Node *)malloc(sizeof(Node));
5 if (NULL == *List){
6 return 0;
7 }
8
9 (*List)->next = NULL; //创建头结点，将其指针域置空
10 return 1;
11 }
链表初始化（二级指针）
链表初始化，即是创建空链表，并对链表中的n个元素进行赋值。一般来说，有头插法、尾插法两种，头插法是在头结点后插入，尾插法是在链表尾插入。
头插法
头插法一般思路：（1）创建带头结点的空链表；（2）创建新结点，对新结点赋值；（3）新结点指向头结点的下一个结点，头结点指向新结点。
1 //初始化链表(头插法)
2 //必须二级指针
3 int iniListHead(Node **List, int n){
4 *List = (Node *)malloc(sizeof(Node));
5 if (NULL == *List){
6 return 0;
7 }
8 (*List)->next = NULL;
9 srand(time(0));
10
11 int i = 0;
12 while (i < n){
13 Node *tmpNode = (Node *)malloc(sizeof(Node));
14 if (NULL == tmpNode){
15 return 0;
16 }
17 tmpNode->data = rand() % 100 + 1;
18 tmpNode->next = (*List)->next;
19 (*List)->next = tmpNode;
20
21
22 ++i;
23 }
24 return 1;
25 }
尾插法
尾插法一般思路：（1）创建带头结点的空链表；（2）创建新结点，对新结点数据域赋值，指针域置空；（3）建立临时变量指向头结点，头结点指向新结点；（4）将临时变量往后移动，指向新结点。
1 //初始化链表(尾插法)
2 //必须二级指针
3 //需要借助辅助变量pCurrent，将每次尾插的新元素当做当前元素
4 int iniListTail(Node **List, int n){
5 *List = (Node *)malloc(sizeof(Node));
6 if (NULL == *List){
7 return 0;
8 }
9 (*List)->next = NULL;
10 srand(time(0));
11
12 Node *pCurrent = *List;
13
14 int i = 0;
15 while (i < n){
16 Node *tmpNode = (Node *)malloc(sizeof(Node));
17 if (NULL == tmpNode){
18 return 0;
19 }
20 tmpNode->data = rand() % 100 + 1;
21 tmpNode->next = NULL;
22 pCurrent->next = tmpNode;
23 pCurrent = tmpNode;
24
25 ++i;
26 }
27 return 1;
28 }
链表元素读取（一、二级指针）
链表元素读取，需要涉及到索引位置。我们知道头结点的数据域没有意义，因此起始位置从第一个结点开始，遍历值从1开始，到pos-1为止，此时p指向pos结点。
1 //链表获取元素
2 //一级，二级指针均可
3 //头结点无意义，从第一个结点开始遍历，i从1开始
4 //每次都指向下一结点，到pos-1即可
5 int getList(Node *List, int pos, int *element){
6 Node *p = List->next;
7
8 int i = 1;
9 while (p && i < pos){
10 p = p->next;
11 ++i;
12 }
13 *element = p->data;
14 return 1;
15 }
按位置插入（一、二级指针）
插入时，需要考虑任意位置，由于头结点的设立，我们不需要单独考虑第一个位置的结点插入。
一般思路：（1）起始位置从头结点开始，遍历值从1开始，到pos-1为止，此时指向pos-1结点；（2）创建新结点，给新结点数据域赋值；（3）新结点指向pos位置的下一结点，pos位置指向新结点。
1 //链表按位置插入
2 //一级，二级指针均可
3 //从头结点开始，有可能插入在第一个位置,遍历从1开始
4 int insertListPos(Node *List, int pos, int value){
5 Node *p = List;
6
7 int i = 1;
8 while (p && i < pos){
9 p = p->next;
10 ++i;
11 }
12 Node *tmpNode = (Node *)malloc(sizeof(Node));
13 tmpNode->data = value;
14 tmpNode->next = p->next;
15 p->next = tmpNode;
16 return 1;
17 }
有序链表按值插入（一、二级指针）
有序链表中涉及到按值插入，按值删除时，需要建立两个临时变量，不同于按位置插入，我们可以在pos前一个停止遍历，按值插入，我们需要遍历找到插入位置，操作插入位置的前一个结点。
一般思路：（1）从第一个结点开始遍历；（2）创建per变量标记当前结点的前一结点；（3）创建新结点，操作per结点；（4）常规插入操作。
1 //有序链表，按值插入
2 //一二级指针均可
3 int insertListValue(Node *List, int value){
4 Node *pCur = List->next;
5 Node *pPer = NULL;
6 while (pCur && pCur->data < value){
7 pPer = pCur;
8 pCur = pCur->next;
9 }
10
11 Node *tmpNode = (Node *)malloc(sizeof(Node));
12 if (NULL == tmpNode){
13 return 0;
14 }
15 tmpNode->data = value;
16 tmpNode->next = pPer->next;
17 pPer->next = tmpNode;
18 return 1;
19 }
按位置删除（一、二级指针）
删除时，由于头结点的设立，因此不需要特殊考虑第一个位置的操作和头指针的移动。需要设置临时变量是释放p->next后，后面还会使用p->next的结点，这样会造成访问出错。
一般思路：（1）起始位置从头结点开始，遍历从1开始，到pos-1为止，此时指向pos-1结点；（2）创建临时变量，指向pos结点；（3）将pos-1结点指向pos的下一结点，释放掉pos结点。
1 //链表按位置删除
2 //一二级指针均可
3 //记得释放结点内存
4 //如果删除第一个结点，需要操纵头结点
5 int deleteListPos(Node *List, int pos){
6 Node *p = List;
7
8 int i = 1;
9 while (p && i < pos){
10 p = p->next;
11 ++i;
12 }
13 Node *tmpNode = p->next;
14 p->next = p->next->next;
15
16 free(tmpNode);
17 return 1;
18 }
按值删除（一、二级指针）
按值删除与按值插入一样，需要两个临时变量。
一般思路：（1）起始位置从第一个结点开始，（2）设立per结点指针保存当前结点的上一结点；（3）常规删除操作。
1 //链表按值删除元素
2 //一二级指针均可
3 //从第一个结点开始
4 int deleteListValue(Node *List, int value){
5 Node *pCur = List->next;
6 Node *pPer = List;
7
8 while (pCur && pCur->data != value){
9 pPer = pCur;
10 pCur = pCur->next;
11 }
12 if (pCur == NULL){ //空链表不删除任何结点
13 return 0;
14 }
15 else{
16 pPer->next = pCur->next;
17 free(pCur);
18 }
19 return 1;
20 }
清空链表（一、二级指针）
清空链表，只是将链表中的结点删除，并释放掉结点空间，保留头结点，并将头结点的指针域置空。
一般思路：（1）起始位置从第一个结点开始；（2）设置临时变量q指向当前结点p的下一结点，释放掉当前结点p，将临时变量q赋给p；（3）最后将头结点的指针置空。
1 //清空链表(不删除头结点)
2 //一级，二级指针均可
3 //首先找到链表地址，然后移动至表尾
4 //判断条件为指针域是否为空，即到达结尾
5 int deleteList(Node *List){
6
7 //这种方法无法删除尾结点，当p->next是尾结点上一节点时，走一遍程序
8 //Node *p= List;
9 //Node *q = NULL;
10 //
11 //while (p->next){
12 // q = p;
13 // free(p);
14 // p = q->next;
15 //}
16
17 Node *p = List->next;
18 Node *q = NULL;
19
20 while (p){
21 q = p->next;
22 free(p);
23 p = q;
24 }
25
26 List->next = NULL;
27 return 1;
28 }
销毁链表（二级指针）
销毁链表，是在清空链表的基础上，删除头结点，将头指针置空，涉及到头指针的操作，需要二级指针。
思路一：（1）与清空链表操作相同，从第一个结点开始删除；（2）最后释放掉头结点，将头指针置空
思路二：（1）起始位置从头结点开始删除；（2）将头指针置空
1 //销毁链表
2 //必须使用二级指针，销毁头结点和头指针
3 //最后将链表头指针置空
4 int desrotyList(Node **List){
5
6 Node *p = *List;
7 Node *q = NULL;
8
9 //如果为空链表，直接删除头结点
10 //如果不是空链表，从头结点开始删除
11 while (p){
12 q = p->next;
13 free(p);
14 p = q;
15 }
16 (*List) = NULL;
17
18 //下面是从第一个结点开始删除
19 //最后释放掉头结点
20 //Node *p = (*List)->next;
21 //Node *q = NULL;
22 //
23 //while (p){
24 // q = p->next;
25 // free(p);
26 // p = q;
27 //}
28 //free(*List);
29 //(*List) = NULL;
30
31 return 1;
32 }二级指针和一级指针插入解析
-------------------------------------------------------------------------------------------------------------
如果上面的资料对你有启发，麻烦点个推荐，让更多人的人看到哦。
关注公众号【两猿社】，懂点互联网，懂点IC的程序猿，带你丰富项目经验哦。
