C 語言靜態鏈表與動態鏈表：原理、實現與對比

編輯：關於C語言

C 語言靜態鏈表與動態鏈表：原理、實現與對比

1. 靜態鏈表

定義

結構體包含指向自身類型的指針成員（自引用結構體）。節點為**編譯期/運行期初期固定分配**的變量（非動態分配），通過指針鏈接形成鏈表。

結構定義

struct Node {
    int data;
    struct Node *next;
};

構建示例

struct Node a, b, c, *head, *p;
a.data = 10; b.data = 20; c.data = 30;
head = &a;
a.next = &b;
b.next = &c;
c.next = NULL;

// 遍歷
p = head;
while (p) {
    printf("%d ", p->data);
    p = p->next;
}
// 輸出: 10 20 30

特點

節點數量、內存位置在程序啟動前確定（全局/棧上）。
**無法動態增刪節點**（只能修改現有節點的鏈接關係）。
適合節點數固定、不頻繁增刪、資源受限環境（無堆/不想用 malloc）。
無內存碎片、無分配失敗風險。

2. 動態鏈表

定義

節點內存由 malloc/free **運行時動態分配/釋放**，節點數量不固定，可隨時增刪。

結構定義（帶頭結點）

struct Node {
    int data;
    struct Node *next;
};
struct Node *head = NULL; // 頭指針

基本操作

// 創建節點
struct Node* create_node(int val) {
    struct Node *p = malloc(sizeof(struct Node));
    p->data = val;
    p->next = NULL;
    return p;
}

// 尾插法建表
void append(struct Node **head, int val) {
    struct Node *p = create_node(val);
    if (!*head) { *head = p; return; }
    struct Node *cur = *head;
    while (cur->next) cur = cur->next;
    cur->next = p;
}

// 遍歷
void print_list(struct Node *head) {
    while (head) { printf("%d ", head->data); head = head->next; }
    putchar('\n');
}

// 釋放整表
void free_list(struct Node *head) {
    while (head) {
        struct Node *tmp = head;
        head = head->next;
        free(tmp);
    }
}

特點

節點數量動態變化，內存按需分配。
支持任意位置插入/刪除（需維護前驅指針）。
需手動管理內存，防洩漏、防懸空指針。
適用於數據量不確定、頻繁增刪場景。

3. 核心對比

維度	靜態鏈表	動態鏈表
節點內存來源	編譯期/棧/全局區（固定）	堆（malloc/free 動態）
節點數量	固定	動態可變
增刪操作	只能修改鏈接，不能增減節點	任意增刪
內存管理	自動（編譯器/作用域）	手動 (malloc/free)
適用場景	節點固定、嵌入式無堆、教學演示	通用數據結構、數據量動態
風險	浪費內存或不夠用	內存洩漏、碎片、分配失敗

4. 進階：靜態鏈表模擬動態分配（數組實現）

在無 malloc 環境（如某些單片機），可用結構體數組 + 索引模擬動態鏈表：

#define MAX_NODES 100
struct StaticNode {
    int data;
    int next; // 索引，-1 表示 NULL
} nodes[MAX_NODES];
int free_list = 0; // 空閒鏈表頭
int head = -1;     // 數據鏈表頭

// 初始化空閒鏈表
void init_pool() {
    for (int i = 0; i < MAX_NODES-1; i++) nodes[i].next = i+1;
    nodes[MAX_NODES-1].next = -1;
}

// 申請節點
int alloc_node() {
    if (free_list == -1) return -1;
    int idx = free_list;
    free_list = nodes[free_list].next;
    return idx;
}

// 歸還節點
void free_node(int idx) {
    nodes[idx].next = free_list;
    free_list = idx;
}

此法結合了「靜態內存安全」與「動態增刪靈活」，是嵌入式系統常用技巧。