C 語言實現帶頭結點單鏈表：頭插法與尾插法構建完整指南

編輯：關於C語言

帶頭結點單鏈表：簡化邊界條件的利器

相比無頭結點版本，帶頭結點單鏈表統一了首節點與普通節點的操作邏輯，消除了「單獨處理頭指針」的特殊情況，是教學與工程實踐的主流選擇。本文實現頭插法與尾插法兩種構建方式。

核心數據結構

typedef int elemType;
typedef struct Node {
    elemType element;
    struct Node *next;
} Node;

關鍵差異：頭結點的角色

頭結點 不存儲有效數據 (或存儲長度等元信息)。
鏈表「為空」定義為：head->next == NULL。
首個數據節點始終是 head->next。

尾插法 `CreateListTailInsert`：順序構建

void CreateListTailInsert(Node *head) {
    Node *pInsert, *pMove = head; // pMove 初始指向頭結點
    
    pInsert = (Node*)malloc(sizeof(Node));
    pInsert->next = NULL;
    scanf("%d", &(pInsert->element));

    while (pInsert->element > 0) { // 輸入 <=0 結束
        pMove->next = pInsert;     // 尾插
        pMove = pInsert;           // pMove 移至新尾部
        
        pInsert = (Node*)malloc(sizeof(Node));
        pInsert->next = NULL;
        scanf("%d", &(pInsert->element));
    }
    free(pInsert); // 釋放最後多分配的節點
    printf("尾插法創建成功\n");
}

頭插法 `CreateListHeadInsert`：逆序構建

void CreateListHeadInsert(Node *head) {
    Node *pInsert;
    
    pInsert = (Node*)malloc(sizeof(Node));
    pInsert->next = NULL;
    scanf("%d", &(pInsert->element));

    while (pInsert->element > 0) {
        pInsert->next = head->next; // 新節點指向原首節點
        head->next = pInsert;       // 頭結點指向新節點
        
        pInsert = (Node*)malloc(sizeof(Node));
        pInsert->next = NULL;
        scanf("%d", &(pInsert->element));
    }
    free(pInsert);
    printf("頭插法創建成功\n");
}

對比總結表

特性	尾插法	頭插法
輸入順序與鏈表順序	一致	相反
需維護尾指針	是	否
核心鏈接語句	`pMove->next = pInsert; pMove = pInsert;`	`pInsert->next = head->next; head->next = pInsert;`
適用場景	隊列、保持輸入序、文件讀取構建	棧、最近優先、表達式求值、哈希桶插入
時間複雜度	O(n) 總計	O(n) 總計

初始化函數 (關鍵前置步驟)

void InitialList(Node **head) {
    *head = (Node*)malloc(sizeof(Node));
    if (!*head) { printf("內存分配失敗\n"); exit(1); }
    (*head)->next = NULL; // 空表標志
    printf("初始化完成\n");
}

完整測試主函數

int main() {
    Node *list;
    InitialList(&list);
    
    // 測試尾插法
    CreateListTailInsert(list);
    PrintList(list); // 輸入 1 2 3 0 → 輸出 1 2 3
    
    // 測試頭插法 (需先清空或重新初始化)
    ClearList(list);
    CreateListHeadInsert(list);
    PrintList(list); // 輸入 1 2 3 0 → 輸出 3 2 1
    
    return 0;
}