16、链表模块的封装：单向链表、双向链表、循环链表的通用接口设计

链表这东西，说实话，是嵌入式开发里绕不开的数据结构。我早年做项目时，总觉得链表就是课本上的概念，直到有一次做动态内存管理模块，才发现没有一套好用的链表库，代码会写得又臭又长。

今天我们就来聊聊，怎么把单向链表、双向链表、循环链表这些“亲戚”统一封装起来。嗯，这里要注意：不是让你写三个独立的库，而是设计一套通用接口，让调用者感觉不到底层是哪种链表。

为什么需要通用接口？

你想想看，如果每个链表类型都单独写一套API，那代码里就会出现 list_add_head、dlist_add_head、clist_add_head 这种命名。调用方换个链表类型，就得改一堆函数名。我在项目中遇到过这种“命名灾难”，后来重构时花了整整两天才改完。

通用接口的核心思想是：接口与实现分离。调用者只关心“插入”、“删除”、“遍历”这些操作，不关心底层是单向还是双向。

单向链表：最基础的实现

单向链表的结构很简单，每个节点只有一个 next 指针。我习惯这样定义：

typedef struct slist_node {
    struct slist_node *next;
} slist_node_t;

typedef struct {
    slist_node_t *head;
    int size;
} slist_t;

注意，节点里没有数据字段。为什么？因为数据是调用者自己定义的。调用者可以把 slist_node_t 嵌入到自己的结构体里：

typedef struct {
    slist_node_t node;  // 链表节点
    int id;
    char name[32];
} my_data_t;

这种做法，说白了就是“侵入式链表”。节点和数据绑定在一起，而不是用 void* 去指向数据。我在项目中用过 void* 的方式，后来发现内存碎片和类型转换问题很头疼。侵入式链表虽然看起来“脏”一点，但性能更好，也更适合嵌入式环境。

双向链表：多一个指针，多一份灵活

双向链表比单向多了一个 prev 指针。删除操作时不需要遍历找前驱节点，这是它最大的优势。

typedef struct dlist_node {
    struct dlist_node *prev;
    struct dlist_node *next;
} dlist_node_t;

typedef struct {
    dlist_node_t *head;
    dlist_node_t *tail;
    int size;
} dlist_t;

我曾经在一个实时任务调度器里用了双向链表。任务需要频繁地插入和删除，单向链表每次删除都要从头遍历，导致调度延迟不稳定。换成双向链表后，延迟从平均 50μs 降到了 8μs。嗯，这个优化效果很明显。

循环链表：让遍历回到起点

循环链表的特点是最后一个节点的 next 指向头节点。双向循环链表则更灵活，头节点的 prev 指向尾节点。

typedef struct clist_node {
    struct clist_node *next;
    struct clist_node *prev;  // 双向循环
} clist_node_t;

typedef struct {
    clist_node_t *head;
    int size;
} clist_t;

循环链表最适合“轮询”场景。比如一个传感器数据采集系统，需要循环遍历所有传感器节点。用循环链表，遍历到尾部后自动回到头部，不需要额外判断。

通用接口设计：统一操作，隐藏差异

现在我们来设计一套通用接口。不管底层是单向、双向还是循环，调用者看到的都是这些函数：

接口函数	功能描述	复杂度
list_init	初始化链表	O(1)
list_add_head	在头部插入节点	O(1)
list_add_tail	在尾部插入节点	O(1) 或 O(n)
list_remove	删除指定节点	O(1) 或 O(n)
list_foreach	遍历所有节点	O(n)
list_is_empty	判断链表是否为空	O(1)

注意，list_add_tail 和 list_remove 的复杂度取决于底层实现。单向链表如果没有尾指针，尾部插入就是 O(n)。双向链表和循环链表则可以是 O(1)。

我建议在接口文档里明确标注每种实现的复杂度，让调用者自己权衡。我曾经见过一个同事，在单向链表上频繁调用 list_add_tail，结果性能惨不忍睹。后来我帮他改成双向链表，问题就解决了。

实战：实现一个通用的链表库

下面我们动手实现一个通用链表库。为了简化，我们以双向链表为基础，因为它的功能最全。单向链表和循环链表可以在此基础上裁剪。

// list.h
#ifndef LIST_H
#define LIST_H

typedef struct list_node {
    struct list_node *prev;
    struct list_node *next;
} list_node_t;

typedef struct {
    list_node_t *head;
    list_node_t *tail;
    int size;
} list_t;

// 初始化
void list_init(list_t *list);

// 头部插入
void list_add_head(list_t *list, list_node_t *node);

// 尾部插入
void list_add_tail(list_t *list, list_node_t *node);

// 删除节点
void list_remove(list_t *list, list_node_t *node);

// 遍历
#define list_foreach(list, node) \
    for (node = (list)->head; node != NULL; node = node->next)

// 判空
int list_is_empty(list_t *list);

#endif

实现文件：

// list.c
#include "list.h"

void list_init(list_t *list) {
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

void list_add_head(list_t *list, list_node_t *node) {
    node->prev = NULL;
    node->next = list->head;
    if (list->head) {
        list->head->prev = node;
    } else {
        list->tail = node;  // 空链表时，尾指针也指向新节点
    }
    list->head = node;
    list->size++;
}

void list_add_tail(list_t *list, list_node_t *node) {
    node->next = NULL;
    node->prev = list->tail;
    if (list->tail) {
        list->tail->next = node;
    } else {
        list->head = node;  // 空链表时，头指针也指向新节点
    }
    list->tail = node;
    list->size++;
}

void list_remove(list_t *list, list_node_t *node) {
    if (node->prev) {
        node->prev->next = node->next;
    } else {
        list->head = node->next;  // 删除的是头节点
    }
    if (node->next) {
        node->next->prev = node->prev;
    } else {
        list->tail = node->prev;  // 删除的是尾节点
    }
    node->prev = NULL;
    node->next = NULL;
    list->size--;
}

int list_is_empty(list_t *list) {
    return list->size == 0;
}

使用示例：

typedef struct {
    list_node_t node;
    int value;
} my_item_t;

int main() {
    list_t list;
    list_init(&list);

    my_item_t item1 = { .value = 10 };
    my_item_t item2 = { .value = 20 };

    list_add_tail(&list, &item1.node);
    list_add_tail(&list, &item2.node);

    list_node_t *pos;
    list_foreach(&list, pos) {
        my_item_t *item = (my_item_t *)pos;
        printf("value = %d\n", item->value);
    }

    return 0;
}

SVG 结构图：链表库的层次设计

避坑指南：我踩过的那些坑

我曾经在一个项目里，把链表节点和数据分开管理，用 void* 指向数据。结果每次插入都要 malloc 一个节点，再 malloc 一份数据。内存碎片严重，最后系统跑了两天就挂了。后来改成侵入式链表，节点和数据一起分配，问题就解决了。

还有一次，我在中断服务函数里调用了 list_remove，结果和主循环的遍历冲突了。嗯，这里要注意：链表操作不是线程安全的。如果要在中断里操作链表，要么关中断，要么用无锁队列。

最后，别忘了测试边界情况：空链表删除、单节点链表删除、头尾节点操作。我每次写完链表库，都会写一个单元测试用例，专门测试这些边界。别问我为什么，问就是吃过亏。

好了，链表模块的封装就聊到这里。这套通用接口设计，我在多个项目中复用，效果不错。你可以在自己的项目里试试，根据实际需求裁剪实现。

---