C 語言單向鏈表實作：頭插法與尾插法完整教學

C 語言單向鏈表實作：頭插法與尾插法完整教學

鏈表是資料結構基石，掌握其節點管理、記憶體分配與插入刪除邏輯，是 C 語言進階的必經之路。本文從零實作單向鏈表，詳細解析頭插法（逆序建立）與尾插法（順序建立）的核心差異，提供可直接編譯執行的完整程式碼。

節點結構定義

struct Node {
    int data;           // 資料域
    struct Node *next;  // 指標域，指向下一個節點
};

核心函式實作

1. 節點建立（含記憶體初始化）

struct Node* create_node(int data) {
    struct Node *p = (struct Node*)malloc(sizeof(struct Node));
    if (NULL == p) {
        fprintf(stderr, "記憶體分配失敗\n");
        return NULL;
    }
    memset(p, 0, sizeof(struct Node));  // 清零殘留資料
    p->data = data;
    p->next = NULL;
    return p;
}

2. 尾插法：維護尾指標 O(1) 插入

void insert_tail(struct Node *head, struct Node *new_node) {
    struct Node *p = head;
    while (p->next != NULL) {  // 遍歷尋找尾節點
        p = p->next;
    }
    p->next = new_node;        // 尾節點指向新節點
    new_node->next = NULL;
}

優化建議：若頻繁尾插，可在結構體額外維護 tail 指標，避免每次遍歷，將時間複雜度從 O(n) 降為 O(1)。

3. 頭插法：新節點插入頭節點之後

void insert_head(struct Node *head, struct Node *new_node) {
    if (head->next == NULL) {      // 空鏈表
        head->next = new_node;
        new_node->next = NULL;
    } else {                       // 非空鏈表
        new_node->next = head->next;
        head->next = new_node;
    }
}

完整可執行程式碼

#include 
#include 
#include 

struct Node {
    int data;
    struct Node *next;
};

struct Node* create_node(int data) {
    struct Node *p = (struct Node*)malloc(sizeof(struct Node));
    if (!p) { perror("malloc"); return NULL; }
    memset(p, 0, sizeof(struct Node));
    p->data = data;
    p->next = NULL;
    return p;
}

void insert_tail(struct Node *head, struct Node *new_node) {
    struct Node *p = head;
    while (p->next) p = p->next;
    p->next = new_node;
    new_node->next = NULL;
}

void insert_head(struct Node *head, struct Node *new_node) {
    new_node->next = head->next;
    head->next = new_node;
}

void print_list(const char *title, struct Node *head) {
    printf("=== %s ===\n", title);
    struct Node *p = head->next;
    int idx = 1;
    while (p) {
        printf("node %d: %d\n", idx++, p->data);
        p = p->next;
    }
}

void free_list(struct Node *head) {
    struct Node *p = head;
    while (p) {
        struct Node *tmp = p;
        p = p->next;
        free(tmp);
    }
}

int main(void) {
    // 頭插法測試：輸出順序為 4 3 2 1 (逆序)
    struct Node *head1 = create_node(0);  // 虛擬頭節點
    for (int i = 1; i <= 4; i++)
        insert_head(head1, create_node(i));
    print_list("頭插法結果 (逆序)", head1);
    free_list(head1);

    // 尾插法測試：輸出順序為 1 2 3 4 (順序)
    struct Node *head2 = create_node(0);
    for (int i = 1; i <= 4; i++)
        insert_tail(head2, create_node(i));
    print_list("尾插法結果 (順序)", head2);
    free_list(head2);

    return 0;
}

執行結果對比

=== 頭插法結果 (逆序) ===
node 1: 4
node 2: 3
node 3: 2
node 4: 1

=== 尾插法結果 (順序) ===
node 1: 1
node 2: 2
node 3: 3
node 4: 4

進階延伸：雙向鏈表與哨兵節點

• 雙向鏈表：節點增加 prev 指標，支援 O(1) 刪除、反向遍歷
• 哨兵節點：頭尾各設一哨兵節點，簡化邊界條件判斷
• 循環鏈表：尾節點指向頭節點，適用於循環排程、緩衝區

常見錯誤與避坑指南