C 語言單鏈表入門：動態節點與指標鏈接實作

C 語言單鏈表入門實作

單鏈表是動態資料結構的基礎，透過指標將分散的節點串聯。本文從零建立節點結構、串聯列印、插入操作，並對比陣列優劣勢。

節點定義：遞迴結構

typedef struct Folder {
    int level;
    char *filename;
    struct Folder *child;  // 必須用結構標籤，因類型尚未定義完成
} Folder;

struct Folder *child 形成遞迴引用，是鏈表的核心。

建立與串聯

int main() {
    Folder first = {1, "first", NULL};
    Folder second = {2, "second", NULL};
    Folder third = {3, "third", NULL};

    first.child = &second;
    second.child = &third;

    // 遍歷列印
    for (Folder *p = &first; p != NULL; p = p->child) {
        printf("%s level is %d\n", p->filename, p->level);
    }
    return 0;
}

輸出：

first level is 1
second level is 2
third level is 3

插入操作：修改指標即可

Folder fourth = {4, "fourth", NULL};
second.child = &fourth;
fourth.child = &third;
// 原: first → second → third
// 新: first → second → fourth → third

插入只需調整兩個指標，O(1) 時間，無需移動資料（陣列需 O(n) 位移）。

鏈表 vs 陣列：選擇指南

何時選鏈表？

• 頻繁頭部/中間插刪，罕見隨機存取
• 資料大小未知或劇烈變化
• 實作堆疊、佇列、哈希桶等 ADT

進階：動態分配節點 (malloc)

靜態建立節點受限於作用域，實務中配合 malloc/free 管理堆上節點，見下一篇「malloc 與 free 實戰」。