C語言鏈表完整實現指南：從基礎結構到增刪查改操作

鏈表基礎概念

鏈表是線性表的鏈式存儲結構。可視為一串珠子：數據是珠子，next 指針是穿珠子的線。優勢在於動態內存管理、插入刪除 O(1)（定位後）、無需預分配容量。

數據結構定義

節點結構

typedef struct Node {
    int data;           // 數據域
    struct Node *next;  // 指針域
} Node;

鏈表管理結構

typedef struct {
    Node *head;   // 頭節點（哨兵節點）
    int count;    // 節點計數
} List;

核心操作實現

1. 初始化

void initList(List *list) {
    list->head = (Node*)malloc(sizeof(Node));
    list->head->next = NULL;
    list->count = 0;
}

2. 逆序創建（頭插法）

void createList(List *list) {
    int arr[10] = {1,2,3,4,5,6,7,8,9,10};
    for (int i = 0; i < 10; i++) {
        Node *p = (Node*)malloc(sizeof(Node));
        p->data = arr[i];
        p->next = list->head->next;
        list->head->next = p;
        list->count++;
    }
}

3. 遍歷打印

void printList(List *list) {
    Node *p = list->head->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    putchar('\n');
}

4. 查找元素位置

int search(List *list, int val) {
    Node *p = list->head->next;
    int pos = 0;
    while (p) {
        pos++;
        if (p->data == val) return pos;
        p = p->next;
    }
    return -1;  // 未找到
}

5. 刪除指定值節點

void deleteNode(List *list, int val) {
    int pos = search(list, val);
    if (pos == -1) { printf("值不存在\n"); return; }
    
    Node *prev = list->head;
    Node *curr = list->head->next;
    while (curr) {
        if (curr->data == val) {
            prev->next = curr->next;
            free(curr);
            list->count--;
            break;
        }
        prev = curr;
        curr = curr->next;
    }
}

6. 指定位置後插入

void insertAfter(List *list, int pos, int val) {
    if (pos < 0 || pos > list->count) { printf("位置非法\n"); return; }
    
    Node *p = list->head;
    for (int i = 0; i < pos; i++) p = p->next;  // 移動到第 pos 個節點
    
    Node *q = (Node*)malloc(sizeof(Node));
    q->data = val;
    q->next = p->next;
    p->next = q;
    list->count++;
}

完整測試主函數

int main() {
    List list;
    initList(&list);
    createList(&list);
    printf("初始鏈表: "); printList(&list);  // 10 9 8 7 6 5 4 3 2 1
    
    deleteNode(&list, 5);
    printf("刪除5後: "); printList(&list);   // 10 9 8 7 6 4 3 2 1
    
    insertAfter(&list, 1, 99);  // 第1個節點(10)後插入
    printf("插入99後: "); printList(&list);  // 10 99 9 8 7 6 4 3 2 1
    
    return 0;
}

鏈表 vs 隊列 vs 棧

關鍵理解：隊列/棧是「接口規範」，鏈表是「實現手段」。同一個隊列可用鏈表實現（鏈隊列）或循環數組實現（順序隊列）。

常見錯誤與調試技巧

1. 野指針：free 後未置 NULL，建議 `free(p), p = NULL;`
2. 內存洩漏：刪除節點忘記 free，或程序結束前未遍釋放
3. 斷鏈：插入刪除時指針賦值順序錯誤，先斷開再連接
4. 越界訪問：未檢查位置合法性直接操作
5. 調試利器：打印節點地址、data、next 三元組，畫圖追蹤

進階主題

• 雙向鏈表：增加 prev 指針，支持雙向遍歷、O(1) 刪除已知節點
• 循環鏈表：尾節點指向頭節點，適用於循環調度（如 Josephus 問題）
• 跳表：多層索引鏈表，實現 O(log n) 查找，Redis 有序集合底層結構