C/C++ 單鏈表完整指南：從基礎定義到工程級實現

什麼是單鏈表？

單鏈表是一種**線性動態資料結構**，由一系列**節點**組成，每個節點包含：

• 資料域：儲存實際資料 (int、結構體、void* 等)
• 指標域：指向下一個節點的位址 (next)

邏輯上連續，物理上**不連續** (堆上動態分配)，支援 O(1) 插入/刪除 (已知前驅節點)，但查詢為 O(n)。

基礎定義

// 節點結構體
typedef struct Node {
    int data;           // 資料域 (可替換為 void* 實現泛型)
    struct Node *next;  // 指標域，指向下一節點
} Node;

// 鏈表管理結構 (封裝頭指標、長度等)
typedef struct {
    Node *head;         // 虛擬頭節點 或 實際首節點
    size_t size;        // 節點數
} List;

建議使用虛擬頭節點：head 不存資料，head->next 指向首節點。插入/刪除統一邏輯，無需特判首節點。

核心操作實現

1. 初始化

bool list_init(List *list) {
    list->head = malloc(sizeof(Node));
    if (!list->head) return false;
    list->head->next = NULL;
    list->size = 0;
    return true;
}

2. 尾插法建立 (O(n) 建立，或維護 tail 指標 O(1))

bool list_push_back(List *list, int val) {
    Node *node = malloc(sizeof(Node));
    if (!node) return false;
    node->data = val;
    node->next = NULL;

    // 找到尾節點 (若維護 tail 指標可優化)
    Node *cur = list->head;
    while (cur->next) cur = cur->next;
    cur->next = node;
    list->size++;
    return true;
}

3. 頭插法 (O(1))

bool list_push_front(List *list, int val) {
    Node *node = malloc(sizeof(Node));
    if (!node) return false;
    node->data = val;
    node->next = list->head->next;
    list->head->next = node;
    list->size++;
    return true;
}

4. 指定位置插入 (0-based 索引)

bool list_insert(List *list, size_t index, int val) {
    if (index > list->size) return false;
    Node *prev = list->head;
    for (size_t i = 0; i < index; i++) prev = prev->next;
    
    Node *node = malloc(sizeof(Node));
    if (!node) return false;
    node->data = val;
    node->next = prev->next;
    prev->next = node;
    list->size++;
    return true;
}

5. 刪除指定位置節點

bool list_erase(List *list, size_t index) {
    if (index >= list->size) return false;
    Node *prev = list->head;
    for (size_t i = 0; i < index; i++) prev = prev->next;
    
    Node *del = prev->next;
    prev->next = del->next;
    free(del);
    list->size--;
    return true;
}

6. 查找 (按值/按索引)

Node* list_find(List *list, int val) {
    for (Node *p = list->head->next; p; p = p->next)
        if (p->data == val) return p;
    return NULL;
}

Node* list_at(List *list, size_t index) {
    if (index >= list->size) return NULL;
    Node *p = list->head->next;
    for (size_t i = 0; i < index; i++) p = p->next;
    return p;
}

7. 遍歷與銷毀

void list_foreach(List *list, void (*visit)(int)) {
    for (Node *p = list->head->next; p; p = p->next)
        visit(p->data);
}

void list_destroy(List *list) {
    Node *p = list->head;
    while (p) {
        Node *next = p->next;
        free(p);
        p = next;
    }
    list->head = NULL;
    list->size = 0;
}

進階主題

泛型鏈表

typedef struct GNode {
    void *data;
    struct GNode *next;
} GNode;

typedef struct {
    GNode *head;
    size_t size;
    size_t data_size; // 資料大小，用於複製
    void (*free_data)(void*); // 可選：自定義釋放
} GList;

bool glist_push_back(GList *list, const void *data) {
    GNode *node = malloc(sizeof(GNode));
    if (!node) return false;
    node->data = malloc(list->data_size);
    if (!node->data) { free(node); return false; }
    memcpy(node->data, data, list->data_size);
    node->next = NULL;
    // ... 同尾插邏輯
    return true;
}

用 void* + data_size + 複製函數實現型別無關容器。

常見面試題：反轉鏈表

// 迭代法 (三指標)
Node* reverse_iter(Node *head) {
    Node *prev = NULL, *cur = head, *next;
    while (cur) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev; // 新頭節點
}

// 遞迴法
Node* reverse_rec(Node *head) {
    if (!head || !head->next) return head;
    Node *new_head = reverse_rec(head->next);
    head->next->next = head;
    head->next = NULL;
    return new_head;
}

環檢測

bool has_cycle(Node *head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

合併兩有序鏈表

Node* merge_sorted(Node *a, Node *b) {
    Node dummy, *tail = &dummy;
    while (a && b) {
        if (a->data <= b->data) { tail->next = a; a = a->next; }
        else { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

工程級最佳實踐

陣列 vs 鏈表：選型指南

總結

單鏈表是理解指標、動態記憶體、遞迴、資料結構封裝的**最佳入門載體**。掌握：

1. 虛擬頭節點 統一邊界條件
2. 三指標法 反轉/遍歷/刪除核心模式
3. 擁有權語意：誰分配誰釋放，避免洩漏/雙重釋放
4. 泛型化思維：void* + 複製/釋放回調
5. 工程化封裝：不透明指標、錯誤碼、迭代器、文檔

從手寫 malloc/free 到設計泛型容器介面，單鏈表承載了 C 語言系統程式設計的核心功力。