C 語言進階：從可變數組到鏈表的演進與完整操作實現

C 語言進階：從可變數組到鏈表的演進與完整操作實現

數組大小固定、插入刪除需搬移數據、擴容需重新分配並拷貝。鏈表通過指針串聯離散內存塊，完美解決上述痛點。本文演示可變數組封裝、鏈表基本構建、尾插法優化、搜索/刪除/清除核心操作。

一、可變數組封裝

// array.h
typedef struct { int *array; int size; } Array;
Array array_create(int init_size);
void array_free(Array *a);
int array_size(const Array *a);
int* array_at(Array *a, int index); // 自動擴容
void array_inflate(Array *a, int more_size);

關鍵點：array_at 訪問越界時自動按 BLOCK_SIZE 擴容，返回元素指針支持左值賦值。

二、鏈表節點與列表定義

// node.h
typedef struct _node {
    int value;
    struct _node *next;
} Node;

typedef struct _list { Node *head; } List;

三、尾插法構建鏈表（優化版）

void add(List *pList, int number) {
    Node *p = malloc(sizeof(Node));
    p->value = number; p->next = NULL;
    Node *last = pList->head;
    if (last) {
        while (last->next) last = last->next;
        last->next = p;
    } else {
        pList->head = p;
    }
}

四、核心操作實現

1. 搜索

Node* find(List *pList, int value) {
    for (Node *p = pList->head; p; p = p->next)
        if (p->value == value) return p;
    return NULL;
}

2. 刪除指定值節點

int delete(List *pList, int value) {
    Node *prev = NULL, *curr = pList->head;
    while (curr) {
        if (curr->value == value) {
            if (prev) prev->next = curr->next;
            else pList->head = curr->next;
            free(curr);
            return 1;
        }
        prev = curr; curr = curr->next;
    }
    return 0;
}

3. 清空鏈表

void clear(List *pList) {
    Node *curr = pList->head;
    while (curr) {
        Node *next = curr->next;
        free(curr);
        curr = next;
    }
    pList->head = NULL;
}

五、雙向鏈表與哨兵節點進階

單向鏈表刪除需維護前驅指針，雙向鏈表（prev/next）可 O(1) 刪除已知節點。引入哨兵節點（Dummy Head/Tail）可統一邊界條件，消除頭尾節點特殊判斷。

六、性能對比總結

工程建議

• 優先使用動態數組（C++ vector、C 封裝），只有頻繁中間插刪、大對象移動代價高時考慮鏈表。
• 鏈表節點內存分配可使用內存池減少 malloc/free 開銷。
• 嚴格檢查 malloc 返回值，防止空指針解引用。