C 語言實作帶頭節點單向鏈表核心操作

帶頭節點（Dummy Header）鏈表簡化邊界條件處理：頭節點不存放有效資料，head->next 指向首個資料節點，空表時指向 NULL。本文提供標準 C 實作。

資料結構定義

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node, *PNode;

1. 建立鏈表（尾插法）

PNode createLinklist(int length) {
    PNode pHead = (PNode)malloc(sizeof(Node));
    if (!pHead) return NULL;
    pHead->next = NULL;

    PNode pTail = pHead;
    for (int i = 1; i <= length; ++i) {
        PNode pNew = (PNode)malloc(sizeof(Node));
        if (!pNew) { /* 錯誤處理：釋放已配置節點 */ return pHead; }
        pNew->data = i * 2;  // 範例資料
        pNew->next = NULL;
        pTail->next = pNew;
        pTail = pNew;
    }
    return pHead;
}

2. 查找第 k 個節點（1-based）

PNode search(PNode pHead, int k) {
    if (k < 1) return NULL;
    PNode p = pHead->next;  // 跳過頭節點
    int i = 1;
    while (p && i < k) {
        p = p->next;
        ++i;
    }
    return (i == k) ? p : NULL;  // 找到返回節點指標，否則 NULL
}

3. 插入節點於第 k 位置之前

bool insert(PNode pHead, PNode pNew, int k) {
    // 尋找第 k-1 個節點（插入位置的前驅）
    PNode p = pHead;
    int i = 0;
    while (p && i < k - 1) {
        p = p->next;
        ++i;
    }
    if (!p || i != k - 1) return false;  // 位置非法

    pNew->next = p->next;
    p->next = pNew;
    return true;
}

4. 刪除第 k 個節點

bool deleteNode(PNode pHead, int k) {
    PNode p = pHead;
    int i = 0;
    while (p && i < k - 1) {
        p = p->next;
        ++i;
    }
    if (!p || !p->next || i != k - 1) return false;  // 位置非法或無該節點

    PNode temp = p->next;
    p->next = temp->next;
    free(temp);
    return true;
}

5. 列印鏈表

void printList(PNode pHead) {
    PNode p = pHead->next;
    while (p) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

6. 釋放整個鏈表

void freeList(PNode pHead) {
    PNode p = pHead->next;
    while (p) {
        PNode temp = p;
        p = p->next;
        free(temp);
    }
    free(pHead);  // 別忘了釋放頭節點
}

主程式測試

int main(void) {
    PNode head = createLinklist(5);
    printList(head);  // 2 -> 4 -> 6 -> 8 -> 10 -> NULL

    insert(head, (PNode)malloc(sizeof(Node)), 3); // 在第3個前插入
    ((PNode)head->next->next->next)->data = 99;
    printList(head);

    deleteNode(head, 2);
    printList(head);

    freeList(head);
    return 0;
}

關鍵點總結

• 頭節點統一處理「空表」與「操作首節點」的特殊情況。
• 所有操作核心：先找前驅節點，再修改 next 指標。
• 動態配置記憶體必須檢查 malloc 返回值，錯誤路徑要釋放已配置資源。
• 刪除節點後務必 free，避免記憶體洩漏。