單向鏈表從入門到精通：結構設計與八大核心操作全解析

當資料在記憶體中不連續分佈時，單向鏈表透過每個節點攜帶的 next 指標，將離散塊串聯成邏輯整體。相較陣列，鏈表在動態增刪、記憶體彈性上具顯著優勢，代價是隨機存取效率較低（O(N)）。本文系統梳理單向鏈表的結構設計與八大核心操作，附完整 C 語言實作。

一、節點結構設計

typedef struct _LINK_NODE {
    int data;
    struct _LINK_NODE* next;
} LINK_NODE;

二、八大核心操作實作

1. 分配節點

LINK_NODE* alloca_node(int value) {
    LINK_NODE* pNode = (LINK_NODE*)malloc(sizeof(LINK_NODE));
    assert(pNode);
    pNode->data = value;
    pNode->next = NULL;
    return pNode;
}

2. 遞迴銷毀整表

void delete_node(LINK_NODE** ppHead) {
    if (!ppHead || !*ppHead) return;
    LINK_NODE** ppNext = &(*ppHead)->next;
    free(*ppHead);
    delete_node(ppNext);
}

3. 尾插法插入（遞迴實作）

STATUS _add_data(LINK_NODE** ppCur, LINK_NODE* pNew) {
    if (!*ppCur) { *ppCur = pNew; return TRUE; }
    return _add_data(&(*ppCur)->next, pNew);
}

STATUS add_data(LINK_NODE** ppHead, int value) {
    if (!ppHead) return FALSE;
    LINK_NODE* pNew = alloca_node(value);
    assert(pNew);
    return _add_data(ppHead, pNew);
}

4. 刪除指定值節點（遞迴）

STATUS _delete_data(LINK_NODE** ppCur, int value) {
    if (!(*ppCur)->next) return FALSE;
    LINK_NODE* pTarget = (*ppCur)->next;
    if (pTarget->data == value) {
        (*ppCur)->next = pTarget->next;
        free(pTarget);
        return TRUE;
    }
    return _delete_data(&(*ppCur)->next, value);
}

STATUS delete_data(LINK_NODE** ppHead, int value) {
    if (!ppHead || !*ppHead) return FALSE;
    if ((*ppHead)->data == value) {
        LINK_NODE* pTmp = *ppHead;
        *ppHead = pTmp->next;
        free(pTmp);
        return TRUE;
    }
    return _delete_data(ppHead, value);
}

5. 遞迴查找

LINK_NODE* find_data(const LINK_NODE* pHead, int value) {
    if (!pHead) return NULL;
    if (pHead->data == value) return (LINK_NODE*)pHead;
    return find_data(pHead->next, value);
}

6. 遞迴列印

void print_node(const LINK_NODE* pHead) {
    if (pHead) {
        printf("%d\n", pHead->data);
        print_node(pHead->next);
    }
}

7. 遞迴統計節點數

int count_node(const LINK_NODE* pHead) {
    if (!pHead) return 0;
    return 1 + count_node(pHead->next);
}

三、遞迴與迭代的抉擇

本文採用遞迴風格展現鏈表操作的自相似結構，代碼簡潔優雅。但需注意：

• 遞迴深度受限於堆疊大小，超長鏈表可能堆疊溢位
• 生產環境建議改為迭代寫法，消除堆疊風險
• 尾遞迴優化可由編譯器自動轉換（需開啟優化選項）

四、鏈表 vs 陣列：選型指南

掌握單向鏈表的八大操作，是理解更複雜資料結構（雙向鏈表、循環鏈表、跳表、鄰接表）的基石。建議動手重寫迭代版本，體會指標操作的微妙之處。