鏈表數據結構全景指南：單鏈表創建、插入、刪除與綜合實例

編輯：關於C語言

為什麼需要鏈表？

數組雖然訪問快（O(1)），但大小固定、插入刪除需移動元素（O(n)）、易造成空間浪費或不足。鏈表通過動態內存分配，按需申請釋放，完美解決上述痛點：

空間靈活：無需預分配，用多少申請多少
插刪高效：僅修改指針，無需移動數據
結構多樣：單向、雙向、循環多種變體適應不同場景

單鏈表核心結構定義

struct node {
    int num;              // 數據域：此處存整型
    struct node *next;    // 指針域：指向同類型下一節點
};

注意：結構體內使用未完全定義的類型指針，這是 C 語言允許的特例（遞歸定義）。

單鏈表創建：尾插法完整實現

struct node *creat(struct node *head) {
    struct node *p1, *p2;
    p1 = p2 = (struct node *)malloc(sizeof(struct node));
    scanf("%d", &p1->num);
    p1->next = NULL;
    
    while (p1->num > 0) {  // 輸入正整數，-999 結束
        if (head == NULL)
            head = p1;           // 空表，接入表頭
        else
            p2->next = p1;       // 非空表，接到表尾
        p2 = p1;
        p1 = (struct node *)malloc(sizeof(struct node));
        scanf("%d", &p1->num);
    }
    return head;
}

單鏈表遍歷輸出

void print(struct node *head) {
    struct node *temp = head;
    while (temp != NULL) {
        printf("%6d", temp->num);
        temp = temp->next;
    }
}

節點刪除：三種情況統一處理

刪除節點可能發生在表頭、表中、表尾。關鍵是保持前驅節點指向後繼：

struct node *delet(struct node *head, char *pstr) {
    struct node *temp = head, *p;
    if (head == NULL) {
        printf("鏈表為空！\n");
        return head;
    }
    while (strcmp(temp->str, pstr) != 0 && temp->next != NULL) {
        p = temp;
        temp = temp->next;
    }
    if (strcmp(temp->str, pstr) == 0) {
        if (temp == head) {          // 刪除表頭
            head = head->next;
            free(temp);
        } else {                     // 刪除表中/表尾
            p->next = temp->next;
            free(temp);
        }
    } else {
        printf("未找到目標節點！\n");
    }
    return head;  // 返回新頭指針，防止表頭刪除導致頭指針失效
}

節點插入：按學號有序插入

插入位置同樣分表頭、表中、表尾三種：

struct node *insert(struct node *head, char *pstr, int n) {
    struct node *p1 = (struct node *)malloc(sizeof(struct node));
    strcpy(p1->str, pstr);
    p1->num = n;
    
    struct node *p2 = head, *p3;
    if (head == NULL) {              // 空表
        head = p1;
        p1->next = NULL;
    } else {
        while (n > p2->num && p2->next != NULL) {
            p3 = p2;
            p2 = p2->next;
        }
        if (n <= p2->num) {          // 找到插入位置
            if (head == p2) {        // 插入表頭
                head = p1;
                p1->next = p2;
            } else {                 // 插入表中
                p3->next = p1;
                p1->next = p2;
            }
        } else {                     // 插入表尾
            p2->next = p1;
            p1->next = NULL;
        }
    }
    return head;
}