C 語言單鏈表完整實現：創建、遍歷、插入、刪除、排序、逆序與內存管理

編輯：關於C語言

C 語言單鏈表完整實現：創建、遍歷、插入、刪除、排序、逆序與內存管理

單鏈表是數據結構教學與工程實踐的基石。本文提供帶頭節點的單鏈表完整 C 實現，涵蓋初始化、尾插法創建、遍歷、判空、求長、按位置插入/刪除、冒泡排序、就地逆序、銷毀釋放等核心操作，代碼風格統一、邊界處理完善、內存安全無洩漏。

一、數據結構定義

#include 
#include 
#include 

typedef struct Node {
    int data;
    struct Node *next;
} Node, *PNode; // PNode 即 Node*

// 帶頭節點鏈表：head->data 無意義，head->next 指向首元節點

二、核心操作實現

1. 初始化（創建頭節點）

PNode create_list() {
    PNode head = (PNode)malloc(sizeof(Node));
    if (!head) { fprintf(stderr, "malloc failed\n"); exit(EXIT_FAILURE); }
    head->next = NULL;
    return head;
}

2. 尾插法創建（交互式輸入）

void build_list_tail(PNode head) {
    int len, val;
    printf("請輸入節點個數: ");
    scanf("%d", &len);
    PNode tail = head;
    for (int i = 0; i < len; ++i) {
        printf("第 %d 個值: ", i+1);
        scanf("%d", &val);
        PNode node = (PNode)malloc(sizeof(Node));
        if (!node) { fprintf(stderr, "malloc failed\n"); exit(EXIT_FAILURE); }
        node->data = val;
        node->next = NULL;
        tail->next = node;
        tail = node;
    }
}

3. 遍歷打印

void traverse(PNode head) {
    PNode p = head->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

4. 判空、求長

bool is_empty(PNode head) { return head->next == NULL; }

int length(PNode head) {
    int len = 0;
    for (PNode p = head->next; p; p = p->next) len++;
    return len;
}

5. 按位置插入（1-based，頭節點後為第 1 位）

bool insert_pos(PNode head, int pos, int val) {
    if (pos < 1) return false;
    PNode prev = head;
    for (int i = 1; i < pos && prev; ++i) prev = prev->next;
    if (!prev) return false; // 位置超出長度+1

    PNode node = (PNode)malloc(sizeof(Node));
    if (!node) return false;
    node->data = val;
    node->next = prev->next;
    prev->next = node;
    return true;
}

6. 按位置刪除（返回被刪值）

bool delete_pos(PNode head, int pos, int *val) {
    if (pos < 1) return false;
    PNode prev = head;
    for (int i = 1; i < pos && prev->next; ++i) prev = prev->next;
    if (!prev->next) return false; // 位置超出長度

    PNode del = prev->next;
    *val = del->data;
    prev->next = del->next;
    free(del);
    return true;
}

7. 冒泡排序（交換數據域，簡化指針操作）

void sort_list(PNode head) {
    int len = length(head);
    for (int i = 0; i < len - 1; ++i) {
        PNode p = head->next;
        for (int j = 0; j < len - 1 - i; ++j) {
            if (p->data > p->next->data) {
                int tmp = p->data;
                p->data = p->next->data;
                p->next->data = tmp;
            }
            p = p->next;
        }
    }
}

8. 就地逆序（三指針法，O(1) 空間）

void reverse_list(PNode head) {
    PNode prev = NULL;
    PNode curr = head->next;
    while (curr) {
        PNode next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head->next = prev;
}

9. 銷毀鏈表（釋放所有節點含頭節點）

void destroy_list(PNode head) {
    PNode curr = head;
    while (curr) {
        PNode next = curr->next;
        free(curr);
        curr = next;
    }
}

三、主函數測試驅動

int main() {
    PNode head = create_list();
    build_list_tail(head);          // 輸入: 5 3 1 4 2
    printf("原始: "); traverse(head); // 3 1 4 2

    sort_list(head);
    printf("排序: "); traverse(head); // 1 2 3 4

    insert_pos(head, 3, 99);
    printf("插入99@3: "); traverse(head); // 1 2 99 3 4

    int val;
    delete_pos(head, 2, &val);
    printf("刪除位置2(%d): ", val); traverse(head); // 1 99 3 4

    reverse_list(head);
    printf("逆序: "); traverse(head); // 4 3 99 1

    destroy_list(head);
    printf("銷毀完成\n");
    return 0;
}

四、進階擴展方向

功能	實現要點
查找節點	按值/按位置返回指針，支持前驅查找
合併有序鏈表	歸併邏輯，O(n+m) 時間，原地修改指針
檢測環/入環點	快慢指針 (Floyd 判圈)
雙向鏈表	添加 prev 指針，支持雙向遍歷、O(1) 刪除給定節點
線程安全	引入 pthread_mutex_t，封裝鎖操作