C 語言實作靜態鏈表與動態鏈表：核心差異與完整代碼對比

編輯：關於C語言

核心概念對比

維度	靜態鏈表	動態鏈表
節點記憶體	編譯期靜態分配（全域/棧上）	執行期 `malloc` 動態分配（堆上）
最大長度	固定，受陣列大小限制	理論上僅受記憶體限制
插入/刪除	僅修改指標，無需移動資料	同，僅修改指標
記憶體釋放	不支援單節點釋放，生命週期隨程式	支援 `free` 精確釋放
適用場景	嵌入式、節點數固定、禁用動態分配環境	通用場景、節點數動態變化

靜態鏈表完整實作

#include 
#include 

#define MAX_NODES 100

typedef struct Node {
    int id;
    float score;
    int next;  // 使用陣列索引作為「指標」，-1 表示空
} Node;

Node pool[MAX_NODES];
int head = -1;
int free_list = 0; // 閒置節點鏈表頭

void init_pool() {
    for (int i = 0; i < MAX_NODES - 1; ++i) pool[i].next = i + 1;
    pool[MAX_NODES - 1].next = -1;
}

int alloc_node() {
    if (free_list == -1) return -1;
    int idx = free_list;
    free_list = pool[idx].next;
    return idx;
}

void free_node(int idx) {
    pool[idx].next = free_list;
    free_list = idx;
}

void insert_after(int prev_idx, int id, float score) {
    int idx = alloc_node();
    if (idx == -1) { puts("Pool full"); return; }
    pool[idx].id = id;
    pool[idx].score = score;
    pool[idx].next = pool[prev_idx].next;
    pool[prev_idx].next = idx;
}

void traverse(int head_idx) {
    for (int p = head_idx; p != -1; p = pool[p].next) {
        printf("id=%d score=%.1f\n", pool[p].id, pool[p].score);
    }
}

int main() {
    init_pool();
    head = alloc_node(); pool[head].id = 1; pool[head].score = 80.0; pool[head].next = -1;
    insert_after(head, 2, 85.0);
    insert_after(pool[head].next, 3, 90.0);
    traverse(head);
    return 0;
}

動態鏈表完整實作

#include 
#include 

typedef struct DNode {
    int id;
    struct DNode* next;
} DNode;

DNode* create_node(int id) {
    DNode* n = (DNode*)malloc(sizeof(DNode));
    if (!n) return NULL;
    n->id = id;
    n->next = NULL;
    return n;
}

void append(DNode** head, int id) {
    DNode* n = create_node(id);
    if (!n) return;
    if (!*head) { *head = n; return; }
    DNode* p = *head;
    while (p->next) p = p->next;
    p->next = n;
}

void traverse_dyn(DNode* head) {
    for (DNode* p = head; p; p = p->next) printf("%d ", p->id);
    puts("");
}

void destroy(DNode** head) {
    DNode* p = *head;
    while (p) {
        DNode* next = p->next;
        free(p);
        p = next;
    }
    *head = NULL;
}

int main() {
    DNode* head = NULL;
    for (int i = 1; i <= 5; ++i) append(&head, i);
    traverse_dyn(head);
    destroy(&head);
    return 0;
}