C 語言動態記憶體管理與鏈結串列完整實作指南

陣列大小必須編譯期確定，無法應對執行期資料量未知的情況。C 語言提供 malloc/calloc/free 三大動態記憶體函式，配合結構體指標即可構建鏈結串列、樹、圖等彈性資料結構。本文完整涵蓋動態配置 API、鏈結串列四大基本操作（建立、遍歷、插入、刪除），並提供生產級錯誤處理模式。

動態記憶體三大函式

鐵律：malloc 失敗回傳 NULL，必須檢查；free 後指標懸空，立即置 NULL 防雙重釋放。

鏈結串列節點設計

struct Node {
    int num;           // 資料域：學號
    int age;           // 資料域：年齡
    struct Node *next; // 指標域：指向下一節點
};
typedef struct Node Node;
typedef Node *List;    // 方便閱讀

四大核心操作實作

1. 建立串列（尾插法，含哨兵頭節點）

List create_list(int n) {
    List head = malloc(sizeof(Node));  // 哨兵頭節點
    if (!head) return NULL;
    head->next = NULL;
    List tail = head;

    for (int i = 0; i < n; ++i) {
        List node = malloc(sizeof(Node));
        if (!node) { destroy_list(head); return NULL; }
        printf("輸入學號 年齡: ");
        scanf("%d %d", &node->num, &node->age);
        node->next = NULL;
        tail->next = node;
        tail = node;
    }
    return head;  // 呼叫端負責銷毀
}

2. 遍歷與輸出

void print_list(List head) {
    for (List p = head->next; p; p = p->next)
        printf("學號:%d 年齡:%d\n", p->num, p->age);
}

3. 插入節點（第 pos 位置，0-based，頭節點後為 0）

bool list_insert(List head, int pos, int num, int age) {
    List prev = head;
    for (int i = 0; i < pos && prev; ++i)
        prev = prev->next;
    if (!prev) return false;  // 越界

    List node = malloc(sizeof(Node));
    if (!node) return false;
    node->num = num; node->age = age;
    node->next = prev->next;
    prev->next = node;
    return true;
}

4. 刪除節點（刪除第 pos 位置）

bool list_erase(List head, int pos) {
    List prev = head;
    for (int i = 0; i < pos && prev->next; ++i)
        prev = prev->next;
    if (!prev->next) return false;  // 越界

    List victim = prev->next;
    prev->next = victim->next;
    free(victim);
    return true;
}

5. 銷毀整個串列

void destroy_list(List head) {
    List p = head;
    while (p) {
        List tmp = p->next;
        free(p);
        p = tmp;
    }
}

完整可執行範例

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

struct Node { int num, age; struct Node *next; };
typedef struct Node Node;
typedef Node *List;

List create_list(int n);
void print_list(List head);
bool list_insert(List head, int pos, int num, int age);
bool list_erase(List head, int pos);
void destroy_list(List head);

int main() {
    int n;
    printf("輸入學生人數: ");
    scanf("%d", &n);
    List head = create_list(n);
    if (!head) { fprintf(stderr, "記憶體不足\n"); return 1; }

    printf("\n--- 初始名單 ---\n");
    print_list(head);

    list_insert(head, 1, 999, 20);  // 第 2 位插入
    printf("\n--- 插入後 ---\n");
    print_list(head);

    list_erase(head, 0);  // 刪除第 1 位
    printf("\n--- 刪除後 ---\n");
    print_list(head);

    destroy_list(head);
    return 0;
}

/* 以上函式實作同前節 */

常見錯誤與最佳實務

進階延伸

1. 雙向鏈結串列：加 prev 指標，支援 O(1) 反向遍歷與節點自我移除。
2. 循環鏈結串列：尾節點 next 指向頭節點，適用循環排程、約瑟夫問題。
3. 記憶體池：預先 malloc 大塊記憶體，自行切分節點，減少系統呼叫開銷、提升快取局部性。
4. 無鎖佇列：CAS 原子操作實現多執行緒安全串列（Michael-Scott 演算法）。

掌握 malloc/free 與鏈結串列四大操作，是從「寫出能跑的程式」邁向「寫出健壯、高效、可維護系統程式」的關鍵門檻。