Java 雙向循環鏈表完整實作與兩種設計對比

雙向循環鏈表是經典資料結構，每個節點擁有前驅與後繼指針，首尾相連形成環。本文提供兩種完整實作風格並深度對比差異。

實作一：UUID 管理多鏈表長度（工業級風格）

特點：支援同時存在多條鏈表，靜態 Map<String, Integer> 記錄各鏈表長度，節點持有 linkedId 關聯。

核心結構

public class BothwayLoopLinked {
    private static final Map<String, Integer> sizeMap = new HashMap<>();
    private String linkedId = null;
    private Object data = null;
    private BothwayLoopLinked prev = this; // 初始自環
    private BothwayLoopLinked next = this;
    ...
}

關鍵操作

• insertAfter/insertBefore：四指針重連，O(1) 插入
• remove()：斷開指針並自環，長度 -1，清除 linkedId
• getSize()：新建/已移除節點視為長度 1 的獨立鏈表

實作二：哨兵節點 + 泛型（教學/標準庫風格）

特點：頭節點為哨兵，不存儲數據；泛型 Node<E>；靜態 size 單鏈表計數。

核心結構

public class Node<E> {
    private E element;
    private Node<E> next;
    private Node<E> previous;
    private static int size = 0;
    ...
}

關鍵操作

• addAfter/addBefore：頭/尾插入，處理空鏈表邊界
• add(index, e)：索引合法性檢查，index > size/2 反向遍歷優化
• remove(index)：同樣雙向遍歷優化
• get(index)：雙向遍歷，for 迴圈邏輯與實作一不同

兩大核心差異深度對比

工程建議

• 生產環境直接使用 java.util.LinkedList（雙向鏈表，非循環）或 ArrayDeque
• 需循環特性時，可包裝 LinkedList 實現邏輯層循環
• 自行實作時，務必處理併發安全（Collections.synchronizedList 或鎖）
• 單元測試覆蓋：空表、單節點、頭尾插入、中間插入、越界、併發修改