C/C++ 通用異構鏈表實現：虛擬節點、解構器回呼、型別擦除

問題

傳統鏈表要求節點型別固定。若要存放不同結構 (Struct_A, Struct_B)，需為每種型別複製插入/刪除/搜尋函數，違反 DRY 原則。

方案一：虛擬鏈表 — 節點與資料分離配置

節點結構僅含 next 指標，資料緊接在節點後配置：

typedef struct ListNode {
    struct ListNode* next;
} ListNode;

ListNode* ListAdd(ListNode* head, void* data, size_t dataSize) {
    // 分配節點 + 資料 連續記憶體
    ListNode* node = (ListNode*)malloc(sizeof(ListNode) + dataSize);
    void* dataPtr = (void*)(node + 1);  // 節點之後即資料
    memcpy(dataPtr, data, dataSize);
    node->next = head;
    return node;  // 新頭節點
}

• 優點：單一函數處理任意型別資料，無型別耦合。
• 缺點：資料含指標/資源時無法自動釋放，遍歷時需外部知曉型別以正確解讀。

方案二：帶解構器回呼的鏈表 — 管理資源生命週期

typedef void (*NodeDestructor)(void* node);  // 參數為節點指標

typedef struct ListNode {
    NodeDestructor destroy;
    struct ListNode* next;
} ListNode;

ListNode* ListAdd(ListNode* head, void* data, size_t dataSize, NodeDestructor dtor) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode) + dataSize);
    void* dataPtr = (void*)(node + 1);
    memcpy(dataPtr, data, dataSize);
    node->destroy = dtor;
    node->next = head;
    return node;
}

void ListDestroy(ListNode* head) {
    while (head) {
        ListNode* next = head->next;
        if (head->destroy) head->destroy(head);  // 釋放資料內部資源
        free(head);
        head = next;
    }
}

// 使用範例：資料含動態分配字串
typedef struct { char* str; } StringData;
void StringDataDestructor(void* node) {
    ListNode* n = (ListNode*)node;
    StringData* d = (StringData*)(n + 1);
    free(d->str);
}

ListNode* head = NULL;
StringData d1 = { strdup("Hello") };
head = ListAdd(head, &d1, sizeof(StringData), StringDataDestructor);
StringData d2 = { strdup("World") };
head = ListAdd(head, &d2, sizeof(StringData), StringDataDestructor);
ListDestroy(head);  // 正確釋放所有字串

方案三：C++ 型別擦除 — 現代 C++ 最佳實踐

使用 std::list> 或 std::vector (C++17)，或自製 type_erased_node：

// 概念示意 (非完整代碼)
class INode {
public:
    virtual ~INode() = default;
    virtual std::unique_ptr Clone() const = 0;
};

template 
class Node : public INode {
    T value;
public:
    Node(T v) : value(std::move(v)) {}
    std::unique_ptr Clone() const override {
        return std::make_unique(value);
    }
    T& Get() { return value; }
};

std::list> list;
list.push_back(std::make_unique>(42));
list.push_back(std::make_unique>("hello"));
// 遍歷需 dynamic_cast 或 Visitor 模式

比較總結

選型建議

• C 專案、極致效能、資料單純 (POD) → **虛擬節點 + 手動管理**。
• C 專案、資料含動態資源 → **解構器回呼**。
• C++ 專案、需型別安全、現代化 → **std::variant (有限型別集) 或 std::any / 型別擦除基類**。
• 單一型別 → **直接用 std::list / std::vector**。