C 語言通用單向鏈表庫：類型無關、回調釋放、切片操作與測試框架完整實現

編輯：關於C語言

配合上一篇 HashMap，本文提供一個生產級、類型無關、無依賴的單向鏈表實現。特點：節點數據由調用者分配/釋放（回調）、支援鍵/值/字串/子列表多種數據視圖、提供完整的增刪改查、切片、拼接、遍歷、複製操作，並附帶調試追蹤宏與完整測試用例。

核心設計

特性	實現細節
數據類型	`union { void* data; long key; const char* str; struct _list_t* list; }` 支援指針、整數鍵、字串、子列表
內存所有權	鏈表僅管理節點結構，數據內存由調用者負責，銷毀時調用 `pfcb_freedata` 回調
迭代器模式	無顯式迭代器，通過 `list_traverse(callback)` 內部迭代
調試支持	`DBG_TRACE` 宏，`_DEBUG` 開啟時輸出操作日誌
C++ 兼容	`extern "C"` 包裹，可直接在 C++ 項目中調用

頭文件精華：list.h


typedef struct _listnode_t {
    struct _listnode_t *next;
    union {
        void *data;
        struct _list_t *list;
        const char *str;
        long key;
    };
} listnode_t;

typedef struct _list_t {
    size_t size;
    listnode_t *head, *tail;
} list_t, *list_p;

typedef void (*pfunc_list_callback)(listnode_t *node); // 統一回調類型

// 核心 API
list_t *list_create();
void list_destroy(list_t *lst, pfunc_list_callback free_cb);
listnode_t *list_node_create(void *data);
listnode_t *list_key_create(long key);
void list_push_back(list_t *lst, listnode_t *node);
void list_push_front(list_t *lst, listnode_t *node);
listnode_t *list_pop_front(list_t *lst);
listnode_t *list_pop_back(list_t *lst);
void list_insert_after(list_t *lst, listnode_t *pos, listnode_t *node);
void list_insert_before(list_t *lst, listnode_t *pos, listnode_t *node);
void list_clear(list_t *lst, pfunc_list_callback free_cb);
size_t list_size(const list_t *lst);
listnode_t *list_node_at(const list_t *lst, size_t idx);
listnode_t *list_find_prev(const list_t *lst, const listnode_t *node);
listnode_t *list_slice(list_t *lst, listnode_t *begin, listnode_t *end); // 切片並從原表分離
void list_traverse(list_t *lst, pfunc_list_callback cb);
list_t *list_copy(list_t lst); // 淺拷貝結構
void list_concat(list_t *first, list_t *second);

關鍵實現片段：list.c

節點創建與銷毀（所有權清晰）


listnode_t *list_node_create(void *data) {
    listnode_t *n = malloc(sizeof(*n));
    n->next = NULL; n->data = data;
    DBG_TRACE("list_node_create\n");
    return n;
}

void list_node_free(listnode_t *node, pfunc_list_callback free_cb) {
    while (node) {
        listnode_t *next = node->next;
        if (free_cb) free_cb(node);
        free(node);
        node = next;
    }
}

切片操作：O(1) 分離子列表


// 將 [begin, end] 從原列表切離，返回切片頭，原列表自動縮減
listnode_t *list_slice(list_t *lst, listnode_t *begin, listnode_t *end) {
    listnode_t *prev = list_find_prev(lst, begin);
    if (!prev) lst->head = end->next;      // 切片含頭節點
    else prev->next = end->next;

    if (lst->tail == end) lst->tail = prev ? prev : lst->head;
    end->next = NULL;

    // 重新計算 size（簡化實現，O(n)）
    lst->size = 0;
    for (listnode_t *p = lst->head; p; p = p->next) lst->size++;
    return begin;
}

調試宏：unistd.h


#ifdef _DEBUG
#include 
static void DBG_TRACE(const char *fmt, ...) {
    va_list ap; va_start(ap, fmt); vprintf(fmt, ap); va_end(ap);
}
#else
static void DBG_TRACE(const char *fmt, ...) {}
#endif

完整測試用例：test.c


#include "list.h"
#include 
#include 
#include 

// 測試 1: 純鍵列表
void list_use_key() {
    list_t *lst = list_create();
    for (long k = 1; k <= 10; ++k) list_push_back(lst, list_key_create(k));
    list_traverse(lst, my_key_print); // 1..10
    list_pop_front(lst); list_pop_back(lst);
    list_traverse(lst, my_key_print); // 2..9
    listnode_t *slice = list_slice(lst, lst->head->next->next, list_find_prev(lst, lst->tail));
    list_node_free(slice, NULL); // 釋放切片節點
    list_traverse(lst, my_key_print); // 2,3,8,9
    list_destroy(lst, NULL);
}

// 測試 2: 攜帶動態數據的 Blob
typedef struct { char *_buff; size_t _size; } blob;
blob *blob_create(size_t n) { blob *b=malloc(sizeof(*b)); b->_buff=malloc(n); b->_size=n; return b; }
void blob_free(blob *b) { free(b->_buff); free(b); }
void blob_free_cb(listnode_t *n) { blob_free(n->data); }
void blob_print_cb(listnode_t *n) { printf("size=%zu buff=%s\n", ((blob*)n->data)->_size, ((blob*)n->data)->_buff); }

void list_use_data() {
    list_t *lst = list_create();
    for (long k = 1; k <= 10; ++k) {
        blob *b = blob_create(50);
        sprintf(b->_buff, "blob %ld", k);
        list_push_back(lst, list_node_create(b));
    }
    list_traverse(lst, blob_print_cb);
    listnode_t *n = list_pop_front(lst); list_node_free(n, blob_free_cb);
    n = list_pop_back(lst); list_node_free(n, blob_free_cb);
    list_traverse(lst, blob_print_cb);
    list_destroy(lst, blob_free_cb); // 統一釋放所有 blob
}

避坑指南

切片後必須手動釋放：list_slice 返回的切片不再被原列表管理，調用者需自行 list_node_free(slice, free_cb)。
淺拷貝陷阱：list_copy 僅複製節點指針結構，數據指針共享，若需深拷貝請自行實現。
回調簽名統一：所有回調均為 void (*)(listnode_t*)，通過 node->data/key/str 取數據，避免多態參數。
非線程安全：多執行緒環境需外部加鎖或改用無鎖隊列。