C語言單向鏈表核心操作完整實現：創建/遍歷/增刪改查/銷毀

編輯：關於C語言

C語言單向鏈表核心操作完整實現：創建/遍歷/增刪改查/銷毀

單向鏈表是數據結構教學與工程實踐的基石。本文提供一個標準、完整、可編譯運行的C語言單向鏈表實現，涵蓋節點定義、鏈表創建、遍歷打印、清空銷毀、判空、求長度、按位置查找、插入、刪除等全部核心操作，代碼風格規範，邏輯清晰，適合教學參考與項目移植。

數據結構定義

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct LinkNode {
    int data;                    // 數據域（本例為int，可泛化為void*）
    struct LinkNode* next;       // 指針域
} LinkNode, *LinkList;           // 別名：LinkList 等價於 LinkNode*

核心操作函數實現

1. 創建鏈表（尾插法，-1結束）

LinkList LinkCreate() {
    LinkList head = NULL, tail = NULL;
    int val;
    while (1) {
        scanf("%d", &val);
        if (val == -1) break;

        LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
        if (!newNode) { perror("malloc failed"); exit(EXIT_FAILURE); }
        newNode->data = val;
        newNode->next = NULL;

        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;  // 返回頭指針（無哨兵節點版本）
}

2. 遍歷打印

void LinkPrint(LinkList head) {
    LinkNode* p = head;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

3. 銷毀鏈表（釋放所有節點）

void ClearList(LinkList head) {
    LinkNode *curr = head, *next;
    while (curr) {
        next = curr->next;
        free(curr);
        curr = next;
    }
    // 注意：調用者需自行將頭指針置NULL
}

4. 判空

bool ListEmpty(LinkList head) {
    return head == NULL;
}

5. 求長度

int ListLength(LinkList head) {
    int len = 0;
    LinkNode* p = head;
    while (p) {
        len++;
        p = p->next;
    }
    return len;
}

6. 按位置查找（1-based索引）

int GetElem(LinkList head, int pos) {
    if (pos < 1 || pos > ListLength(head)) return -1;  // 錯誤碼
    LinkNode* p = head;
    for (int i = 1; i < pos; i++) p = p->next;
    return p->data;
}

7. 按位置插入（1-based，插入到pos位置，原pos及之後後移）

bool ListInsert(LinkList* headRef, int val, int pos) {
    int len = ListLength(*headRef);
    if (pos < 1 || pos > len + 1) return false;  // 允許在尾部插入(pos=len+1)

    LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
    if (!newNode) return false;
    newNode->data = val;

    if (pos == 1) {  // 頭插
        newNode->next = *headRef;
        *headRef = newNode;
        return true;
    }

    // 找到第 pos-1 個節點
    LinkNode* p = *headRef;
    for (int i = 1; i < pos - 1; i++) p = p->next;
    newNode->next = p->next;
    p->next = newNode;
    return true;
}

8. 按位置刪除（1-based）

bool ListDelete(LinkList* headRef, int pos) {
    if (pos < 1 || pos > ListLength(*headRef)) return false;

    LinkNode* delNode;
    if (pos == 1) {  // 刪除頭節點
        delNode = *headRef;
        *headRef = delNode->next;
    } else {
        LinkNode* p = *headRef;
        for (int i = 1; i < pos - 1; i++) p = p->next;
        delNode = p->next;
        p->next = delNode->next;
    }
    free(delNode);
    return true;
}

主函數測試驗證

int main() {
    printf("請輸入鏈表數據（-1結束）：");
    LinkList list = LinkCreate();
    printf("創建完成："); LinkPrint(list);

    printf("長度：%d\n", ListLength(list));
    printf("第3個元素：%d\n", GetElem(list, 3));

    ListInsert(&list, 99, 2);
    printf("在位置2插入99："); LinkPrint(list);

    ListDelete(&list, 1);
    printf("刪除頭節點："); LinkPrint(list);

    ClearList(list);
    printf("銷毀後判空：%s\n", ListEmpty(list) ? "真" : "假");
    return 0;
}

關鍵技術點總結

操作	時間複雜度	關鍵難點	邊界處理
創建	O(n)	尾指針維護	空表、單節點
遍歷	O(n)	指針推進	空表
查找	O(n)	索引轉指針	越界返回錯誤碼
插入	O(n)	前驅節點定位、頭插特判	pos=1, pos=len+1
刪除	O(n)	前驅節點定位、釋放內存、頭刪特判	pos=1, pos=len
銷毀	O(n)	釋放前保存next	調用者置NULL