C 與 Java 實現單鏈表完整對比：創建、插入、刪除操作詳解

鏈表是數據結構面試與工程實踐的高頻考點。本文以單鏈表為例，對比 C 語言（指針手動管理內存）與 Java（引用自動 GC）的實現差異，涵蓋初始化、尾插、節點刪除三大核心操作，幫你建立跨語言的數據結構思維。

一、核心結構定義對比

二、初始化：獲取頭節點

C 版：動態分配頭節點

node* init(void) {
    node* head = (node*)malloc(sizeof(node));
    if (head == NULL) return NULL; // 內存分配失敗檢查
    head->next = NULL;             // 空鏈表標記
    return head;
}

關鍵點：必須檢查 malloc 返回值；頭節點本身不存有效數據，僅作哨兵。

Java 版：直接實例化

class Node {
    Node next = null;
    int data;
    public Node(int d) { data = d; }
    // 頭節點通常直接 new Node(-1) 或類似哨兵值
}

關鍵點：無內存分配失敗憂慮（OOM 除外）；構造器封裝初始化邏輯。

三、尾部插入數據

C 版：遍歷到尾部，掛接新節點

void insert(node* head, int data) {
    if (head == NULL) return;
    node* p = head;
    while (p->next != NULL) p = p->next; // 找尾節點
    
    node* newNode = (node*)malloc(sizeof(node));
    if (newNode == NULL) return;
    newNode->data = data;
    newNode->next = NULL;
    p->next = newNode; // 掛接
}

Java 版：邏輯一致，語法更簡潔

void appendToTail(int d) {
    Node end = new Node(d);
    Node n = this; // 從當前節點（通常是頭）開始
    while (n.next != null) n = n.next;
    n.next = end;
}

異同：邏輯完全一致（O(n) 查找尾部），Java 省去內存檢查與釋放代碼。

四、刪除指定值節點

C 版：雙指針追蹤，手動 free

void delete(node* head, int data) {
    if (head == NULL) return;
    node *p = head;
    
    // 情況 1：頭節點即目標（假設頭節點存數據，或頭節點後第一個）
    if (head->data == data) { // 注意：若頭節點為哨兵，此判斷需調整
        head = head->next;
        free(p);
        return;
    }
    
    // 情況 2：中間/尾部節點
    node *q = head->next;
    while (q != NULL) {
        if (q->data == data) {
            p->next = q->next; // 斷鏈
            free(q);           // 釋放內存
            return;            // 僅刪第一個匹配
        }
        p = q;
        q = q->next;
    }
}

難點：需維護前驅指針 p 以便斷鏈；必須 free 否則內存洩漏。

Java 版：引用自動斷鏈，GC 回收

Node deleteNode(Node head, int d) {
    if (head.data == d) return head.next; // 刪頭節點
    
    Node n = head;
    while (n.next != null) {
        if (n.next.data == d) {
            n.next = n.next.next; // 斷鏈，被斷開節點自動成 GC 目標
            return head;
        }
        n = n.next;
    }
    return head; // 未找到
}

優勢：無需前驅指針變量（利用 n.next 間接訪問），無 free，代碼更安全簡潔。

五、核心差異總結

六、工程建議

1. Java 實戰：直接用 java.util.LinkedList，無需手寫。手寫僅為面試/教學理解原理。
2. C 實戰：封裝 List 抽象數據類型（ADT），隱藏指針細節，提供統一 API。
3. 通用優化：維護 tail 指針/引用，將尾插從 O(n) 降為 O(1)；引入 size 字段快速獲取長度。