您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 數據結構深度解析：雙向鏈表、循環雙向鏈表、排序循環雙向鏈表、XOR 鏈表設計與實現

編輯：Java 相關知識

本文系統講解四種進階鏈表結構的設計原理、核心操作（增刪改查）、代碼實現與性能分析：
1. **帶頭結點雙向鏈表** —— 增加 `prev` 指針實現雙向遍歷，尾指針優化尾部插入。
2. **循環雙向鏈表** —— 首尾相連，統一插入刪除邏輯，無需區分頭/中/尾。
3. **排序循環雙向鏈表** —— 繼承循環雙向鏈表，重寫 `add` 按值有序插入。
4. **XOR 鏈表** —— 利用異或運算單指針存儲前後地址差，理論節省 50% 指針空間，但 Java 難以高效實現。
附帶完整可運行泛型代碼、測試用例、操作圖解、效率對比表。

一、帶頭結點雙向鏈表

1. 節點定義

public class DNode<T> {
    public T data;
    public DNode<T> prev, next;
    public DNode(T data, DNode<T> prev, DNode<T> next) { this.data=data; this.prev=prev; this.next=next; }
    public DNode(T data) { this(data, null, null); }
    public DNode() { this(null, null, null); }
}

2. 核心類結構

public class HeadDoubleLinkedList<T> implements ILinkedList<T> {
    protected DNode<T> head; // 虛擬頭結點（不存數據）
    protected DNode<T> tail; // 尾指針，O(1) 尾部插入
    
    public HeadDoubleLinkedList() { head = tail = new DNode<>(); }
    // 構造函數接受數組快速建表...
}

3. 關鍵操作實現精要

操作	核心邏輯	複雜度
插入	找前驅 `front` → 新節點 `q(prev=front, next=front.next)` → `front.next.prev=q` (若非尾) → `front.next=q` → 更新 `tail`	O(n) 查找 + O(1) 插入
刪除	找目標 `p` → `p.next.prev=p.prev` (若非尾) → `p.prev.next=p.next` → 更新 `tail`	O(n) 查找 + O(1) 刪除
查值/改值	從 `head.next` 遍歷至索引	O(n)
尾部追加	`tail.next=new Node(data, tail, null); tail=tail.next;`	O(1)

4. 完整代碼

// 見文末完整類 HeadDoubleLinkedList（含構造、增刪改查、contains、clear、toString、main 測試）

二、循環雙向鏈表

1. 結構特點

`head.next` 指向首節點，`head.prev` 指向尾節點。
尾節點 `next` 指向 `head`，首節點 `prev` 指向 `head`。
**無需 `tail` 指針**，`head.prev` 即尾節點。
遍歷終止條件：`p != head`。

2. 插入/刪除統一邏輯（無需分頭中尾）

// 插入：找前驅 p → q=new Node(data, p, p.next) → p.next=q → q.next.prev=q
// 刪除：找目標 p → p.prev.next=p.next → p.next.prev=p.prev
// 以上邏輯對頭部、中間、尾部**完全一致**，因 p.next/p.prev 永不為 null

3. 完整代碼

// 見文末 LoopHeadDoubleLinkedList 類

三、排序循環雙向鏈表

繼承 `LoopHeadDoubleLinkedList<T extends Comparable<? super T>>`。
重寫 `add(T data)`：按值大小尋找插入位置，調用父類尾部插入或中間插入邏輯。
插入複雜度 O(n)（查找位置），但保證鏈表始終有序。

@Override
public boolean add(T data) {
    if (data == null || !(data instanceof Comparable)) throw new IllegalArgumentException();
    Comparable<T> cmp = (Comparable<T>) data;
    // 空表或值大於尾節點 → 尾部插入
    if (isEmpty() || cmp.compareTo(head.prev.data) > 0) return super.add(data);
    // 尋找第一個大於 data 的節點 p
    DNode<T> p = head.next;
    while (p != head && cmp.compareTo(p.data) > 0) p = p.next;
    // 在 p 前插入
    DNode<T> q = new DNode<>(data, p.prev, p);
    p.prev.next = q; p.prev = q;
    return true;
}

四、XOR 鏈表（異或鏈表）理論設計

1. 原理

每個節點僅存一個 `ptrdiff = prev_address XOR next_address`。
已知當前節點 `C` 的 `ptrdiff` 及其中一鄰居地址，即可計算另一鄰居：
`next = ptrdiff XOR prev` / `prev = ptrdiff XOR next`。

2. 異或性質

`X XOR X = 0`
`X XOR 0 = X`
`X XOR Y = Y XOR X`
`(X XOR Y) XOR Z = X XOR (Y XOR Z)`

3. 為什麼 Java 難以實現？

無法直接獲取/操作對象內存地址（無指針算術）。
`sun.misc.Unsafe` 可繞過但極不推薦、非標準、版本脆弱。
GC 移動對象導致地址失效，XOR 值瞬時失效。
結論：**XOR 鏈表適合 C/C++ 手動內存管理環境，Java 僅作算法理論學習**。

五、鏈表 vs 動態數組 vs 數組效率對比

操作	鏈表	動態數組	數組
索引訪問	O(n)	O(1)	O(1)
頭部插入/刪除	O(1)	O(n)	O(n) 或不支援
尾部插入	O(1) 有尾指針	O(1) 擴容攤銷	O(1) 固定長度
尾部刪除	O(n) 無尾指針 / O(1) 雙向+尾指針	O(1)	O(1)
中間插入/刪除	O(n) 查找 + O(1) 操作	O(n) 移動元素	O(n) 移動元素
空間開銷	O(n) 指針	O(n) 擴容冗餘	O(n) 固定

六、完整可運行代碼（含測試主方法）

1. 統一接口

public interface ILinkedList<T> {
    boolean isEmpty(); int length(); T get(int index); T set(int index, T data);
    boolean add(int index, T data); boolean add(T data);
    T remove(int index); boolean removeAll(T data); void clear();
    boolean contains(T data); String toString();
}

2. HeadDoubleLinkedList（帶頭雙向）

public class HeadDoubleLinkedList<T> implements ILinkedList<T> {
    protected DNode<T> head, tail;
    public HeadDoubleLinkedList() { head = tail = new DNode<>(); }
    public HeadDoubleLinkedList(T[] array) { this(); if(array!=null) for(T t:array) add(t); }
    // 實現所有接口方法（含帶索引插入、刪除、查找、修改、尾部追加、contains、clear、toString）
    // 關鍵點：插入刪除需處理 front.next==null、更新 tail、prev/next 雙向指針一致性
    // 測試 main：構建、get、add(index)、add(tail)、set、remove、removeAll、contains
}

3. LoopHeadDoubleLinkedList（循環雙向）

public class LoopHeadDoubleLinkedList<T> implements ILinkedList<T> {
    protected DNode<T> head;
    public LoopHeadDoubleLinkedList() { head = new DNode<>(); head.next=head; head.prev=head; }
    public LoopHeadDoubleLinkedList(T[] array) { this(); if(array!=null) for(T t:array) add(t); }
    // 實現：遍歷條件 p!=head，插入刪除無需分支，尾部插入用 head.prev
    // 測試 main 同前
}

4. SortLoopHeadDoubleLinkedList（排序循環雙向）

public class SortLoopHeadDoubleLinkedList<T extends Comparable<? super T>> 
        extends LoopHeadDoubleLinkedList<T> {
    @Override public boolean add(T data) {
        if(data==null||!(data instanceof Comparable)) throw new IllegalArgumentException();
        Comparable<T> cmp = (Comparable<T>) data;
        if(isEmpty() || cmp.compareTo(head.prev.data) > 0) return super.add(data);
        DNode<T> p = head.next;
        while(p!=head && cmp.compareTo(p.data) > 0) p = p.next;
        DNode<T> q = new DNode<>(data, p.prev, p);
        p.prev.next = q; p.prev = q;
        return true;
    }
    public static void main(String[] args) {
        SortLoopHeadDoubleLinkedList<Integer> list = new SortLoopHeadDoubleLinkedList<>();
        list.add(50); list.add(40); list.add(80); list.add(20);
        System.out.println(list); // (20, 40, 50, 80)
    }
}

七、總結

**雙向鏈表** 增加 `prev` 指針實現 O(1) 反向遍歷、已知節點 O(1) 前驅訪問，代價是雙倍指針空間與插入刪除指針操作翻倍。
**循環雙向鏈表** 首尾相連消除邊界條件，插入刪除邏輯統一，代碼更簡潔健壯。
**排序鏈表** 通過繼承復用邏輯，插入時自動維持有序，適合動態有序集合場景（如優先級隊列底層）。
**XOR 鏈表** 展示位運算巧思，但受限於 Java 內存模型與 GC，**工程上不可用**，僅作演算法面試考點與 C/C++ 系統級開發參考。
選型建議：隨機訪問多 → `ArrayList`/`動態數組`；頭尾頻繁增刪、迭代多 → `LinkedList`/`雙向鏈表`；需有序動態集合 → `TreeSet`/`排序鏈表`/跳表。