資料結構深度解析：順序表、鏈表與其變體的 C 語言實現指南

前言：為何我們需要多樣化的線性表？

在計算機科學的基石中，線性表是最基本的資料結構之一。雖然它們都用於存儲有序的數據集合，但在底層存儲方式、操作效率及適用場景上卻有著天壤之別。本文將系統梳理順序表、單鏈表、循環單鏈表、循環雙鏈表及有序單鏈表的核心特性，並提供完整的 C 語言實現代碼，幫助開發者在實際工程中做出最優選擇。

一、 核心結構特性對比

1. 順序表：空間換時間的隨機訪問王者

順序表利用一塊連續的內存空間依次存儲數據元素。其最大優勢在於支持 O(1) 的隨機訪問，即可直接通過下標定位任意元素。然而，插入與刪除操作需要移動大量元素，平均時間複雜度為 O(n)，且容量固定（或需動態擴容），容易產生內存碎片或溢出風險。

2. 單鏈表：動態靈活的插刪高手

單鏈表由數據域與指針域組成的節點串聯而成，不要求內存連續。

• 優勢：插入、刪除只需修改指針，時間複雜度 O(1)（已知位置前驅節點時）；內存利用靈活，無容量上限。
• 劣勢：不支持隨機訪問，查找第 i 個元素需 O(n) 遍歷；額外的指針域增加空間開銷；緩存局部性差。

3. 雙向鏈表：雙向奔赴的代價與收穫

在單鏈表基礎上增加前驅指針，實現雙向遍歷。雖然空間開銷進一步增加，但讓「查找前驅節點」從 O(n) 降為 O(1)，在頻繁雙向操作（如瀏覽器歷史記錄、雙端隊列）場景下極具優勢。引入「頭尾哨兵節點」可簡化邊界條件判斷，是工程落地的常用技巧。

4. 循環鏈表：無頭無尾的優雅閉環

將尾節點指向頭節點（單向）或頭尾雙向指向，形成邏輯閉環。

• 循環單鏈表：僅需維護尾指針即可 O(1) 訪問頭尾，適合循環輪該任務調度（如作業系統時間片輪轉）。
• 循環雙鏈表：結合雙向與循環特性，操作對稱性極強，Linux 內核 `list_head` 即採用此結構，是內核級資料結構的典範。

5. 有序單鏈表：為集合運算而生

維持節點數據有序（遞增/遞減），使得合併、求交集、並集、差集等集合運算可在 O(m+n) 線性時間內完成，是實現稀疏多項式、倒排索引等場景的理想選擇。

二、 存儲方式的工程考量

節點內存分配策略直接影響性能與調試體驗：

• 動態分配：`malloc`/`free` 按需申請，靈活但易產生碎片，調試困難。
• 靜態數組池：預分配大數組，用下標代替指針（「數組模擬鏈表」），消除碎片、便於調試、天然支持持久化，但容量固定。高性能服務器開發中極為常見。

三、 完整 C 語言實現代碼庫

以下提供所有結構的標準操作集：初始化、銷毀、判空、求長、遍歷、按位查找、按值查找、插入、刪除。代碼採用帶頭節點設計，統一邊界處理邏輯。

1. 順序表實現

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

#define MAX_SIZE 50
typedef char ElemType;

typedef struct {
    ElemType data[MAX_SIZE];
    int length;
} SqList;

// 初始化
void InitList(SqList *&L) {
    L = (SqList *)malloc(sizeof(SqList));
    L->length = 0;
}

// 銷毀
void DestroyList(SqList *L) { free(L); }

// 判空、求長、遍歷、查找、插入、刪除... (完整代碼見原文)
// 關鍵點：插入/刪除需移動元素，注意下標邊界檢查 (1 ~ length+1)

2. 單鏈表實現

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LinkList;

// 初始化：建立頭節點，next 置 NULL
void InitList(LinkList *&L) {
    L = (LinkList *)malloc(sizeof(LinkList));
    L->next = NULL;
}

// 插入第 i 位置：尋找第 i-1 個節點，修改指針鏈接
int ListInsert(LinkList *&L, int i, ElemType e) {
    LinkList *p = L, *s; int j = 0;
    while (j < i-1 && p) { p = p->next; j++; }
    if (!p) return 0;
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = e; s->next = p->next; p->next = s;
    return 1;
}
// ... 刪除、查找等操作同理

3. 雙鏈表實現

typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;
} DLinkList;

// 插入需維護雙向指針：s->next = p->next; p->next->prior = s; s->prior = p; p->next = s;
// 刪除同理需修復前驅後繼指向

4. 循環單鏈表實現

// 初始化：頭節點 next 指向自己
void InitList(LinkList *&L) {
    L = (LinkList *)malloc(sizeof(LinkList));
    L->next = L;  // 關鍵差異：指向自身
}

// 判空：L->next == L
// 遍歷：p = L->next; while(p != L) { ... p = p->next; }
// 插入刪除邏輯同單鏈表，但終止條件變為 p != L

5. 循環雙鏈表實現

// 初始化：頭節點 prior 和 next 均指向自己
L->prior = L->next = L;

// 插入第 i 個節點 (i=1 為頭插)：
// 需處理四指針鏈接：新節點、前驅、後繼、前驅的後繼、後繼的前驅
// 代碼嚴謹性要求極高，建議參考 Linux kernel list_head 宏實現

6. 有序單鏈表與集合運算

採用插入排序思想構建有序表：將原鏈表拆解，逐個節點插入新有序鏈表適當位置。

void Sort(LinkList *&head) {
    LinkList *p = head->next, *q, *r;
    if (p) {
        r = p->next; p->next = NULL; // 構造單節點有序表
        p = r;
        while (p) {
            r = p->next;
            q = head;
            while (q->next && q->next->data < p->data) q = q->next;
            p->next = q->next; q->next = p; // 插入
            p = r;
        }
    }
}

// 並集：雙指針歸併，重複元素只保留一個
// 交集：遍歷 A，在 B 中查找匹配值
// 差集：遍歷 A，過濾掉在 B 中存在的值

四、 選型決策指南

五、 總結與最佳實踐

沒有完美的資料結構，只有最適合場景的工程選擇。掌握上述結構的「指針操作本質」與「時間空間權衡」，並能熟練編寫無錯誤的邊界代碼（尤其是雙向/循環鏈表的四指針鏈接），是從初級程序員邁向系統級開發者的必經之路。建議讀者在理解原理基礎上，嘗試手寫一個通用的「帶頭節點循環雙鏈表模板庫」，將成為職業生涯長期受用的財富。