Java 實作鏈結串列與雙向鏈結串列：以物件參考替代指標的優雅實現

前言：Java 無指標也能玩轉鏈結串列

鏈結串列是基本重要的資料結構。C/C++ 靠指標實作，Java 雖無指標語法，但**物件參考本質即指標**（概念層面），反而因記憶體自動管理、型別安全，實作更簡潔優雅。

單向鏈結串列設計

節點類別

class Node {
    Object data;  // 使用 Object 型別支援任意資料
    Node next;    // 指向下一節點
    Node(Object d) { data = d; next = null; }
}

串列控制類別 List

維護四個關鍵欄位：

• Head：首節點
• Tail：尾節點 (支援 O(1) 尾端插入)
• Pointer：**指向當前節點的前驅節點** (關鍵設計！null 代表當前為首節點)
• Length：節點數 (O(1) 取得大小)

為何 Pointer 指向前驅而非當前？ 刪除當前節點時，需修改前驅節點的 next 指向後繼節點以維持串列完整。若 Pointer 指向當前節點，刪除後將難以更新前驅連結。

輔助方法 cursor() 回傳當前節點：Pointer == null ? Head : Pointer.next。

核心操作方法

完整原始碼 (List.java)

import java.io.*;
public class List {
    private Node Head = null, Tail = null, Pointer = null;
    private int Length = 0;

    public void deleteAll() { Head = Tail = Pointer = null; Length = 0; }
    public void reset() { Pointer = null; }
    public boolean isEmpty() { return Length == 0; }
    public boolean isEnd() {
        if (Length == 0) throw new NullPointerException();
        if (Length == 1) return true;
        return cursor() == Tail;
    }
    public Object nextNode() {
        if (Length <= 1) throw new NoSuchElementException();
        Node temp = cursor();
        Pointer = temp;
        if (temp != Tail) return temp.next.data;
        throw new NoSuchElementException();
    }
    public Object currentNode() { return cursor().data; }
    public void insert(Object d) {
        Node e = new Node(d);
        if (Length == 0) { Head = Tail = e; }
        else {
            Node temp = cursor();
            e.next = temp;
            if (Pointer == null) Head = e;
            else Pointer.next = e;
        }
        Length++;
    }
    public int size() { return Length; }
    public Object remove() {
        if (Length == 0) throw new NoSuchElementException();
        Object temp;
        if (Length == 1) { temp = Head.data; deleteAll(); }
        else {
            Node cur = cursor();
            temp = cur.data;
            if (cur == Head) Head = cur.next;
            else if (cur == Tail) { Pointer.next = null; Tail = Pointer; reset(); }
            else Pointer.next = cur.next;
            Length--;
        }
        return temp;
    }
    private Node cursor() {
        if (Head == null) throw new NullPointerException();
        return (Pointer == null) ? Head : Pointer.next;
    }
    // main() 示範基本用法：插入 1~10、遍歷列印、逐一刪除、驗證空串列
    public static void main(String[] args) { ... }
}
class Node { Object data; Node next; Node(Object d) { data = d; next = null; } }

雙向鏈結串列擴展

節點類別新增 previous 參考：

class Node {
    Object data;
    Node next, previous;
    Node(Object d) { data = d; next = previous = null; }
}

操作邏輯相似，插入/刪除時同步維護 next 與 previous 兩向連結。此架構亦可直接應用於堆疊 (Stack) 與佇列 (Queue) 實作，讀者可自行嘗試修改 List 類別實現。

結語

Java 物件參考機制讓鏈結串列實作既直觀又安全。掌握「Pointer 指向前驅」的設計精髓，能靈活處理插入刪除邊界條件。這份實作不僅是資料結構練習，更展現 Java 以高層抽象簡化底層操作的語言哲學。