Java 創建鏈表：單向/雙向節點定義與插入比較邏輯

節點定義

// 單向鏈表
class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }
}

// 雙向鏈表
class DNode {
    int data;
    DNode prev, next;
    DNode(int data) { this.data = data; }
}

插入邏輯（單向為例）

// 尾插
public void addLast(int data) {
    Node n = new Node(data);
    if (head == null) { head = tail = n; }
    else { tail.next = n; tail = n; }
    size++;
}

// 按值有序插入
public void addSorted(int data) {
    Node n = new Node(data);
    if (head == null || data <= head.data) { n.next = head; head = n; return; }
    Node cur = head;
    while (cur.next != null && cur.next.data < data) cur = cur.next;
    n.next = cur.next; cur.next = n;
    if (n.next == null) tail = n;
    size++;
}

前驅節點獲取

• 單向鏈表：遍歷時保留 prev 引用，或用 while (cur.next != null && cur.next.data < target) 讓 cur 停在前驅。
• 雙向鏈表：直接 node.prev O(1) 獲取。

比較邏輯

節點間比較僅比較 data 域（或自定義 Comparator），不要比較引用地址。

掌握節點定義、插入位置查找、前驅獲取三要素，手寫鏈表不再是難題。