C 語言實現通用單向鏈表：輕量級、類型無關、生產級 API 設計

設計目標

在不使用 C++ STL std::list 的環境下（嵌入式、內核、老舊編譯器），實現一個類型安全性由調用者保證、極輕量、功能完整的單向鏈表庫。核心特性：

• 泛型載荷：節點攜帶 void* data 或 long key (聯合體)，支援任意數據類型。
• 零侵入：不要求數據結構內嵌節點指針（非內核 list_head 風格），節點獨立分配。
• 回調釋放：list_destroy 接受釋放回調，解決數據內存洩漏。
• 完整操作集：創建、銷毀、頭插/尾插、頭刪、索引訪問、拷貝、拼接、清空。

頭文件 list.h — API 契約

#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

#include "unistd.h" // 專案通用類型定義

// 節點結構：聯合體支援 void*/list*/string/key 多種載荷
typedef struct _listnode_t {
    struct _listnode_t *next;
    union {
        void* data;
        struct _list_t *list; // 巢狀列表指針(罕用)
        const char *str;      // 字符串直存(省一次 malloc)
        long key;             // 整數鍵值直存(省一次 malloc)
    };
} listnode_t;

// 列表頭結構
typedef struct _list_t {
    size_t size;        // 節點數
    listnode_t *head;   // 頭節點
    listnode_t *tail;   // 尾節點 (O(1) 尾插)
} list_t, *list_p;

// 節點釋放回調原型：調用者負責釋放 node->data 等業務內存
typedef void(*pfcb_list_node_free)(listnode_t* node);

// === 核心 API ===
extern void  list_append_node(list_t *in_list, listnode_t *in_node); // 尾插
extern listnode_t* list_remove_head(list_t *in_list);                // 頭刪並返回節點
extern void  list_remove_all(list_t *in_list, pfcb_list_node_free pfunc); // 清空列表(調用回調釋放節點數據)
extern list_t* list_copy(list_t in_list);                            // 淺拷貝列表頭結構(節點不複製)
extern void  list_concat(list_t *first, list_t *second);             // 拼接 second 到 first 尾部，second 置空
extern listnode_t* list_node_create(void* node_data);                // 創建攜帶 data 的節點
extern listnode_t* list_key_create(long node_key);                   // 創建攜帶 key 的節點
extern list_t* list_create();                                        // 創建空列表
extern void  list_destroy(list_t *in_list, pfcb_list_node_free pfunc); // 銷毀列表及所有節點
extern size_t list_size(const list_t* in_list);                      // 獲取大小
extern listnode_t* list_node_at(const list_t* in_list, int index);   // 0-based 索引訪問

#endif

實現文件 list.c — 核心邏輯

尾插 list_append_node

void list_append_node(list_t *in_list, listnode_t *node) {
    node->next = NULL;
    if (in_list->head) {
        in_list->tail->next = node;
        in_list->tail = node;
    } else {
        in_list->head = in_list->tail = node;
    }
    in_list->size++;
}

維護 tail 指針實現 O(1) 尾插，適合隊列、緩衝區場景。

頭刪 list_remove_head

listnode_t* list_remove_head(list_t *in_list) {
    listnode_t *node = NULL;
    if (in_list->head) {
        node = in_list->head;
        in_list->head = in_list->head->next;
        if (!in_list->head) in_list->tail = NULL; // 列表變空
        node->next = NULL; // 斷開連接
        in_list->size--;
    }
    assert(in_list->size >= 0);
    return node; // 調用者負責 free(node) 及 node->data
}

返回被移除節點所有權，不自動 free 節點內存，靈活性最高（可重用節點、轉移所有權）。

清空與銷毀 list_remove_all / list_destroy

void list_remove_all(list_t *in_list, pfcb_list_node_free pf) {
    listnode_t *node;
    while ((node = list_remove_head(in_list))) {
        if (pf) (*pf)(node); // 調用回調釋放業務數據
        free(node);          // 釋放節點本身
    }
    assert(in_list->size == 0);
}

void list_destroy(list_t *in_list, pfcb_list_node_free pf) {
    list_remove_all(in_list, pf);
    free(in_list); // 釋放列表頭結構
}

關鍵設計：分離「節點內存管理」與「業務數據管理」。庫負責節點 malloc/free，業務數據 node->data 由調用者通過回調 pf 釋放（如 free(node->data) 或遞歸銷毀子列表）。

拼接 list_concat

void list_concat(list_t *first, list_t *second) {
    if (first->head) {
        if (second->head) {
            first->tail->next = second->head;
            first->tail = second->tail;
        }
    } else {
        *first = *second; // first 為空，直接搬移頭尾指針
    }
    second->head = second->tail = NULL; // second 置空
    first->size += second->size;
}

O(1) 拼接，不複製節點，僅重鏈指針，極高效。

索引訪問 list_node_at

listnode_t* list_node_at(const list_t* in_list, int index) {
    assert(index >= 0 && index < (int)in_list->size);
    listnode_t *node = in_list->head;
    for (int i = 0; i < index; i++) node = node->next;
    return node;
}

O(N) 線性查找，單向鏈表固有限制。頻繁隨機訪問請改用陣列/跳表。

通用類型定義 unistd.h

專案統一的類型別名（uint32, size_t, BOOL 等）與標準頭文件打包，消除平台差異。

使用示例

// 業務數據結構
typedef struct { int id; char name[32]; } User;

// 釋放回調
void user_node_free(listnode_t *node) {
    free(node->data); // 釋放 User 結構體內存
}

int main() {
    list_t *users = list_create();
    for (int i = 0; i < 3; i++) {
        User *u = malloc(sizeof(User));
        u->id = i; sprintf(u->name, "User%d", i);
        list_append_node(users, list_node_create(u));
    }
    // 遍歷
    for (size_t i = 0; i < list_size(users); i++) {
        User *u = list_node_at(users, i)->data;
        printf("%d: %s\n", u->id, u->name);
    }
    list_destroy(users, user_node_free); // 完整清理
    return 0;
}

優缺點總結與適用場景

適用場景：嵌入式系統、OS 內核模塊、C 語言編譯器前端、輕量級腳本語言 VM、任何禁用 C++/STL 的項目。

擴展方向

• 雙向鏈表 (prev 指針) 支援 O(1) 尾刪、反向遍歷。
• 內核風格 list_head 侵入式設計（節點嵌入業務結構），省一次 malloc，但要求業務結構包含節點。
• 線程安全版（自旋鎖/互斥鎖內嵌 list_t）。
• 內存池分配器替換 malloc/free，消除碎片、提升實時性。