C語言實現單鏈表：從頭文件設計到核心操作的完整工程實踐

項目架構：模塊化設計思想

本實現採用「頭文件聲明 + 源文件實現」的經典模塊化結構，將數據結構定義、接口聲明與具體算法分離，便於維護與復用。核心數據類型抽象為 datatype（默認 int），通過宏切換可適配不同業務場景。

核心數據結構定義

// function.h
#define true 1
#define false 0

typedef int datatype;  // 業務數據類型抽象層

// 單鏈表節點：數據域 + 指針域
typedef struct LNode {
    datatype data;
    struct LNode *next;
} LNode, *LinkList;  // LinkList 本質是指向頭節點的指針

採用帶頭節點設計：頭節點不存儲有效數據，next 指向首個數據節點。這統一了空表、插入刪除頭節點等邊界條件處理，代碼更簡潔健壯。

核心接口設計

關鍵算法深度解析

1. 統一的查找前驅節點模式

插入、刪除、查找均基於「定位第 i-1 個節點」：

LinkList p = head;  // 從頭節點開始
int j = 0;
while (p && j < i-1) { p = p->next; j++; }
if (!p || j > i-1) return false;  // 位置非法
// p 現在指向第 i-1 個節點，為操作目標節點的前驅

此模式將「找節點」與「做操作」解耦，邏輯清晰，邊界處理統一。

2. 插入操作：三步走戰略

LinkList newNode = (LinkList)malloc(sizeof(LNode));
newNode->data = e;           // 1. 填充數據
newNode->next = p->next;     // 2. 新節點指向後繼
p->next = newNode;           // 3. 前驅指向新節點

順序不可顛倒，否則會丟失後續鏈表。

3. 刪除操作：斷鏈釋放

LinkList q = p->next;        // 待刪節點
*e = q->data;                // 保存數據
p->next = q->next;           // 斷鏈
free(q);                     // 釋放內存

4. 有序表合併：歸併排序核心邏輯

void MergeList(LinkList A, LinkList B, LinkList C) {
    C = A;  // 復用 A 的頭節點作為合併表頭
    LinkList pa = A->next, pb = B->next, pc = C;
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa; pc = pa; pa = pa->next;
        } else {
            pc->next = pb; pc = pb; pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;  // 掛載剩餘段
    free(B);  // 釋放 B 的頭節點
}

時間複雜度 O(m+n)，空間複雜度 O(1)，就地合併，極致高效。

5. 銷毀操作：逐節點釋放

void ListDestroy(LinkList head) {
    while (head) {
        LinkList p = head;
        head = head->next;
        free(p);
    }
}

注意：頭節點也需釋放，調用後原頭指針成為懸空指針，上層應置 NULL。

工程化細節與避坑指南

• 類型抽象：typedef int datatype 便於後期擴展為 float、結構體等
• 錯誤碼語義化：統一返回 true/false，避免魔術數字
• const 正確性：只讀操作（如 ListPrint、GetElem）參數應加 const LinkList
• 內存安全：malloc 失敗檢查、釋放後置空、防止重複釋放
• 調試友好：ListPrint 格式化輸出，便於單元測試驗證

擴展方向

1. 雙向鏈表：添加 prev 指針，支持反向遍歷、O(1) 刪除已知節點
2. 循環鏈表：尾節點指向頭節點，適用於循環調度、Josephus 問題
3. 泛型化：節點存 void* + 類型標識 + 操作函數指針，實現真正泛型容器
4. 線程安全：引入讀寫鎖，支持多線程並發訪問

這份實現雖屬教學級，但體現了C語言數據結構工程化的核心原則：抽象封裝、邊界統一、內存規範、接口正交。掌握此模式，可快速構建生產級容器組件。