鏈表核心操作詳解：插入、刪除與遍歷的 C 語言實現

鏈表節點操作基礎

鏈表由 n 個離散節點通過指針相連組成，所有操作均透過頭指針（指向頭節點地址）對節點進行操作來實現。掌握節點層面的指針操作是理解鏈表的關鍵。

1. 節點插入操作

將 q 指向的節點插入到 p 指向節點之後，有兩種實現方式：

方法一：使用臨時變量

Node *r = p->pNext;  // 保存 p 的下一個節點地址
p->pNext = q;        // p 指向 q
q->pNext = r;        // q 指向原來 p 的下一個節點

方法二：不使用臨時變量

q->pNext = p->pNext; // 讓 q 指向 p 原本的下一個節點
p->pNext = q;        // 再讓 p 指向 q

第二種方法更簡潔，但需注意操作順序不可顛倒，否則會丟失後續節點地址。

2. 節點刪除操作

刪除 p 後面的節點，需用臨時變量保存被刪節點地址以便釋放內存：

Node *r = p->pNext;
p->pNext = p->pNext->pNext; // 跳過被刪節點
free(r);                    // 釋放內存
r = NULL;                   // 避免野指針

3. 判斷鏈表是否為空

空鏈表僅包含頭節點，頭節點的指針域為 NULL 即表示鏈表為空：

bool IsEmpty(PNODE pHead) {
    return (pHead->pNext == NULL);
}

完整鏈表操作實現

以下代碼實現了鏈表的創建、遍歷、長度計算、插入、刪除、查找、修改及排序等核心功能：

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

typedef struct Node {
    int data;
    struct Node *pNext;
} NODE, *PNODE;

// 函數聲明
PNODE CreateList();
void TraverseList(PNODE);
bool IsEmpty(PNODE);
int Length(PNODE);
bool InsertNode(PNODE, int, int);
bool DeleteNode(PNODE, int, int *);
bool QueryNode(PNODE, int);
bool ModifyNode(PNODE, int, int);
void SortList(PNODE);

int main() {
    PNODE pHead = CreateList();
    if (0 == Length(pHead)) {
        printf("鏈表無有效節點，退出程序！\n");
        exit(-1);
    }
    TraverseList(pHead);
    
    if (InsertNode(pHead, 2, 100)) {
        printf("插入後：");
        TraverseList(pHead);
    } else {
        printf("插入操作失敗！\n");
    }
    
    SortList(pHead);
    printf("排序後：");
    TraverseList(pHead);
    return 0;
}

// 創建鏈表（尾插法）
PNODE CreateList() {
    int len, i, val;
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (NULL == pHead) {
        printf("分配失敗，程序終止運行！\n");
        exit(-1);
    }
    PNODE pTail = pHead;
    pTail->pNext = NULL;
    
    printf("請輸入要創建的鏈表節點個數：len=");
    scanf("%d", &len);
    
    for (i = 0; i < len; i++) {
        printf("請輸入第 %d 個節點的值：", i + 1);
        scanf("%d", &val);
        
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (NULL == pNew) {
            printf("分配失敗，程序終止運行！\n");
            exit(-1);
        }
        pNew->data = val;
        pTail->pNext = pNew;
        pNew->pNext = NULL;
        pTail = pNew;
    }
    return pHead;
}

// 遍歷鏈表
void TraverseList(PNODE pHead) {
    PNODE p = pHead->pNext;
    printf("遍歷整個鏈表：");
    while (NULL != p) {
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
}

// 判斷是否為空
bool IsEmpty(PNODE pHead) {
    return (NULL == pHead->pNext);
}

// 求鏈表長度
int Length(PNODE pHead) {
    PNODE p = pHead->pNext;
    int len = 0;
    while (NULL != p) {
        ++len;
        p = p->pNext;
    }
    return len;
}

// 指定位置插入節點
bool InsertNode(PNODE pHead, int pos, int val) {
    int i = 0;
    PNODE p = pHead;
    
    // 找到插入位置的前一個節點
    while (NULL != p && i < pos - 1) {
        p = p->pNext;
        ++i;
    }
    
    if (i > pos - 1 || NULL == p) return false;
    
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (NULL == pNew) {
        printf("動態內存分配失敗，程序終止！\n");
        exit(-1);
    }
    
    pNew->data = val;
    PNODE q = p->pNext;
    p->pNext = pNew;
    pNew->pNext = q;
    return true;
}

// 指定位置刪除節點
bool DeleteNode(PNODE pHead, int pos, int *pVal) {
    int i = 0;
    PNODE p = pHead;
    
    while (NULL != p->pNext && i < pos - 1) {
        p = p->pNext;
        ++i;
    }
    
    if (i > pos - 1 || NULL == p) return false;
    
    PNODE q = p->pNext;
    *pVal = q->data;
    p->pNext = p->pNext->pNext;
    free(q);
    q = NULL;
    return true;
}

// 鏈表排序（冒泡排序思想，交換數據域）
void SortList(PNODE pHead) {
    int i, j, t;
    int len = Length(pHead);
    PNODE p, q;
    
    for (i = 0, p = pHead->pNext; i < len - 1; p = p->pNext, i++) {
        for (j = i + 1, q = p->pNext; j < len; q = q->pNext, j++) {
            if (p->data > q->data) {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
}

// 查找指定位置節點
bool QueryNode(PNODE pHead, int pos) {
    int i = 0;
    PNODE p = pHead;
    
    while (NULL != p->pNext && i < pos - 1) {
        p = p->pNext;
        ++i;
    }
    
    if (i > pos - 1 || NULL == p) return false;
    
    PNODE q = p->pNext;
    printf("第 %d 號位置上節點的值為：%d\n", pos, q->data);
    return true;
}

// 修改指定位置節點值
bool ModifyNode(PNODE pHead, int pos, int val) {
    int i = 0;
    PNODE p = pHead;
    
    while (NULL != p->pNext && i < pos - 1) {
        p = p->pNext;
        ++i;
    }
    
    if (i > pos - 1 || NULL == p) return false;
    
    PNODE q = p->pNext;
    q->data = val;
    printf("修改第 %d 號位置上節點的值為：%d\n", pos, q->data);
    return true;
}

開發環境注意事項

• C/C++ 編譯器差異：VC++ 中 C 編譯器不支持 bool 類型，需使用 C++ 編譯器或自行定義。
• 變量聲明位置：C 語言要求所有變量必須在函數開頭聲明，C++ 則允許隨時聲明。

數據結構與算法的再理解

狹義與廣義視角

泛型編程思想

泛型旨在實現「不同存儲方式，相同操作邏輯」，主要通過模板、運算符重載、指針等技術實現，是 C++ 標準庫（STL）的核心基石。

線性結構存儲對比

理解這些特性差異，有助於根據具體場景選擇最合適的數據結構。