Java 雙向循環鏈表完整實現與核心原理解析

雙向循環鏈表的核心特性

雙向循環鏈表是數據結構中極具靈活性的結構，每個節點同時持有前驅與後繼引用，且首尾節點相互連接形成環狀。這種結構使得從任意節點出發均可遍歷整個鏈表，且插入、刪除操作僅需調整鄰近節點指針，時間複雜度為 O(1)。

完整實現代碼解析

以下是一個支援多實例獨立計數的雙向循環鏈表實現，通過 UUID 與靜態 Map 解決多鏈表共存時的長度管理問題：

package com.xlst.util;

import java.util.HashMap;
import java.util.Map;
import java.util.UUID;

/**
 * 雙向循環鏈表實現
 * 特性：支援多實例獨立計數、哨兵節點設計、O(1) 插入刪除
 */
public class BothwayLoopLinked {
    /** 存放各鏈表長度的靜態 Map，鍵為鏈表唯一 ID */
    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;

    public BothwayLoopLinked() {}

    /**
     * 在當前節點後插入新節點
     * @param newLinked 待插入節點
     */
    public void insertAfter(BothwayLoopLinked newLinked) {
        BothwayLoopLinked oldBefore = this;
        BothwayLoopLinked oldAfter = this.next;

        // 重新鏈接指針
        oldBefore.next = newLinked;
        newLinked.prev = oldBefore;
        oldAfter.prev = newLinked;
        newLinked.next = oldAfter;

        // 更新長度並綁定鏈表 ID
        changeSize(+1);
        newLinked.linkedId = this.linkedId;
    }

    /**
     * 在當前節點前插入新節點
     * @param newLinked 待插入節點
     */
    public void insertBefore(BothwayLoopLinked newLinked) {
        BothwayLoopLinked oldBefore = this.prev;
        BothwayLoopLinked oldAfter = this;

        oldBefore.next = newLinked;
        newLinked.prev = oldBefore;
        oldAfter.prev = newLinked;
        newLinked.next = oldAfter;

        changeSize(+1);
        newLinked.linkedId = this.linkedId;
    }

    /** 從鏈表移除自身 */
    public BothwayLoopLinked remove() {
        return remove(this);
    }

    /** 移除指定節點 */
    public BothwayLoopLinked remove(BothwayLoopLinked linked) {
        linked.prev.next = linked.next;
        linked.next.prev = linked.prev;

        // 斷開節點自身引用，幫助 GC
        linked.prev = linked;
        linked.next = linked;

        changeSize(-1);
        linked.linkedId = null; // 解除綁定

        return linked;
    }

    /** 修改鏈表長度 */
    private void changeSize(int value) {
        if (this.linkedId == null) {
            this.linkedId = UUID.randomUUID().toString();
            sizeMap.put(linkedId, 1 + value);
        } else {
            Integer size = sizeMap.get(this.linkedId);
            size += value; // Integer 為引用類型，直接修改生效
        }
    }

    // Getter/Setter 方法
    public Object getData() { return data; }
    public void setData(Object data) { this.data = data; }

    /** 獲取鏈表長度，獨立節點視為長度 1 */
    public int getSize() {
        return (linkedId == null) ? 1 : sizeMap.get(this.linkedId);
    }

    public BothwayLoopLinked getPrev() { return prev; }
    public BothwayLoopLinked getNext() { return next; }
}

關鍵設計亮點

• 多實例隔離：靜態 sizeMap 配合 UUID 確保每個鏈表實例擁有獨立計數器，避免多鏈表共存時數據錯亂。
• 哨兵節點模式：節點初始化時 prev = next = this，單節點即形成閉環，統一了邊界條件處理。
• 內存安全：刪除節點時主動斷開自身引用（linked.prev = linked.next = linked），加速垃圾回收。

對比示例：傳統帶頭節點的雙向循環鏈表

另一種常見實現使用虛擬頭節點（哨兵），頭節點不存儲數據，next 指向首元素，previous 指向尾元素：

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

    // 尾部添加
    public void addAfter(E e) {
        Node<E> newNode = new Node<>(e, this, this.previous == null ? this : this.previous);
        if (this.next == null) this.next = newNode;
        if (this.previous == null) this.previous = newNode;
        this.previous.next = newNode;
        this.previous = newNode;
        size++;
    }

    // 索引查找優化：雙向遍歷
    public E get(int index) {
        if (index > size >> 1) { // 從尾部反向遍歷
            Node<E> temp = this;
            for (int i = size; i > index; i--) temp = temp.previous;
            return temp.element;
        } else { // 從頭部正向遍歷
            Node<E> temp = this;
            for (int i = 0; i <= index; i++) temp = temp.next;
            return temp.element;
        }
    }
}

兩種實現的核心差異

最佳實踐建議

1. 選擇無頭節點版當需要多個獨立鏈表實例，或節點頻繁在不同鏈表間移動時。
2. 選擇帶頭節點版當需要統一入口管理，或參考 java.util.LinkedList 內部實現風格時。
3. 注意 get(index) 的邊界條件：帶頭節點版首次遍歷從 head.next 開始，索引 0 對應首個數據節點。