一、链表概述：为什么需要链表？
大家好，我是你们的嵌入式讲师。今天咱们聊聊链表。
说实话，我刚开始学C语言那会儿，觉得数组就够用了。存数据嘛，一个挨一个排好，多整齐。直到我在一个项目中，需要动态管理一批传感器节点——数量不确定，随时可能增加或删除。用数组？嗯，那可真把我坑惨了。
数组的大小是固定的。你预先分配100个元素，结果来了101个传感器，直接溢出。你分配1000个吧，平时只用几十个，内存又白白浪费。嵌入式设备的内存多宝贵啊，你想想看。
这时候，链表就派上用场了。
1.1 链表 vs 数组：一张表说清楚
| 对比项 | 数组 | 链表 |
|---|---|---|
| 内存分配 | 连续内存，大小固定 | 离散内存，动态分配 |
| 插入/删除 | 需要移动大量元素，O(n) | 只需修改指针，O(1) |
| 随机访问 | 通过下标直接访问，O(1) | 必须遍历，O(n) |
| 内存利用率 | 可能浪费（预分配过多） | 按需分配，利用率高 |
| 适用场景 | 数据量固定，频繁查询 | 数据量动态变化，频繁增删 |
说白了，数组和链表没有谁绝对好。关键看你的需求。我个人的习惯是：如果数据量在编译期就能确定，而且主要是查，那就用数组。如果数据是运行时动态增长的，或者需要频繁插入删除，那就用链表。
1.2 链表的基本概念
链表的核心思想，就是「每个节点只管两件事：存自己的数据，记下一个节点的地址」。
来看一个最简单的结构体定义：
// 单向链表节点
struct Node {
int data; // 数据域
struct Node *next; // 指针域，指向下一个节点
};这里有几个关键术语，我一个个说清楚：
- 节点（Node）：链表的基本单元。每个节点包含数据域和指针域。
- 头指针（Head Pointer）：指向链表第一个节点的指针。如果链表为空，头指针为NULL。
- 尾节点（Tail Node）：最后一个节点，它的next指针指向NULL，表示链表结束。
重要提醒：头指针不是节点，它只是一个指针变量。很多初学者会把头指针和头节点搞混。头节点是第一个实际存储数据的节点，而头指针是指向这个节点的指针。
1.3 链表的逻辑结构
为了让你更直观地理解，我画了一张图：
你看这张图，头指针指向第一个节点，第一个节点的next指向第二个节点，以此类推。最后一个节点的next指向NULL，表示「后面没人了」。
我的小技巧：调试链表程序时，我习惯先画图。把每个节点的地址、数据、next指针都画出来，对照着看代码，bug往往一眼就能发现。我曾经在一个项目中，就是因为没画图，花了两小时才找到一个指针没更新的问题。
1.4 链表的分类
链表不止一种。根据指针的指向方式，常见的有：
- 单向链表：每个节点只有一个next指针，只能从头往后遍历。
- 双向链表：每个节点有prev和next两个指针，可以向前或向后遍历。
- 循环链表：尾节点的next指向头节点，形成一个环。
咱们这门课，先从最基础的单向链表讲起。搞懂了它，其他的都是变种，一通百通。
注意：链表虽然灵活，但也不是银弹。每个节点额外存储一个指针，会占用更多内存。在嵌入式系统中，如果节点数量巨大（比如几万个），这个开销不可忽视。我曾经在一个项目中，用链表管理10万个事件记录，结果内存直接爆了。后来改用静态数组+位图标记，才解决问题。
1.5 什么时候该用链表？
我总结了几条经验，供你参考：
- 数据量不确定：运行时才知道要存多少数据，用链表动态分配。
- 频繁插入删除：在中间位置插入或删除元素，链表比数组快得多。
- 不需要随机访问：你只需要顺序遍历数据，不需要按下标直接取第N个。
- 内存碎片不是问题：如果你的系统内存管理比较健壮，或者有内存池，链表很合适。
反过来，如果你需要频繁随机访问，或者数据量很小且固定，数组可能是更好的选择。
好了，这一章我们理清了链表的基本概念。下一章，我会带你手写一个单向链表的创建和遍历。代码不多，但每一步我都会讲清楚为什么这么写。