C與指標第十二章：結構體與指標實作鏈表

第十二章：使用結構與指標——鏈表實作核心

本章專注鏈表這一經典資料結構，從單向鏈表進階至雙向鏈表，展示指標操作記憶體的強大威力。

單向鏈表

每個節點包含資料欄位與指向下一節點的指標。獨立根指標指向首節點，遍歷僅能單向進行。

插入操作關鍵步驟：

1. 新節點的 link 指向其後繼節點
2. 前驅節點的 link 指向新節點

為處理插入頭節點這類特殊情況，C 語言常用「指向需修改的 link 欄位之指標」而非「指向前驅節點之指標」，統一邏輯、消除特例。

雙向鏈表

節點擁有 fwd（指向後繼）與 bwd（指向前驅）兩個指標。雙根指標分別指向首尾節點，支援雙向遍歷與中途改變方向。

插入需修改四個指標：

• 新節點的 fwd、bwd
• 前驅節點的 fwd
• 後繼節點的 bwd

警告與編程提示

警告：

1. 防止遍歷越界落至鏈表尾部之後
2. 指標操作無安全網，需格外謹慎
3. 從 if 提煉語句可能改變測試結果

編程提示：

1. 消除特殊情況，提升代碼可維護性
2. 勿輕易提煉語句，避免增加維護難度

編程實例

1. 精簡版單向鏈表插入（按序插入）

#include 

typedef struct NODE {
    struct NODE *link;
    int value;
} Node;

int sll_int(register Node **linkp, int new_value) {
    register Node *current;
    register Node *new_node;

    /* 尋找插入位置：按序遍歷直到值 >= 新值 */
    while ((current = *linkp) != NULL && current->value < new_value) {
        linkp = ¤t->link;  // 移動 linkp 指向下一個 Node 的 link
    }

    /* 分配新節點記憶體 */
    new_node = (Node *)malloc(sizeof(Node));
    if (new_node == NULL) return 0;

    new_node->value = new_value;

    /* 插入新節點 */
    new_node->link = current;
    *linkp = new_node;
    return 1;
}

2. 雙向鏈表插入操作

#include 

typedef struct NODE {
    struct NODE *fwd;
    struct NODE *bwd;
    int value;
} Node;

int dll_insert(Node *rootp, int value) {
    Node *this_node;
    Node *next_node;
    Node *new_node;

    /* 遍歷尋找插入位置 */
    for (this_node = rootp; next_node != NULL; this_node = next_node) {
        if (next_node->value == value) return 0;      // 已存在
        if (next_node->value < value) break;          // 找到位置
        next_node = next_node->fwd;
    }

    /* 分配新節點記憶體 */
    new_node = (Node *)malloc(sizeof(Node));
    if (new_node == NULL) return -1;
    new_node->value = value;

    /* 分情況插入：非尾部 vs 尾部；非頭部 vs 頭部（含空鏈表） */
    if (next_node->fwd != NULL) {
        /* 不在尾部 */
        if (this_node != rootp) {
            /* 非頭部 */
            this_node->fwd = new_node;
            next_node->bwd = new_node;
            new_node->bwd = this_node;
            new_node->fwd = next_node;
        } else {
            /* 頭部 */
            rootp->fwd = new_node;
            next_node->bwd = new_node;
            new_node->bwd = rootp;
            new_node->fwd = next_node;
        }
    } else {
        /* 在尾部 */
        if (this_node->bwd != rootp) {
            /* 非頭部 */
            new_node->fwd = NULL;
            new_node->bwd = this_node;
            this_node->fwd = new_node;
            rootp->bwd = new_node;
        } else {
            /* 頭部（空鏈表） */
            new_node->fwd = NULL;
            new_node->bwd = NULL;
            rootp->bwd = new_node;
            rootp->fwd = new_node;
        }
    }
    return 1;
}

本章不再安排習題，後續資料結構專題將提供大量代碼實戰訓練。