02-链表

概述

链表作为 C 语言中一种基础的数据结构，在平时写程序的时候用的并不多，但在操作系统里面使用的非常多。理解链表及其在 RTOS 中的应用，这对后续深入学习 RTOS 内核机制非常重要。
一、什么是链表？

链表是一种动态数据结构，由多个「节点」通过指针连接而成。每个节点包含两部分：

• 数据域：存储实际数据（如整数、结构体等）；
  
• 指针域：存储下一个（或上一个）节点的地址，用于连接节点。
  

与数组的核心区别：

• 数组需要预先分配固定大小的连续内存，大小不可动态调整；
  
• 链表的节点在内存中可以不连续，通过指针关联，大小可动态增减，插入 / 删除操作更灵活（无需移动大量元素）。
  

二、C 语言中链表的基础实现

在 C 语言中，链表通过「结构体 + 指针」实现。我们先从最基础的单链表开始讲解。
1. 定义节点结构

单链表的每个节点包含「数据」和「指向下一节点的指针」：

1. // 单链表节点结构
2. typedef struct Node {
3.     int data;               // 数据域（可替换为任意类型，如结构体）
4.     struct Node* next;      // 指针域：指向 next 节点
5. } Node;

复制代码

如果是双向链表（在RTOS 中更常用），还会增加一个「指向前一节点的指针」，方便双向遍历和操作：

1. // 双向链表节点结构
2. typedef struct DNode {
3.     int data;
4.     struct DNode* prev;     // 指向 prev 节点
5.     struct DNode* next;     // 指向 next 节点
6. } DNode;

复制代码

2. 基础操作（以单链表为例）

链表的核心操作包括：创建节点、初始化链表、插入、删除、遍历、释放内存。
（1）创建节点

通过 malloc 动态分配节点内存，并初始化数据和指针：

1. // 创建新节点（返回节点指针，失败返回NULL）
2. Node* createNode(int data) {
3.     Node* newNode = (Node*)malloc(sizeof(Node));
4.     if (newNode == NULL) {
5.         return NULL; // 内存分配失败
6.     }
7.     newNode->data = data;
8.     newNode->next = NULL; // 新节点默认指向NULL
9.     return newNode;
10. }

复制代码

（2）初始化链表（头节点）

通常用一个「头节点」作为链表的起点（头节点可不含实际数据，仅用于简化操作）：

1. // 初始化链表（返回头节点）
2. Node* initList() {
3.     Node* head = createNode(0); // 头节点数据可忽略
4.     return head;
5. }

复制代码

（3）插入节点（尾部插入为例）

在链表末尾添加新节点：

1. // 向链表尾部插入节点
2. void insertTail(Node* head, int data) {
3.     if (head == NULL) return;
4.    
5.     Node* newNode = createNode(data);
6.     if (newNode == NULL) return;
7.    
8.     // 遍历到链表尾部
9.     Node* cur = head;
10.     while (cur->next != NULL) {
11.         cur = cur->next;
12.     }
13.     // 插入新节点
14.     cur->next = newNode;
15. }

复制代码

（4）删除节点（按值删除为例）

找到目标节点并释放其内存，同时调整指针连接：

1. // 从链表中删除首个值为data的节点
2. void deleteNode(Node* head, int data) {
3.     if (head == NULL || head->next == NULL) return;
4.    
5.     Node* cur = head->next; // 当前节点
6.     Node* prev = head;      // 前序节点
7.    
8.     while (cur != NULL) {
9.         if (cur->data == data) {
10.             prev->next = cur->next; // 跳过当前节点
11.             free(cur);              // 释放内存
12.             return;
13.         }
14.         prev = cur;
15.         cur = cur->next;
16.     }
17. }

复制代码

（5）遍历链表

从头节点开始，通过指针依次访问每个节点：

1. // 遍历并打印链表所有数据
2. void traverseList(Node* head) {
3.     if (head == NULL || head->next == NULL) {
4.         printf("链表为空\n");
5.         return;
6.     }
7.    
8.     Node* cur = head->next;
9.     while (cur != NULL) {
10.         printf("%d ", cur->data);
11.         cur = cur->next;
12.     }
13.     printf("\n");
14. }

复制代码

（6）释放链表

避免内存泄漏，需要手动释放所有节点：

1. // 释放整个链表
2. void freeList(Node* head) {
3.     if (head == NULL) return;
4.    
5.     Node* cur = head;
6.     Node* temp;
7.     while (cur != NULL) {
8.         temp = cur;
9.         cur = cur->next;
10.         free(temp);
11.     }
12. }

复制代码

三、链表在 RTOS 中的核心应用

RTOS的核心是任务管理、资源调度、事件处理等，而链表是实现这些功能的「基础设施」。原因是：

• RTOS 需要频繁添加 / 删除任务、消息、定时器等对象；
  
• 链表的动态性和高效操作（尤其是双向链表的插入 / 删除）能满足实时性要求。
  

1. 任务管理（最核心的应用）

RTOS 中每个任务由「任务控制块（TCB）」描述（包含任务优先级、状态、栈指针等信息）。这些 TCB 通常通过链表组织，常见场景：

• 按任务状态分组：就绪态、阻塞态、挂起态的任务分别组成独立链表（如「就绪链表」「阻塞链表」）。
  例如：当一个任务等待信号量时，会从「就绪链表」移到「阻塞链表」；当信号量释放时，再从「阻塞链表」移回「就绪链表」。
  
• 按优先级排序：同状态的任务（如就绪态）可能按优先级组成链表，调度器只需从链表头部取最高优先级任务运行。
  

2. 消息队列

RTOS 中任务间通信常用「消息队列」，消息通常以链表形式存储：

• 新消息通过「尾部插入」加入队列；
  
• 接收消息时从「头部取出」，避免内存拷贝（直接通过指针传递）。
  这种方式比数组实现的队列更灵活（无需预设最大长度）。
  

3. 定时器管理

RTOS 中的软件定时器（如延时、定时回调）通常用链表管理：

• 所有定时器组成一个「定时器链表」，按超时时间排序；
  
• 系统时钟中断触发时，遍历链表检查是否有定时器超时，若超时则执行回调函数。
  

4. RTOS 中链表的特殊设计

为满足实时性，RTOS 的链表实现与通用链表有差异：

• 双向循环链表：几乎所有 RTOS 都用双向循环链表，每个节点有prev和next指针，且尾节点指向头节点，插入 / 删除操作可在 O (1) 时间完成。
  
• 静态内存：避免使用malloc/free（可能导致内存碎片和不确定的执行时间），而是预先从内存池分配节点，操作时仅调整指针。
  
• 宏定义简化操作：通过宏封装链表操作（如LIST_INSERT_AFTER LIST_REMOVE），减少代码冗余，保证高效性。
  

四、总结

• 链表是 C 语言中重要的动态数据结构，通过指针连接节点，适合频繁插入 / 删除的场景；
  
• 掌握链表是理解 RTOS 内核的基础 ——RTOS 用链表管理任务、消息、定时器等核心对象，其高效的操作特性是实时性的保障。
  

如下为链表操作demo例子，方便学习理解：

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
5. // 单向链表节点结构体
6. typedef struct student {
7.     // 数据域
8.     int num;        // 学号
9.     int score;      // 分数
10.     char name[20];  // 姓名
11.     // 指针域
12.     struct student *next;
13. } STU;
15. // 双向链表节点结构体
16. typedef struct double_student {
17.     // 数据域
18.     int num;        // 学号
19.     int score;      // 分数
20.     char name[20];  // 姓名
21.     // 指针域
22.     struct double_student *front;  // 保存上一个节点的地址
23.     struct double_student *next;   // 保存下一个节点的地址
24. } DSTU;
26. // ==================== 单向链表操作函数 ====================
28. // 单向链表创建（尾插法）
29. void link_creat_head(STU **p_head, STU *p_new) {
30.     STU *p_mov = *p_head;
31.     if (*p_head == NULL) {  // 当第一次加入链表为空时，head指向p_new
32.         *p_head = p_new;
33.         p_new->next = NULL;
34.     } else {  // 第二次及以后加入链表
35.         while (p_mov->next != NULL) {
36.             p_mov = p_mov->next;  // 找到原有链表的最后一个节点
37.         }
38.         p_mov->next = p_new;  // 将新申请的节点加入链表
39.         p_new->next = NULL;
40.     }
41. }
43. // 单向链表遍历
44. void link_print(STU *head) {
45.     STU *p_mov;
46.     p_mov = head;
47.     printf("\n=== 单向链表遍历结果 ===\n");
48.     while (p_mov != NULL) {
49.         printf("学号=%d 分数=%d 姓名:%s\n", p_mov->num, p_mov->score, p_mov->name);
50.         p_mov = p_mov->next;
51.     }
52.     printf("========================\n");
53. }
55. // 单向链表释放
56. void link_free(STU **p_head) {
57.     STU *pb = *p_head;
58.     while (*p_head != NULL) {
59.         pb = *p_head;
60.         *p_head = (*p_head)->next;
61.         free(pb);
62.         pb = NULL;
63.     }
64. }
66. // 按学号查找节点
67. STU *link_search_num(STU *head, int num) {
68.     STU *p_mov;
69.     p_mov = head;
70.     while (p_mov != NULL) {
71.         if (p_mov->num == num) {  // 找到了
72.             return p_mov;
73.         }
74.         p_mov = p_mov->next;
75.     }
76.     return NULL;  // 没有找到
77. }
79. // 按姓名查找节点
80. STU *link_search_name(STU *head, char *name) {
81.     STU *p_mov;
82.     p_mov = head;
83.     while (p_mov != NULL) {
84.         if (strcmp(p_mov->name, name) == 0) {  // 找到了
85.             return p_mov;
86.         }
87.         p_mov = p_mov->next;
88.     }
89.     return NULL;  // 没有找到
90. }
92. // 删除指定学号的节点
93. void link_delete_num(STU **p_head, int num) {
94.     STU *pb, *pf;
95.     pb = pf = *p_head;
96.     if (*p_head == NULL) {  // 链表为空，不用删
97.         printf("链表为空，没有您要删的节点\n");
98.         return;
99.     }
100.     while (pb->num != num && pb->next != NULL) {  // 循环找要删除的节点
101.         pf = pb;
102.         pb = pb->next;
103.     }
104.     if (pb->num == num) {  // 找到了一个节点的num和num相同
105.         if (pb == *p_head) {  // 要删除的节点是头节点
106.             *p_head = pb->next;
107.         } else {
108.             pf->next = pb->next;
109.         }
110.         free(pb);
111.         pb = NULL;
112.         printf("删除学号为 %d 的节点成功\n", num);
113.     } else {  // 没有找到
114.         printf("没有您要删除的节点\n");
115.     }
116. }
118. // 按学号顺序插入节点
119. void link_insert_num(STU **p_head, STU *p_new) {
120.     STU *pb, *pf;
121.     pb = pf = *p_head;
122.     if (*p_head == NULL) {  // 链表为空链表
123.         *p_head = p_new;
124.         p_new->next = NULL;
125.         return;
126.     }
127.     while ((p_new->num >= pb->num) && (pb->next != NULL)) {
128.         pf = pb;
129.         pb = pb->next;
130.     }
131.     if (p_new->num < pb->num) {  // 找到一个节点的num比新来的节点num大，插在pb的前面
132.         if (pb == *p_head) {  // 找到的节点是头节点，插在最前面
133.             p_new->next = *p_head;
134.             *p_head = p_new;
135.         } else {
136.             pf->next = p_new;
137.             p_new->next = pb;
138.         }
139.     } else {  // 没有找到pb的num比p_new->num大的节点，插在最后
140.         pb->next = p_new;
141.         p_new->next = NULL;
142.     }
143. }
145. // 链表排序（按学号从小到大）
146. void link_order(STU *head) {
147.     STU *pf, *pb, temp;
148.     pf = head;
149.     if (head == NULL) {
150.         printf("链表为空,不用排序\n");
151.         return;
152.     }
153.     if (head->next == NULL) {
154.         printf("只有一个节点，不用排序\n");
155.         return;
156.     }
157.     while (pf->next != NULL) {  // 以pf指向的节点为基准节点
158.         pb = pf->next;  // pb从基准元素的下个元素开始
159.         while (pb != NULL) {
160.             if (pf->num > pb->num) {
161.                 // 交换数据域，不改变指针结构
162.                 temp.num = pb->num;
163.                 temp.score = pb->score;
164.                 strcpy(temp.name, pb->name);
165.                
166.                 pb->num = pf->num;
167.                 pb->score = pf->score;
168.                 strcpy(pb->name, pf->name);
169.                
170.                 pf->num = temp.num;
171.                 pf->score = temp.score;
172.                 strcpy(pf->name, temp.name);
173.             }
174.             pb = pb->next;
175.         }
176.         pf = pf->next;
177.     }
178. }
180. // ==================== 双向链表操作函数 ====================
182. // 双向链表创建（尾插法）
183. void double_link_creat_head(DSTU **p_head, DSTU *p_new) {
184.     DSTU *p_mov = *p_head;
185.     if (*p_head == NULL) {  // 当第一次加入链表为空时，head指向p_new
186.         *p_head = p_new;
187.         p_new->front = NULL;
188.         p_new->next = NULL;
189.     } else {  // 第二次及以后加入链表
190.         while (p_mov->next != NULL) {
191.             p_mov = p_mov->next;  // 找到原有链表的最后一个节点
192.         }
193.         p_mov->next = p_new;  // 将新申请的节点加入链表
194.         p_new->front = p_mov;
195.         p_new->next = NULL;
196.     }
197. }
199. // 双向链表遍历（正向和反向）
200. void double_link_print(DSTU *head) {
201.     DSTU *pb;
202.     pb = head;
203.     printf("\n=== 双向链表正向遍历 ===\n");
204.     while (pb != NULL) {
205.         printf("学号=%d 分数=%d 姓名:%s\n", pb->num, pb->score, pb->name);
206.         if (pb->next == NULL) break;  // 记录最后一个节点
207.         pb = pb->next;
208.     }
209.     printf("\n=== 双向链表反向遍历 ===\n");
210.     while (pb != NULL) {
211.         printf("学号=%d 分数=%d 姓名:%s\n", pb->num, pb->score, pb->name);
212.         pb = pb->front;
213.     }
214.     printf("========================\n");
215. }
217. // 双向链表删除节点
218. void double_link_delete_num(DSTU **p_head, int num) {
219.     DSTU *pb, *pf;
220.     pb = *p_head;
221.     if (*p_head == NULL) {  // 链表为空，不需要删除
222.         printf("链表为空，没有您要删除的节点\n");
223.         return;
224.     }
225.     while ((pb->num != num) && (pb->next != NULL)) {
226.         pb = pb->next;
227.     }
228.     if (pb->num == num) {  // 找到了一个节点的num和num相同，删除pb指向的节点
229.         if (pb == *p_head) {  // 找到的节点是头节点
230.             if ((*p_head)->next == NULL) {  // 只有一个节点的情况
231.                 *p_head = NULL;
232.             } else {  // 有多个节点的情况
233.                 *p_head = pb->next;  // main函数中的head指向下个节点
234.                 (*p_head)->front = NULL;
235.             }
236.         } else {  // 要删的节点是其他节点
237.             if (pb->next != NULL) {  // 删除中间节点
238.                 pf = pb->front;  // 让pf指向找到的节点的前一个节点
239.                 pf->next = pb->next;  // 前一个节点的next保存后一个节点的地址
240.                 (pb->next)->front = pf;  // 后一个节点的front保存前一个节点的地址
241.             } else {  // 删除尾节点
242.                 pf = pb->front;
243.                 pf->next = NULL;
244.             }
245.         }
246.         free(pb);  // 释放找到的节点
247.         printf("删除学号为 %d 的节点成功\n", num);
248.     } else {  // 没找到
249.         printf("没有您要删除的节点\n");
250.     }
251. }
253. // ==================== 主函数和菜单系统 ====================
255. void print_menu() {
256.     printf("\n========== 链表操作演示程序 ==========\n");
257.     printf("1. 单向链表操作\n");
258.     printf("2. 双向链表操作\n");
259.     printf("0. 退出程序\n");
260.     printf("====================================\n");
261.     printf("请选择操作: ");
262. }
264. void print_single_menu() {
265.     printf("\n========== 单向链表操作菜单 ==========\n");
266.     printf("1. 创建链表\n");
267.     printf("2. 遍历链表\n");
268.     printf("3. 查找节点（按学号）\n");
269.     printf("4. 查找节点（按姓名）\n");
270.     printf("5. 插入节点（按学号排序）\n");
271.     printf("6. 删除节点（按学号）\n");
272.     printf("7. 链表排序\n");
273.     printf("8. 释放链表\n");
274.     printf("0. 返回主菜单\n");
275.     printf("====================================\n");
276.     printf("请选择操作: ");
277. }
279. void print_double_menu() {
280.     printf("\n========== 双向链表操作菜单 ==========\n");
281.     printf("1. 创建链表\n");
282.     printf("2. 遍历链表（正向+反向）\n");
283.     printf("3. 删除节点（按学号）\n");
284.     printf("0. 返回主菜单\n");
285.     printf("====================================\n");
286.     printf("请选择操作: ");
287. }
289. void single_list_operations() {
290.     STU *head = NULL, *p_new = NULL, *result = NULL;
291.     int choice, num, score, delete_num;
292.     char name[20], search_name[20];
293.    
294.     while (1) {
295.         print_single_menu();
296.         scanf("%d", &choice);
297.         
298.         switch (choice) {
299.             case 1:  // 创建链表
300.                 printf("请输入链表初始个数: ");
301.                 scanf("%d", &num);
302.                 for (int i = 0; i < num; i++) {
303.                     p_new = (STU*)malloc(sizeof(STU));
304.                     printf("请输入第%d个节点的学号、分数、姓名: ", i+1);
305.                     scanf("%d %d %s", &p_new->num, &p_new->score, p_new->name);
306.                     link_creat_head(&head, p_new);
307.                 }
308.                 printf("链表创建成功！\n");
309.                 break;
310.                
311.             case 2:  // 遍历链表
312.                 link_print(head);
313.                 break;
314.                
315.             case 3:  // 按学号查找
316.                 printf("请输入要查找的学号: ");
317.                 scanf("%d", &num);
318.                 result = link_search_num(head, num);
319.                 if (result != NULL) {
320.                     printf("找到节点: 学号=%d 分数=%d 姓名=%s\n",
321.                            result->num, result->score, result->name);
322.                 } else {
323.                     printf("未找到学号为 %d 的节点\n", num);
324.                 }
325.                 break;
326.                
327.             case 4:  // 按姓名查找
328.                 printf("请输入要查找的姓名: ");
329.                 scanf("%s", search_name);
330.                 result = link_search_name(head, search_name);
331.                 if (result != NULL) {
332.                     printf("找到节点: 学号=%d 分数=%d 姓名=%s\n",
333.                            result->num, result->score, result->name);
334.                 } else {
335.                     printf("未找到姓名为 %s 的节点\n", search_name);
336.                 }
337.                 break;
338.                
339.             case 5:  // 插入节点
340.                 p_new = (STU*)malloc(sizeof(STU));
341.                 printf("请输入要插入节点的学号、分数、姓名: ");
342.                 scanf("%d %d %s", &p_new->num, &p_new->score, p_new->name);
343.                 link_insert_num(&head, p_new);
344.                 printf("节点插入成功！\n");
345.                 break;
346.                
347.             case 6:  // 删除节点
348.                 printf("请输入要删除的学号: ");
349.                 scanf("%d", &delete_num);
350.                 link_delete_num(&head, delete_num);
351.                 break;
352.                
353.             case 7:  // 链表排序
354.                 link_order(head);
355.                 printf("链表排序完成！\n");
356.                 break;
357.                
358.             case 8:  // 释放链表
359.                 link_free(&head);
360.                 printf("链表已释放！\n");
361.                 break;
362.                
363.             case 0:  // 返回主菜单
364.                 if (head != NULL) {
365.                     link_free(&head);
366.                 }
367.                 return;
368.                
369.             default:
370.                 printf("无效选择，请重新输入！\n");
371.         }
372.     }
373. }
375. void double_list_operations() {
376.     DSTU *head = NULL, *p_new = NULL;
377.     int choice, num, delete_num;
378.    
379.     while (1) {
380.         print_double_menu();
381.         scanf("%d", &choice);
382.         
383.         switch (choice) {
384.             case 1:  // 创建链表
385.                 printf("请输入链表初始个数: ");
386.                 scanf("%d", &num);
387.                 for (int i = 0; i < num; i++) {
388.                     p_new = (DSTU*)malloc(sizeof(DSTU));
389.                     printf("请输入第%d个节点的学号、分数、姓名: ", i+1);
390.                     scanf("%d %d %s", &p_new->num, &p_new->score, p_new->name);
391.                     double_link_creat_head(&head, p_new);
392.                 }
393.                 printf("双向链表创建成功！\n");
394.                 break;
395.                
396.             case 2:  // 遍历链表
397.                 double_link_print(head);
398.                 break;
399.                
400.             case 3:  // 删除节点
401.                 printf("请输入要删除的学号: ");
402.                 scanf("%d", &delete_num);
403.                 double_link_delete_num(&head, delete_num);
404.                 break;
405.                
406.             case 0:  // 返回主菜单
407.                 // 释放双向链表内存
408.                 while (head != NULL) {
409.                     DSTU *temp = head;
410.                     head = head->next;
411.                     free(temp);
412.                 }
413.                 return;
414.                
415.             default:
416.                 printf("无效选择，请重新输入！\n");
417.         }
418.     }
419. }
421. int main() {
422.     int choice;
423.    
424.     printf("欢迎使用链表基础知识演示程序！\n");
425.     printf("本程序实现了博客中介绍的所有链表操作功能\n");
426.    
427.     while (1) {
428.         print_menu();
429.         scanf("%d", &choice);
430.         
431.         switch (choice) {
432.             case 1:
433.                 single_list_operations();
434.                 break;
435.             case 2:
436.                 double_list_operations();
437.                 break;
438.             case 0:
439.                 printf("感谢使用，程序退出！\n");
440.                 return 0;
441.             default:
442.                 printf("无效选择，请重新输入！\n");
443.         }
444.     }
445.    
446.     return 0;
447. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

这个好，看起来很实用