鏈表的 C 語言實現（四）：單鏈表插入操作（後插法）

單鏈表插入：後插法

假設已知連續節點 p（前驅）和 q（後繼），在兩者間插入新節點 s：

1. 為 s 分配空間並賦值
2. s->link = q（或 p->link）
3. p->link = s

順序關鍵：先連後繼，再連前驅，避免斷鏈。

插入函數實作

void insert(stud *p) {  // 在節點 p 之後插入
    char stuname[20];
    stud *s;              // 新節點指標
    
    if ((s = (stud *)malloc(sizeof(stud))) == NULL) {
        printf("無法分配記憶體！\n");
        exit(0);
    }
    printf("請輸入要插入的姓名: ");
    scanf("%s", stuname);
    strcpy(s->name, stuname);  // 複製字符串到資料域
    
    s->link = p->link;  // 1. 新節點指向原後繼
    p->link = s;        // 2. 前驅指向新節點
}

主程式流程

int main() {
    int number = N;
    char fullname[20];
    stud *head, *searchpoint;
    
    head = creat(number);           // 建立鏈表
    printf("請輸入要查找的姓名: ");
    scanf("%s", fullname);
    searchpoint = search(head, fullname); // 找到插入位置的前驅節點
    
    if (searchpoint)
        insert(searchpoint);        // 在該節點後插入
    return 0;
}

關鍵函數

• strcpy(dest, src)：字符串複製，確保資料域獨立儲存副本
• 插入操作不改變其他節點，僅調整兩個指標
• 時間複雜度 O(1)（給定前驅節點時）