C語言雙向循環鏈表實戰應用：有序數據集的高效插入與雙向遍歷

為什麼選擇雙向循環鏈表？

對比單向鏈表與陣列，雙向循環鏈表在 **頻繁插入/刪除** 且需 **雙向遍歷** 的場景具備決定性優勢：

• 插入/刪除僅修改鄰近節點指標，O(1) 級操作（已知位置）。
• 無需移動大量數據（陣列需 O(n) 位移）。
• 循環特性簡化邊界判斷，頭尾節點統一處理。
• 雙向指標支援 **反向遍歷**，適合「查看前 N 條記錄」等需求。

經典應用場景：有序日誌/記錄管理系統

需求：維護一個按時間/編號排序的記錄集，支援：

1. 新記錄插入並保持有序。
2. 按編號查詢記錄詳情。
3. 從某記錄向前/向後翻閱 N 條。

核心結構定義

typedef struct Node {
    int id;                 // 記錄編號（有序鍵）
    char info[100];         // 其他資訊
    struct Node *prev, *next;
} Node;

Node *head = NULL;          // 循環鏈表頭指標（也可設哨兵節點）

關鍵操作實現

1. 有序插入

void insert_sorted(int id, const char *info) {
    Node *newnode = (Node *)malloc(sizeof(Node));
    newnode->id = id;
    strcpy(newnode->info, info);

    if (!head) {                    // 空表
        head = newnode->prev = newnode->next = newnode;
        return;
    }

    Node *p = head;
    do {
        if (p->id >= id) break;     // 找到插入位置（p 之前）
        p = p->next;
    } while (p != head);

    // 插入到 p 之前（等價於 p->prev 之後）
    newnode->prev = p->prev;
    newnode->next = p;
    p->prev->next = newnode;
    p->prev = newnode;

    if (id < head->id) head = newnode;  // 更新頭節點
}

2. 雙向遍歷打印

void print_forward(Node *start, int n) {   // 向後 n 條
    Node *p = start;
    for (int i = 0; i < n && p; i++) {
        printf("%d: %s\n", p->id, p->info);
        p = p->next;
        if (p == head) break;              // 循環保護
    }
}

void print_backward(Node *start, int n) {  // 向前 n 條
    Node *p = start;
    for (int i = 0; i < n && p; i++) {
        printf("%d: %s\n", p->id, p->info);
        p = p->prev;
        if (p == head->prev) break;        // 循環保護
    }
}

課程設計擴展建議

• **持久化**：程式啟動時從二進制檔案載入鏈表，退出時保存。
• **索引優化**：對大量數據（>10 萬節點），輔助跳表或哈希表加速查詢。
• **記憶體池**：頻繁分配/釋放節點時，預分配記憶體池減少碎片。
• **圖形化介面**：結合 EasyX / SDL2 繪製鏈表結構動畫演示插入過程。

總結

雙向循環鏈表是「有序、動態、雙向訪問」數據集的教科書級數據結構。掌握其指標操作邏輯，不僅能完成課程設計，更能深度理解 Linux 核心 list_head、C++ STL list 等工業級實現的精髓。