C 語言單向非循環鏈表完整實現：LINKLIST 結構體、增刪改查排序與工程化避坑指南

編輯：關於C語言

鏈表是數據結構教學與工程實踐的基石。本文基於一個完整的 LINKLIST 結構體實現，系統講解帶頭結點的單向非循環鏈表的初始化、創建、遍歷、插入、刪除、排序等核心操作，並深度分析局部變量未初始化、格式化輸出、記憶體管理等工程級避坑要點。

數據結構設計：頭結點統一邊界條件

typedef struct Node {
    int data;
    struct Node *pNext;
} NODE;

typedef struct {
    NODE *pHead;  // 頭結點（不存數據）
    NODE *pTail;  // 尾結點指針，O(1) 尾插
    int len;      // 長度計數
} LINKLIST;

設計優勢：

頭結點哨兵：消除「空表插入/刪除首節點」的特殊邏輯
尾指針：CreatList 尾插 O(1)，無需遍歷
長度字段：ListLength O(1)，避免遍歷計數

核心操作實現解析

初始化 `InitList`

void InitList(LINKLIST *pList) {
    pList->pHead = pList->pTail = (NODE*)malloc(sizeof(NODE));
    if (!pList->pHead) { printf("內存分配失敗\n"); exit(-1); }
    pList->pTail->pNext = NULL;
    pList->len = 0;
}

關鍵： 頭尾指針初始指向同一塊哨兵節點，len=0 表示無有效數據節點。

尾插創建 `CreatList`

void CreatList(LINKLIST *pList) {
    int n; printf("輸入鏈表長度: "); scanf("%d", &n);
    for (int i=0; ipNext = NULL;
        printf("第 %d 個元素: ", i+1); scanf("%d", &pNew->data);
        pList->pTail->pNext = pNew;  // 鏈接
        pList->pTail = pNew;         // 移動尾指針
        pList->len++;
    }
}

遍歷輸出 `TraverseList`

void TraverseList(LINKLIST *pList) {
    NODE *p = pList->pHead->pNext;  // 跳過頭結點
    while (p) {
        printf("%-5d ", p->data);   // %-5d: 左對齊寬度 5
        p = p->pNext;
    }
    printf("\n");
}

格式化細節： %-5d 左對齊佔 5 字符，%5d 右對齊。對齊輸出對調試輸出可讀性至關重要。

刪除節點 `DeleteList`

bool DeleteList(LINKLIST *pList, int pos, int *pVal) {
    int i = 0;
    NODE *p = pList->pHead;
    // 定位到第 pos-1 個節點
    while (p->pNext && i < pos-1) { i++; p = p->pNext; }
    // 邊界檢查：越界或空表
    if (!p->pNext || i > pos-1) return false;

    NODE *q = p->pNext;
    *pVal = q->data;
    p->pNext = q->pNext;
    if (q == pList->pTail) pList->pTail = p; // 刪除尾節點需更新尾指針
    free(q); q = NULL;
    pList->len--;
    return true;
}

避坑點： 刪除尾節點時必須更新 pTail，否則尾指針懸空。

插入節點 `InsertList`

bool InsertList(LINKLIST *pList, int pos, int val) {
    int i = 0;
    NODE *p = pList->pHead;
    while (p && i < pos-1) { i++; p = p->pNext; }
    if (i > pos-1 || !p) return false;  // 注意：i 未初始化會導致 UB！

    NODE *pNew = (NODE*)malloc(sizeof(NODE));
    pNew->data = val;
    NODE *q = p->pNext;
    p->pNext = pNew;
    pNew->pNext = q;
    if (!q) pList->pTail = pNew;  // 插入尾部更新尾指針
    pList->len++;
    return true;
}

關鍵 Bug 修復： 原代碼 int i = 0; 註釋說「局部變量 i 沒初始化，程序運行時出錯」。C 語言局部變量不自動初始化，必須顯式 int i = 0;，這是導致隨機崩潰的經典陷阱。

冒泡排序 `SortList`

void SortList(LINKLIST *pList) {
    int len = pList->len;
    for (int i=0, p=pList->pHead->pNext; ipNext) {
        for (int j=i+1, q=p->pNext; jpNext) {
            if (p->data > q->data) {
                int tmp = p->data; p->data = q->data; q->data = tmp;
            }
        }
    }
}

注意： 此處交換的是 data 而非節點指針。對於大型結構體，應交換指針或使用合併排序 O(n log n)。

測試驗證


// 輸入: 7 個元素 99 -23 52 -77 45 38 123
// 輸出:
the list is not empty, the length of list is 7
99    -23   52    -77   45    38    123
刪除第3個元素，該元素是52
99    -23   -77   45    38    123
length: 6
在第3個元素前插入88
99    -23   88    -77   45    38    123
length: 7
排序後:
-77   -23   38    45    88    99    123
length: 7

工程化避坑總結

局部變量必須初始化：int i = 0; 而非 int i;
頭結點模式統一邊界：插入/刪除無需特判首節點
尾指針維護：尾插、尾刪、尾部插入均需更新 pTail
記憶體檢查：malloc 返回值必須檢查
釋放後置空：free(q); q = NULL; 防野指針
格式化輸出：%-5d 對齊讓調試輸出清晰可讀
const 正確性：只讀操作參數加 const（如 TraverseList(const LINKLIST*)）

現代化 C++ 封裝建議


template 
class ForwardList {
    struct Node { T data; Node* next; };
    Node* head_;  // 哨兵
    Node* tail_;
    size_t size_;
public:
    ForwardList() : head_(new Node()), tail_(head_), size_(0) {}
    ~ForwardList() { clear(); delete head_; }
    void push_back(const T& val);
    bool insert(size_t pos, const T& val);
    bool erase(size_t pos, T* out = nullptr);
    void sort();  // 合併排序 O(n log n)
    // 迭代器支援 range-based for
};

總結

單向鏈表看似簡單，實則蘊含邊界條件統一、指針操作規範、記憶體管理紀律、輸出可讀性等工程核心素養。通過 LINKLIST 這一帶頭結點、尾指針、長度計數的經典設計，我們不僅掌握了增刪改查排序的標準實現，更建立了「哨兵節點簡化邏輯、尾指針優化尾部操作、初始化防禦性編程」的工程直覺。下次手寫鏈表，請記住：先畫圖、再寫碼、每步問「空表怎麼辦？尾部怎麼辦？記憶體怎麼辦？」。