單向鏈表完整實作指南：從節點設計到增刪查改的核心操作

當資料在記憶體中不連續分佈時，單向鏈表透過「下一個節點指標」將離散節點串聯起來。相較於線性陣列，鏈表具備節點建立靈活、刪除無需移動資料、可透過遞迴或迴圈遍歷訪問等優勢（代價是隨機存取效率較低）。本文以 int 為例，完整示範單向鏈表的結構定義與八大核心操作實作。

一、節點結構定義

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

每個節點包含資料欄位 data 與指向下一節點的指標 next。

二、建立節點

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

三、刪除整條鏈表（遞迴版）

void delete_node(LINK_NODE** pNode) {
    if (NULL == pNode || NULL == *pNode) return;
    LINK_NODE** pNext = &(*pNode)->next;
    free(*pNode);
    delete_node(pNext);
}

透過二級指標修改呼叫端指標，遞迴釋放每個節點。

四、插入資料（尾端插入，遞迴實作）

STATUS _add_data(LINK_NODE** pNode, LINK_NODE* pDataNode) {
    if (NULL == *pNode) {
        *pNode = pDataNode;
        return TRUE;
    }
    return _add_data(&(*pNode)->next, pDataNode);
}

STATUS add_data(const LINK_NODE** pNode, int value) {
    if (NULL == *pNode) return FALSE;
    LINK_NODE* pDataNode = alloca_node(value);
    assert(NULL != pDataNode);
    return _add_data((LINK_NODE**)pNode, pDataNode);
}

五、刪除指定值節點

分為頭節點刪除與非頭節點刪除兩種情況，均採遞迴：

STATUS _delete_data(LINK_NODE** pNode, int value) {
    if (NULL == (*pNode)->next) return FALSE;
    LINK_NODE* pLinkNode = (*pNode)->next;
    if (value == pLinkNode->data) {
        (*pNode)->next = pLinkNode->next;
        free(pLinkNode);
        return TRUE;
    }
    return _delete_data(&(*pNode)->next, value);
}

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

六、查找資料

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

七、列印與統計

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

int count_node(const LINK_NODE* pLinkNode) {
    if (NULL == pLinkNode) return 0;
    return 1 + count_node(pLinkNode->next);
}

總結

單向鏈表雖結構簡單，但其遞迴操作模式（建立、遍歷、刪除）是掌握指標操作與遞迴思維的絕佳練習。實務上需注意記憶體洩漏與空指標防護。