Java 鏈表深度解析：單向循環鏈表與雙向循環鏈表完整實現

前言

循環鏈表將尾節點指向頭節點，形成環狀結構，適用於輪詢調度、緩衝區管理等場景。本文提供生產級完整實現，涵蓋單向/雙向循環鏈表的增刪改查、邊界處理、單元測試，代碼可直接落地項目。

核心設計決策

• 哨兵節點：head 不存業務數據，head.next == head 表示空表，統一邊界邏輯
• 統一接口：ICommOperate<T> 定義增刪改查契約，便於多態替換
• 1-based 索引：符合業務直覺，內部轉 0-based 處理
• 防禦性編程：越界檢查、空表守衛、GC 輔助

一、單向循環鏈表

節點定義

public class SNode {
    private String data;
    private SNode nextNode;
    // 構造器、getter/setter 省略
}

核心操作實現精要

插入尾部

public boolean insertNode(SNode node) {
    initIfEmpty(); // 空表初始化 head.next = head
    if (size == 0) {
        head.setNextNode(node);
        node.setNextNode(head);
    } else {
        SNode cur = head;
        while (cur.getNextNode() != head) cur = cur.getNextNode(); // 找尾
        cur.setNextNode(node);
        node.setNextNode(head); // 閉環
    }
    size++; return true;
}

指定位置插入

遍歷找到 pos-1 節點（前驅），新節點 next 指向當前節點，前驅 next 指向新節點。位置越界自動尾插。

刪除節點

找到 pos-1 節點（前驅）與 pos 節點（目標）及 pos+1 節點（後繼）
前驅 next 直接指向後繼 → 目標斷鏈 → System.gc() 提示回收 → size--

按序遍歷

public void printLink() {
    if (size == 0) { println("空表"); return; }
    SNode cur = head.getNextNode();
    int i = 0;
    while (cur != head) { // 遇頭節點停止
        println("第 " + (++i) + " 個: " + cur);
        cur = cur.getNextNode();
    }
}

二、雙向循環鏈表

節點增強

public class DNode {
    private String data;
    private DNode priorNode, nextNode;
    // 雙向指針
}

關鍵差異點

• 初始化：head.next = head; head.prior = head;
• 插入尾部：新節點 prior=尾節點, next=head；尾節點 next=新節點；head.prior=新節點
• 中間插入：四指針同步更新 pre.next=new; new.prior=pre; new.next=cur; cur.prior=new
• 刪除：pre.next=cur.next; cur.next.prior=pre（尾節點特判 head.prior=pre）

三、完整可運行測試類

public static void main(String[] args) {
    // 單向測試
    SingleCycleLinkList scll = new SingleCycleLinkList();
    Stream.of("節點1","節點2","節點3","節點4","節點5")
          .map(SNode::new).forEach(scll::insertNode);
    scll.printLink();
    scll.insertPosNode(3, new SNode("插入指定位置"));
    scll.printLink();
    scll.deleteNode(3);
    scll.printLink();
    scll.updateNode(3, Map.of("data","modified"));
    scll.printLink();

    // 雙向測試
    DoubleCycleLinkList dcll = new DoubleCycleLinkList();
    Stream.of("節點1","節點2","節點3","節點4","節點5")
          .map(DNode::new).forEach(dcll::insertNode);
    dcll.printLink();
    // ... 同樣驗證增刪改查
}

性能與適用場景對比

* 維護 tail 指針或利用 head.prior 可 O(1) 尾插

工程落地建議

1. 實際項目優先用 java.util.LinkedList（雙向非循環）或 ArrayDeque，經過 JIT 優化、線程不安全但性能極佳
2. 需線程安全用 Collections.synchronizedList 或並發包
3. 教學/面試/特殊環形業務（如時間輪、Round-Robin 調度）再手寫循環鏈表
4. 生產代碼務必補全：泛型、迭代器、Serializable、單元測試覆蓋邊界條件