循環單向鏈表深度解析：結構特性與核心操作實作

循環單向鏈表將尾節點的 next 指向頭節點，形成閉環。這一特性帶來獨特優勢：可從任意節點出發遍歷全表，無須固定頭指標，極大提升操作靈活性。本文詳細解析其與普通單向鏈表的差異，並給出關鍵操作的完整 C 實作。

核心差異：遍歷終止條件

普通鏈表以 NULL 為終點；循環鏈表則以 回到起始節點 為終止條件。這影響所有遍歷類操作（列印、查找、統計等）。

關鍵操作實作

1. 列印資料

void print_data(const LINK_NODE* pHead) {
    if (!pHead) return;

    const LINK_NODE* pCur = pHead;
    do {
        printf("%d\n", pCur->data);
        pCur = pCur->next;
    } while (pCur != pHead);  // 關鍵：回到頭節點即結束
}

2. 插入資料

插入邏輯分兩種情況：

• 空表：新節點 next 指向自己，成為頭節點
• 非空表：插入頭節點之後，僅需調整兩個指標

STATUS insert_data(LINK_NODE** ppHead, int data) {
    if (!ppHead) return FALSE;

    LINK_NODE* pNew = create_link_node(data);
    assert(pNew);

    if (!*ppHead) {           // 空表
        pNew->next = pNew;
        *ppHead = pNew;
        return TRUE;
    }

    if (find_data(*ppHead, data)) return FALSE; // 唯一性檢查

    pNew->next = (*ppHead)->next;
    (*ppHead)->next = pNew;
    return TRUE;
}

3. 刪除資料

刪除需找到目標節點的前驅節點。循環特性允許從目標節點出發繞一圈找到前驅：

STATUS delete_data(LINK_NODE** ppHead, int data) {
    if (!ppHead || !*ppHead) return FALSE;

    LINK_NODE* pTarget = find_data(*ppHead, data);
    if (!pTarget) return FALSE;

    LINK_NODE* pPrev = pTarget->next;
    while (pPrev->next != pTarget)  // 繞圈找前驅
        pPrev = pPrev->next;

    if (pTarget == *ppHead) {       // 刪除頭節點
        if (pTarget->next == pTarget) { // 唯一節點
            *ppHead = NULL;
        } else {
            pPrev->next = pTarget->next;
            *ppHead = pTarget->next;    // 更新頭指標
        }
    } else {
        pPrev->next = pTarget->next;    // 一般節點
    }

    free(pTarget);
    return TRUE;
}

設計要點總結

1. 空表處理：新節點自指，建立最小循環單元
2. 遍歷終止：統一改為 pCur != pHead 條件
3. 前驅查找：利用循環特性從目標節點出發反向尋找
4. 頭節點維護：刪除頭節點時必須更新外部頭指標

循環單向鏈表雖結構簡單，但其「無固定起點」特性在循環緩衝區、輪詢調度、Josephus 問題等場景極具價值。掌握其操作細節，是進階資料結構應用的基石。