C語言單鏈表教科書級實現：傳統存儲結構與 10 大核心操作完整代碼

C語言單鏈表教科書級實現：傳統存儲結構與 10 大核心操作完整代碼

單鏈表是動態數據結構的入門基石。本文採用**傳統結構（結構體 + 指針域）**，實現 10 種核心操作：按值/序號查找、插入、刪除、頭插/尾插建表、有序歸並、銷毀、求長、遍歷。每個函數附詳細邏輯註釋、時間複雜度分析與邊界處理。

數據結構定義

typedef struct Node {
    char data;           // 數據域（演示用 char，易改為任意類型）
    struct Node *next;   // 指針域
} Node, *LinkList;       // LinkList = Node* ，語義化「鏈表頭指針」

10 大操作函數原型

// 1. 按值查找
LinkList getElemByValue(LinkList L, char value);
// 2. 按序號查找
void getElemByNum(LinkList L, int num, char *value);
// 3. 刪除第 i 個結點
void deleteList(LinkList L, int i, char *value);
// 4. 第 i 位置前插入
void insertList(LinkList L, int i, char value);
// 5. 頭插法建表（逆序）
void createListByHead(LinkList *L, int n);
// 6. 尾插法建表（順序）
void createListByTail(LinkList *L, int n);
// 7. 有序鏈表歸並（尾插，不申請新結點）
void mergeListsByTail(LinkList LA, LinkList LB, LinkList LC);
// 8. 銷毀鏈表
void destoryLinkList(LinkList *L);
// 9. 求表長（存入頭結點 data 域）
void getLength(LinkList L);
// 10. 遍歷打印
void traversalList(LinkList L);

核心算法邏輯詳解

查找（按值/按序）：順序遍歷，O(n)

LinkList getElemByValue(LinkList L, char value) {
    LinkList p = L->next;  // 跳過頭結點
    while (p && p->data != value) p = p->next;
    return p;  // 找到返回結點指針，否則 NULL
}

刪除：必須找到前驅結點，O(n)

void deleteList(LinkList L, int i, char *value) {
    LinkList p = L;  // p 指向頭結點（第 0 位）
    int j = 0;
    while (p->next && j < i-1) { p = p->next; j++; }  // 移動到第 i-1 結點
    if (!p->next || j > i-1) { puts("i不合法"); return; }
    LinkList tmp = p->next;      // tmp 指向被刪結點
    p->next = tmp->next;         // 斷鏈
    *value = tmp->data;          // 返回數據
    free(tmp); tmp = NULL;       // 釋放內存
}

插入：同樣找前驅，注意指針修改順序，O(n)

void insertList(LinkList L, int i, char value) {
    LinkList p = L; int j = 0;
    while (p && j < i-1) { p = p->next; j++; }
    if (!p || j > i-1) { puts("i不合法"); return; }
    LinkList s = malloc(sizeof(Node));
    s->data = value;
    s->next = p->next;  // 先掛後繼
    p->next = s;        // 再掛前驅（順序不可反！）
}

頭插法 vs 尾插法

有序歸並：雙指針比較 + 尾插，O(n+m)，空間 O(1)

void mergeListsByTail(LinkList LA, LinkList LB, LinkList LC) {
    LinkList pa = LA->next, pb = LB->next;
    LC = LA;          // 復用 LA 頭結點作為 LC 頭結點
    LinkList pc = LA; // pc 作為尾指針
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa; pc = pa; pa = pa->next;
        } else {
            pc->next = pb; pc = pb; pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;  // 掛掉剩餘段
    free(LB); LB = NULL;      // 釋放 LB 頭結點
}

銷毀：逐個 free，頭指針置 NULL，O(n)

void destoryLinkList(LinkList *L) {
    LinkList p;
    while (*L) {
        p = (*L)->next;
        free(*L);
        *L = p;
    }
    *L = NULL;  // 斬斷外部引用
}

測試主程序

int main() {
    LinkList L = NULL, L2 = NULL, val = NULL;
    char v;
    
    // 尾插建表 1->2->3->4->5
    createListByTail(&L, 5);
    getLength(L); traversalList(L);
    destoryLinkList(&L);
    
    // 頭插建表 a->b->c->d->e → e d c b a
    createListByHead(&L2, 5);
    getLength(L2); traversalList(L2);
    
    val = getElemByValue(L2, '2');
    insertList(L2, 1, 'p');  // 第 1 位前插 p
    traversalList(L2);
    
    getElemByNum(L2, 2, &v);
    deleteList(L2, 1, &v);
    traversalList(L2);
    
    destoryLinkList(&L2);
    return 0;
}

scanf 輸入陷阱與應對

代碼中反復出現：

scanf("%c", &(p->data));
while (getchar() != '\n');  // 清空輸入隊列殘留換行

**原因**：%c 讀取單字符，**不跳過空白**，上次輸入的 \n 會被下次 %c 讀走。循環清空是標準應對。

避坑總結

1. **帶頭結點**：統一空表/非空表、首元結點操作邏輯，碼量減半
2. **刪除/插入必找前驅**：單鏈表無法反向遍歷，前驅是修改 next 的前提
3. **指針修改順序**：插入先掛後繼、刪除先存被刪結點，**防斷鏈**
4. **free 後置 NULL**：防野指針二次訪問
5. **函數參數傳遞**：需修改頭指針（建表、銷毀）傳 LinkList*，僅遍歷傳 LinkList

這套「結構定義清晰、操作邊界完備、內存管理嚴謹」的單鏈表代碼，可直接作為項目庫組件或面試手寫模板。