单向链表由多个节点组成，每个节点保存数据和下一个节点的指针。它适合节点数量变化、经常在已知位置插入删除的场景；若固定数组已经够用，嵌入式项目通常优先数组，因为内存更可控、缓存局部性更好。

节点结构

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct sensor_node sensor_node_t;

struct sensor_node {
    uint8_t address;
    sensor_node_t *next;
};

typedef struct {
    sensor_node_t *head;
    size_t count;
} sensor_list_t;

结构体不能直接包含一个完整的自身对象，否则大小会无限递归；但可以包含指向同类型的指针。

遍历

sensor_node_t *sensor_list_find(sensor_list_t *list, uint8_t address)
{
    if (list == NULL) {
        return NULL;
    }

    for (sensor_node_t *node = list->head;
         node != NULL;
         node = node->next) {
        if (node->address == address) {
            return node;
        }
    }

    return NULL;
}

查找时间是 O(n)，不能因为“插入快”就认为所有操作都快。

头部插入

bool sensor_list_push_front(sensor_list_t *list,
                            sensor_node_t *node)
{
    if ((list == NULL) || (node == NULL)) {
        return false;
    }

    node->next = list->head;
    list->head = node;
    list->count++;
    return true;
}

这个版本不动态分配内存，节点由调用方提供。调用方必须保证节点在链表使用期间一直有效，并且同一节点不能同时挂入多个位置。

删除指定节点

bool sensor_list_remove(sensor_list_t *list,
                        sensor_node_t *target)
{
    if ((list == NULL) || (target == NULL)) {
        return false;
    }

    sensor_node_t **link = &list->head;

    while (*link != NULL) {
        if (*link == target) {
            *link = target->next;
            target->next = NULL;
            list->count--;
            return true;
        }
        link = &(*link)->next;
    }

    return false;
}

sensor_node_t **link 指向“当前保存节点地址的位置”，因此同一套逻辑可以处理头节点和普通节点。

删除时遍历

若循环中删除当前节点，必须先保存 next：

sensor_node_t *node = list->head;
while (node != NULL) {
    sensor_node_t *next = node->next;
    if (should_remove(node)) {
        sensor_list_remove(list, node);
    }
    node = next;
}

如果节点使用动态内存，释放后绝不能再读取 node->next。

嵌入式中的内存选择

节点数量固定：静态数组加空闲链表或对象池。
节点数量很少且配置期创建：可以动态分配，但要检查失败并明确释放。
ISR：不要临时 malloc/free，使用预分配节点并控制临界区。
高频查找：链表可能不是合适选择，可考虑数组、哈希表或索引表。

链表本身不提供线程安全。任务和 ISR 或多个任务同时改链时，需要按上下文使用临界区、Mutex 或单一拥有者任务。

常见问题排查

遍历死循环：节点被重复插入或 next 形成环。
删除头节点失败：只处理了 previous->next，没有更新 head。
删除时崩溃：释放节点后仍访问其成员。
节点偶发乱码：插入了局部变量节点，离开作用域后已失效。
长期运行内存碎片：频繁动态创建和销毁节点。

权威资料

Linux Kernel：Linked Lists in Linux

Linux 内核使用的是侵入式循环双向链表，和本文实现不同，但其结构体嵌入、初始化、遍历、删除及并发注意事项很有参考价值；官方文档也特别提醒，简单数组足够时链表往往不是最佳选择。

单向链表