您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言實現靜態鏈表與動態鏈表完整對比

編輯：關於C

鏈表是線性表鏈式存儲的兩種主要形式。本文通過完整可編譯代碼對比靜態鏈表（數組模擬、固定容量、無動態分配）與動態鏈表（堆分配、按需擴展）的結構差異、操作邏輯、適用場景，幫助開發者根據系統約束選擇最佳方案。

一、靜態鏈表：數組池 + 游標

核心思想

預分配固定大小結構體數組 Node pool[MAX_SIZE]
用數組下標 (游標) 代替指針表示後繼關係
維護備用鏈表 管理空閒節點（分配=取頭，釋放=插頭）
零 malloc/free，確定性內存佔用，適合無堆/實時/嵌入式環境

關鍵數據結構

#define MAX_SIZE 100

typedef struct {
    int data;      // 數據域
    int next;      // 指針域：存儲下一節點在 pool 中的下標，-1 表示空
} StaticNode;

StaticNode pool[MAX_SIZE];
int freeHead = 0;   // 備用鏈表頭
int listHead = -1;  // 數據鏈表頭

初始化備用鏈表

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

分配/釋放節點 (O(1))

int allocate_node() {
    if (freeHead == -1) return -1;  // 滿
    int idx = freeHead;
    freeHead = pool[freeHead].next;
    return idx;
}

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

插入/刪除/遍歷示例

// 头插法建表
void create_list(int *arr, int n) {
    for (int i = n - 1; i >= 0; --i) {
        int idx = allocate_node();
        if (idx == -1) break;
        pool[idx].data = arr[i];
        pool[idx].next = listHead;
        listHead = idx;
    }
}

// 遍歷
void traverse() {
    for (int p = listHead; p != -1; p = pool[p].next)
        printf("%d ", pool[p].data);
    puts("");
}

二、動態鏈表：堆分配 + 指針

核心思想

每個節點運行時 malloc 分配，free 釋放
指針直接關聯節點，容量僅受限於堆大小
通用性強，標準庫容器 (glib, C++ STL list) 皆採用此模型

數據結構

typedef struct DynNode {
    int data;
    struct DynNode *next;
} DynNode;

DynNode *head = NULL;

基本操作

// 尾插法建表 (保持輸入順序)
void create_list_dyn(int *arr, int n) {
    DynNode *tail = NULL;
    for (int i = 0; i < n; ++i) {
        DynNode *p = malloc(sizeof(DynNode));
        p->data = arr[i];
        p->next = NULL;
        if (!head) head = p;
        else tail->next = p;
        tail = p;
    }
}

// 遍歷
void traverse_dyn() {
    for (DynNode *p = head; p; p = p->next)
        printf("%d ", p->data);
    puts("");
}

// 銷毀
void destroy_dyn() {
    while (head) {
        DynNode *tmp = head;
        head = head->next;
        free(tmp);
    }
}

三、深度對比表

維度	靜態鏈表	動態鏈表
內存分配	編譯期/啟動期一次性分配	運行時按需 malloc/free
最大容量	固定 (MAX_SIZE)	動態 (堆限制)
內存碎片	無 (連續數組)	有 (堆碎片)
分配/釋放速度	極快 (O(1) 陣列操作)	較慢 (系統調用/鎖竞爭)
確定性	強 (硬實時友好)	弱 (不確定延遲)
跨函數共享	需全局/靜態池	自然傳遞指針
調試便利性	數組索引易觀察	指針追蹤需工具
擴展性	難 (需重編譯擴容)	自然支持

四、選型決策樹


是否有堆/動態內存支持？
├── 否 (裸機、內核、安全關鍵實時系統)
│   └── → 靜態鏈表 (或環形緩衝區)
└── 是
    ├── 最大節點數可預估且固定？
    │   ├── 是，且追求極致確定性/零碎片
    │   │   └── → 靜態鏈表
    │   └── 否
    │       └── → 動態鏈表
    └── 需要頻繁跨模塊傳遞/持久化？
        └── → 動態鏈表 (指針語義天然適配)

五、工程化增強建議

靜態鏈表：封裝為模塊，導出 list_create/capacity/size/push/pop/foreach 接口；調試版添加邊界檢查/重複釋放檢測（標記節點狀態位）
動態鏈表：使用內存池 批量分配節點 (兼顧速度/碎片)；引入哨兵節點 簡化頭尾邊界邏輯
統一抽象：定義通用迭代器接口 typedef bool (*Visitor)(void *data, void *ctx); void list_foreach(List *l, Visitor v, void *ctx); 使上層算法與存儲解耦