C 語言單鏈表核心操作完整實現：創建、遍歷、插入、刪除、查找、排序、反轉

編輯：關於C語言

數據結構定義


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

核心操作函數庫

1. 創建鏈表 (尾插法)


PNode create_list(void) {
    PNode head = (PNode)malloc(sizeof(Node));
    if (!head) return NULL;
    head->next = NULL;
    
    PNode tail = head;
    int val;
    while (scanf("%d", &val) == 1 && val != -1) { // -1 結束標誌
        PNode node = (PNode)malloc(sizeof(Node));
        if (!node) break;
        node->data = val;
        node->next = NULL;
        tail->next = node;
        tail = node;
    }
    return head; // 返回虛擬頭節點
}

2. 遍歷打印


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

3. 指定位置插入 (0-based 索引，頭節點後為第 0 位)


bool insert_at(PNode head, int index, int value) {
    PNode prev = head;
    for (int i = 0; i < index && prev; i++)
        prev = prev->next;
    if (!prev) return false; // 索引越界
    
    PNode node = (PNode)malloc(sizeof(Node));
    if (!node) return false;
    node->data = value;
    node->next = prev->next;
    prev->next = node;
    return true;
}

4. 按值刪除首個匹配節點


bool delete_val(PNode head, int value) {
    PNode prev = head;
    PNode cur = head->next;
    while (cur) {
        if (cur->data == value) {
            prev->next = cur->next;
            free(cur);
            return true;
        }
        prev = cur;
        cur = cur->next;
    }
    return false; // 未找到
}

5. 查找節點 (返回指針)


PNode find_node(PNode head, int value) {
    PNode cur = head->next;
    while (cur) {
        if (cur->data == value) return cur;
        cur = cur->next;
    }
    return NULL;
}

6. 獲取長度


int list_length(PNode head) {
    int len = 0;
    PNode cur = head->next;
    while (cur) { len++; cur = cur->next; }
    return len;
}

7. 冒泡排序 (數據域交換，非指針重鏈)


void bubble_sort(PNode head) {
    for (PNode i = head->next; i; i = i->next) {
        for (PNode j = i->next; j; j = j->next) {
            if (i->data > j->data) {
                int tmp = i->data;
                i->data = j->data;
                j->data = tmp;
            }
        }
    }
}

8. 就地反轉 (三指針法，O(1) 空間)


void reverse_list(PNode head) {
    PNode prev = NULL;
    PNode cur = head->next;
    head->next = NULL; // 原鏈表置空
    
    while (cur) {
        PNode next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    head->next = prev; // 新頭接回虛擬頭節點
}

完整測試主程式


int main() {
    PNode list = create_list(); // 輸入: 3 1 4 1 5 9 -1
    printf("原始: "); print_list(list); // 3->1->4->1->5->9
    
    insert_at(list, 2, 99); // 第2位插入99
    printf("插入後: "); print_list(list); // 3->1->99->4->1->5->9
    
    delete_val(list, 1); // 刪除第一個1
    printf("刪除1: "); print_list(list); // 3->99->4->1->5->9
    
    bubble_sort(list);
    printf("排序後: "); print_list(list); // 1->3->4->5->9->99
    
    reverse_list(list);
    printf("反轉後: "); print_list(list); // 99->9->5->4->3->1
    
    // 釋放內存
    PNode cur = list->next;
    while (cur) {
        PNode tmp = cur;
        cur = cur->next;
        free(tmp);
    }
    free(list);
    return 0;
}

進階話題

主題	關鍵點
雙向鏈表	增加 `prev` 指針，支援 O(1) 反向遍歷、任意節點刪除
循環鏈表	尾節點 next 指向頭，適用於循環調度、Josephus 問題
跳表	多層索引層，O(log n) 查找/插入/刪除，Redis 有序集合底層
內存池優化	預分配節點塊，避免頻繁 malloc/free 碎片與開銷
無鎖並發	CAS 原子操作實現 Lock-Free 鏈表，高性能佇列/棧