之前看到一篇单向链表的博文，代码也看着很舒服，于是乎记录下来，留给自己~，循序渐进，慢慢
延伸到真正的内核链表~（敢问路在何方?路在脚下~）
1. 简介
链表是Linux 内核中最简单，最普通的数据结构。链表是一种存放和操作可变数量元素（常称为节点）
的数据结构，链表和静态数组的不同之处在于，它所包含的元素都是动态创建并插入链表的，在编译
时不必知道具体需要创建多少个元素，另外也因为链表中每个元素的创建时间各不相同，所以它们在
内存中无须占用连续内存区。正是因为元素不连续的存放，所以各个元素需要通过某种方式被链接在
一起，于是每个元素都包含一个指向下一个元素的指针，当有元素加入链表或从链表中删除元素时，
简单调整一下节点的指针就可以了。
根据它的特性，链表可分为：单链表，双链表，单向循环链表和双向循环链表，今天总结记录的就是
最简单的单链表，
1.1 节点类型描述
1 typedef struct node_t {
2 data_t data; /* 节点数据域 */3struct node_t *next; /* 节点的后继指针域 */4 }linknode_t, *linklist_t;
另一种写法
1
struct
node_t {
2
data_t data;
3
struct node_t *next;
4}
5 typedef struct node_t linknode_t;
6 typedef struct node_t* linklist_t;
细看说明：
* linknode_t A;
* linklist_t p = &A;
*
* 结构变量A为所描述的节点，而指针变量p为指向此类型节点的指针(p值为节点的地址)
* 这样看来 linknode_t 和 linklist_t 的作用是一样的，那么为什么我们要定义两个数据类
* 型(同一种)呢? 答曰：主要为了代码的可读性，我们要求标识符要望文识义,便于理解
*
* linknode_t *pnode 指向一个节点
* linklist_t list 指向一个整体
1.2 头节点 head （~黄河之水天上来~）
在顺序存储线性表，如何表达一个空表{ }，是通过list->last = -1来表现的，所谓的空表就是
数据域为NULL，而链表有数据域和指针域，我们如何表现空链表呢？这时，就引入了头结点
的概念，头结点和其他节点数据类型一样，只是数据域为NULL，head->next = NULL，下面
我们看一个创建空链表的函数，如何利用头结点来创建一个空链表，只要头节点在，链表就还在~
1
//
创建一个空链表
2
linklist_t
3
CreateEmptyLinklist()
4
{
5
linklist_t list;
6 list = (linklist_t)malloc(sizeof(linknode_t));
7 8if(NULL != list) {
9 list->next = NULL;
10 }
1112return list;
13 }
2. 链表基本运算的相关"算法"操作 or 操刀（~烹羊宰牛且为乐，会须一饮三百杯~）
链表的运算除了上面的创建空链表，还有数据的插入，删除，查找等函数，链表的运算有各种实现方
法，如何写出一个高效的，封装性较好的函数是我们要考虑的，比如数据插入函数，我们就要尽可能
考虑所有能出现的结果，比如：1）如果需插入数据的链表是个空表；2）所插入的位置超过了链表的
长度；如果我们的函数能包含所有能出现的情况，不仅能大大提高我们的开发效率，也会减少代码的
错误率。下面看一个可用性较强的链表插入操作的函数实现~
int
InsertLinklist(linklist_t list,
int
at, data_t x)
{
linknode_t *node_prev, *node_at, *node_new;
int pos_at;
int found = 0;
if (NULL == list) return -1;
/* at must >= 0 */if (at < 0) return -1;
/*第一步、新节点分配空间*/
node_new = (linklist_t)malloc(sizeof(linknode_t));
if (NULL == node_new) {
return -1;
}
node_new->data = x; /* assigned value *//*
*节点如果插入超过链表长度的位置，会接到尾节点后面，
*这样，node_new成了尾节点，node_new->next = NULL
*/
node_new->next = NULL;
/*第二步、定位*/
node_prev = list; //跟随指针，帮助我们更好的定位
node_at = list->next; //遍历指针
pos_at = 0;
while(NULL != node_at) {
if(pos_at == at){
found = 1; //找到正确的位置，跳出循环break;
}
/* move to the next pos_at */
node_prev = node_at; //跟随指针先跳到遍历指针的位置
node_at = node_at->next; //遍历指针跳到下一个节点的位置
pos_at++;
}
/*第三步、插入*/if(found) {
/* found = 1,找到正确的位置，插入 */
node_new->next = node_at; //插入的节点next指向node_at
node_prev->next = node_new; //插入节点的前一个节点 }
else {
/*若是没找到正确的位置，即所插入位置超越了链表的长度，
*则接到尾节点的后面，同样，这样适用于{ }即空链表，这样
*我们可以建立一个空链表，利用这个函数，实现链表的初始化
*/
node_prev->next = node_new;
}
return0;
}
3. 正文开始 Demo（~与君歌一曲，请君为我倾耳听~）
listlink.h
1
#ifndef _LIST_LINK_H_
2
#define _LIST_LINK_H_
3 4 typedef int data_t;
5 6 typedef struct node_t {
7 data_t data; /* 节点数据域 */ 8struct node_t *next; /* 节点的后继指针域 */ 9 }linknode_t, *linklist_t;
10111213/* 链表操作函数*/
1415// 创建一个空链表16linklist_t CreateEmptyLinklist();
1718// 销毁链表19void DestroyLinklist(linklist_t list);
2021// 清空链表22void ClearLinklist(linklist_t list);
2324// 是否为空链表25int IsEmptyLinklist(linklist_t list);
2627// 链表长度28int LengthLinklist(linklist_t list);
2930// 获去链表节点数据31int GetLinklist(linklist_t list, int at, data_t *x);
3233// 设置链表节点数据34int SetLinklist(linklist_t list, int at, data_t x);
3536// 插入节点37int InsertLinklist(linklist_t list, int at, data_t x);
3839// 删除节点40int DeleteLinklist(linklist_t list, int at);
4142// 链表转置43linklist_t ReverseLinklist(linklist_t list);
4445// 打印链表46int Display(linklist_t list);
474849#endif /* _LIST_LINK_H_*/
listlink.c
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include "listlink.h" 4 5// 创建一个空链表 6linklist_t
7CreateEmptyLinklist()
8{
9 linklist_t list;
10 list = (linklist_t)malloc(sizeof(linknode_t));
11 12if(NULL != list) {
13 list->next = NULL;
14 }
15 16return list;
17}
18 19// 销毁链表 20void 21DestroyLinklist(linklist_t list)
22{
23if(NULL != list) {
24 ClearLinklist(list);
25free(list);
26 }
27}
28 29// 清空链表 30void 31ClearLinklist(linklist_t list)
32{
33 linknode_t *node; /* pointer to the node to be remove */ 34if(NULL == list) return;
35 36while(NULL != list->next) {
37 node = list->next;
38 list->next = node->next; //此时node->next是第二node节点元素依次往后 39free(node);
40 }
41return;
42}
43 44// 是否为空链表 45int 46IsEmptyLinklist(linklist_t list)
47{
48if(NULL != list) {
49if(NULL == list->next) // 只有头节点 50return1; // 返回1,是个空链表 51else 52return0; // 返回0,链表非空 53 54 } else 55return -1; // 返回-1, 错误的类型 56}
57 58// 链表长度 59int 60LengthLinklist(linklist_t list)
61{
62int len = 0;
63 linknode_t *node; // 遍历指针 64 65if(NULL == list) return -1;
66 67 node = list->next; // node指针指向第一个节点 68while(NULL != node) {
69 len++;
70 node = node->next;
71 }
72 73return len;
74}
75 76// 获去一个链表指定节点数据域的数据值 77int 78 GetLinklist(linklist_t list, int at, data_t *x)
79{
80 linknode_t *node; // 遍历节点的指针 81int pos; // 用于遍历比较 82 83if(NULL == list) return -1;
84/*at 必须要 >= 0*/ 85if(at < 0) return -1;
86 87/* 从第一个元素开始 */ 88 node = list->next; // node指针指向一个元素 89 pos = 0;
90while(NULL != node) {
91if(at == pos) {
92if(NULL != x)
93 *x = node->data;
94return0;
95 }
96// 下一个元素 97 node = node->next;
98 pos++;
99 }
100return -1;
101}
102103// 设置一个指定链表节点的数据域值104int105 SetLinklist(linklist_t list, int at, data_t x)
106{
107 linknode_t *node; // 遍历链表108int pos;
109int found = 0;
110111if(!list) return -1;
112/*at 必须 >= 0*/113if(at < 0) return -1;
114115/* node指针指向第一个元素 */116 node = list->next;
117 pos = 0;
118while(NULL != node) {
119if(at == pos) {
120 found = 1; // 找到了位置121 node->data = x;
122break;
123 }
124/*往后移动元素*/125 node = node->next;
126 pos++;
127 }
128if(1 == found)
129return0;
130else131return -1;
132}
133134// 插入节点135int136 InsertLinklist(linklist_t list, int at, data_t x)
137{
138/*139 * node_at and pos_at are used to locate the position of node_at.
140 * node_prev follows the node_at and always points to previous node
141 * of node_at.
142 * node_new is used to point to the new node to be inserted.
143*/144 linknode_t *node_prev, *node_at, *node_new;
145int pos_at;
146int found = 0;
147148if(NULL == list) return -1;
149150/* at 必须 >= 0 */151if(at < 0) return -1;
152153 node_new = malloc(sizeof(linknode_t));
154if(NULL == node_new)
155return -1;
156 node_new->data = x; // assigned value157 node_new->next = NULL;
158159 node_prev = list; // head160 node_at = list->next; //node_at指针指向第一元素161 pos_at = 0;
162while(NULL != node_at) {
163if(pos_at == at) {
164 found = 1; // found the node ‘at‘165break;
166 }
167/* move to the next pos_at */168 node_prev = node_at;
169 node_at = node_at->next;
170 pos_at++;
171 }
172173if(found) {
174/* insert */175 node_new->next = node_at;
176 node_prev->next = node_new;
177 } else{
178/*179 * If not found,means the provided ‘at‘
180 * exceeds the upper limit of the list, just
181 * append the new node to the end of the list
182*/183 node_prev->next = node_new;
184 }
185186return0;
187}
188189// 删除节点190int191 DeleteLinklist(linklist_t list, int at)
192{
193/*194 * node_at and pos_at are used to locate the position of node_at.
195 * node_prev follows the node_at and always points to previous node
196 * of node_at.
197*/198 linknode_t *node_prev, *node_at;
199int pos_at;
200int found = 0;
201202if(!list) return -1;
203if(at < 0) return -1;
204205 node_prev = list; // node_prev指针指向链表头206 node_at = list->next; // node_at指针指向第一元素207 pos_at = 0;
208209while(NULL != node_at) {
210if(pos_at == at) {
211// found the node ‘at‘212 found = 1;
213break;
214 }
215// move to the next pos_at216 node_prev = node_at;
217 node_at = node_at->next;
218 pos_at++;
219 }
220if(found) {
221// remove 222 node_prev->next = node_at->next;
223free(node_at);
224return0;
225 }else226return -1;
227}
228229// 链表转置230linklist_t
231ReverseLinklist(linklist_t list)
232{
233 linknode_t *node; // iterator234 linknode_t *node_prev; // previous node of iterator235 linknode_t *node_next; /* next node of iterator
236 * used to backup next of iterator
237*/238if(NULL == list) return NULL;
239 node_prev = NULL;
240 node = list->next; // node指针指向第一个元素241while(NULL != node) {
242/*243 * step1: backup node->next
244 * due to the next of iterator will be
245 * modified in step2
246*/247 node_next = node->next;
248/*249 * when iterator reaches the last node
250 * of original list, make the list head
251 * point to the last node, so the original
252 * last one becomes the first one.
253*/254if(NULL == node_next)
255 list->next = node;
256/*257 * step2: reverse the linkage between nodes
258 * make the node pointer to the previous node,
259 * not the next node
260*/261 node->next = node_prev;
262/*263 * step3: move forward
264*/265 node_prev = node;
266 node = node_next;
267 }
268269return list;
270}
271272// 打印链表273int274Display(linklist_t list)
275{
276 linknode_t *node;
277278if(NULL == list) return -1;
279280 node = list->next;
281while(node != NULL) {
282 printf(" %d ", node->data);
283 node = node->next;
284 }
285 printf("n");
286287return0;
288}
289290291int main(int argc, char *argv[])
292{
293int i;
294 data_t x;
295 linklist_t p;
296297/*创建链表*/298 p = CreateEmptyLinklist();
299 Display(p);
300 data_t a[10] = {1,3,5,7,9,11,13,15,17,19};
301302for(i = 0; i < 10; i++) {
303/*插入链表*/304 InsertLinklist(p, i, a[i]);
305 }
306 Display(p);
307308/*链表转置*/309 ReverseLinklist(p);
310/*链表长度*/311 printf("The length of the list is [%d]n", LengthLinklist(p));
312 Display(p);
313314/*获取特定节点值*/315 GetLinklist(p, 4, &x);
316 printf("The No.4 of this list is [%d]n", x);
317318/*设置特定节点的值*/319 SetLinklist(p, 4, 100);
320 GetLinklist(p, 4, &x);
321 printf("After updating! The No.4 of this list is [%d]n", x);
322 Display(p);
323324/*删除节点*/325 DeleteLinklist(p,5);
326 printf("After delete！The length of list is [%d]n", LengthLinklist(p));
327 Display(p);
328329/*清空链表*/330 ClearLinklist(p);
331if(IsEmptyLinklist(p))
332 printf("This list is empty!n");
333/*销毁链表*/334 DestroyLinklist(p);
335 printf("This list is destroyed!n");
336337338return0;
339340 }
4 . 鸣谢（你动了谁的奶酪？ ^_^）
感谢下面博主的共享，本文的基石，谢谢！！
感谢：https://blog.csdn.net/zqixiao_09/article/details/50402523
5. 后记（-- 癫狂风骚过后的落寞）
君不见，高堂明镜悲白发，朝如青丝暮成雪。
。。。。。。
五花马，千金裘，呼儿将出换美酒，与尔同消万古愁。
单向链表<-（~将进酒，杯莫停~）' ref='nofollow'>Linux C 数据结构 ->单向链表<-（~将进酒，杯莫停~）
原文：https://www.cnblogs.com/zhaoosheLBJ/p/9277744.html
【说明】：本文章由站长整理发布，文章内容不代表本站观点，如文中有侵权行为，请与本站客服联系(QQ:254677821)！