Java語言實現鏈表與雙向鏈表的完整指南

鏈表作為基礎且重要的數據結構，在程式設計中佔據核心地位。雖然C/C++透過指標實現鏈表，但Java雖無顯性指標，卻能利用物件引用輕鬆實現鏈表結構，甚至比C/C++更直觀簡潔。

鏈表節點的Java實現

在Java中，物件引用本質上就是指標的概念實現。我們可以定義節點類別如下：

class Node {
    Object data;  // 資料域，使用Object支援任意類型
    Node next;    // 指向下一個節點的引用
}

將資料域定義為Object類型，利用其作為所有類別的父類別特性，實現程式碼的通用性。

鏈表管理類別設計

為了方便操作，鏈表需要維護表頭、表尾、當前節點指標及長度計數器。巧妙之處在於Pointer不直接指向當前節點，而是指向其前驅節點：

• Head：指向第一個節點
• Tail：指向最後一個節點，便於尾部插入
• Pointer：指向當前節點的前驅節點（null表示當前為首節點）
• Length：記錄鏈表大小，避免遍歷統計

這種設計使刪除當前節點後，仍能輕鬆維持鏈表完整性，避免了直接指向當前節點帶來的操作困難。

核心操作方法

List類別封裝了鏈表的基本操作：

• reset()：將第一個節點設為當前節點
• insert(Object d)：在當前節點前插入新節點並設為當前
• remove()：刪除當前節點並返回其內容，後繼節點成為當前
• nextNode()：移動到下一個節點並返回其值
• currentNode()：獲取當前節點的值
• isEmpty()/isEnd()：判斷空表與是否到達尾部
• size()：O(1)時間獲取鏈表長度

關鍵原始碼片段

public class List {
    private Node Head = null;
    private Node Tail = null;
    private Node Pointer = null;
    private int Length = 0;

    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++;
    }

    private Node cursor() {
        return (Pointer == null) ? Head : Pointer.next;
    }
    // 其他方法省略...
}

透過cursor()輔助方法獲取當前節點，配合Pointer指向前驅的設計，實現了優雅的鏈表操作邏輯。