Java 實作雙向鏈表 (Doubly Linked List) 完整教學

Java 實作雙向鏈表 (Doubly Linked List) 完整教學

雙向鏈表每個節點同時持有前驅與後繼引用，支援雙向遍歷與 O(1) 刪除已知節點。本文從零建構一個泛型雙向鏈表 DoubleNodeList<T>，涵蓋增刪改查、頭尾操作與邊界處理。

節點內部類別

private static class Node {
    Node prev;
    Node next;
    T data;
    public Node(T data) { this.data = data; }
}

核心欄位

private Node head;   // 頭節點
private Node tail;   // 尾節點
private int size;       // 長度

主要操作方法

新增節點 (尾插法)

public void add(T data) {
    if (isEmpty()) {
        head = tail = new Node<>(data);
    } else {
        Node node = new Node<>(data);
        node.prev = tail;
        tail.next = node;
        tail = node;
    }
    size++;
}

指定值後插入

public boolean addAfter(T target, T data) {
    Node cur = head;
    while (cur != null) {
        if (cur.data.equals(target)) {
            Node node = new Node<>(data);
            node.prev = cur;
            node.next = cur.next;
            cur.next = node;
            if (node.next == null) tail = node; // 插在尾部
            else node.next.prev = node;
            size++;
            return true;
        }
        cur = cur.next;
    }
    return false;
}

指定值前插入

public boolean addBefore(T target, T data) {
    Node cur = head;
    while (cur != null) {
        if (cur.data.equals(target)) {
            Node node = new Node<>(data);
            node.next = cur;
            node.prev = cur.prev;
            if (cur.prev == null) head = node; // 插在頭部
            else cur.prev.next = node;
            cur.prev = node;
            size++;
            return true;
        }
        cur = cur.next;
    }
    return false;
}

刪除節點

public boolean remove(T data) {
    Node cur = head;
    while (cur != null) {
        if (cur.data.equals(data)) {
            if (cur.prev != null) cur.prev.next = cur.next;
            else head = cur.next; // 刪除頭節點
            if (cur.next != null) cur.next.prev = cur.prev;
            else tail = cur.prev; // 刪除尾節點
            size--;
            return true;
        }
        cur = cur.next;
    }
    return false;
}

其他常用方法

• get(int index)：索引存取 (拋出 IndexOutOfBoundsException)
• set(T oldVal, T newVal)：替換首個匹配值
• contains(T data)、getFirst()、getLast()、getSize()、isEmpty()、clear()
• printList()：順向列印除錯用

使用範例

DoubleNodeList list = new DoubleNodeList<>();
list.add("A"); list.add("B"); list.add("C");
list.addAfter("B", "B2"); // A B B2 C
list.addBefore("C", "C1"); // A B B2 C1 C
list.remove("B");         // A B2 C1 C
System.out.println(list.get(2)); // C1

與 JDK 集合對比

* 需持有節點引用；本實作以值查找為 O(n)。

擴充方向

• 實作 Iterable、ListIterator 支援 for-each 與雙向游標。
• 加入 addAll()、subList() 等 List 介面方法。
• 無哨兵節點版本可簡化邊界判斷 (引入 dummy head/tail)。