Java 單向鏈表完整實作：增刪改查與遍歷詳解

資料結構設計

private static class Node<E> {
    E data;
    Node<E> next;
    Node(E e) { this.data = e; this.next = null; }
}

內部靜態類 Node 封裝資料與指標，泛型 E 支援任意類型元素。

核心欄位

• head：頭節點（哨兵或首元素）
• last：尾節點，支援 O(1) 尾插
• length：節點計數
• other：遍歷用暫存指標

主要操作實作

建構子

public NodeList() { this.head = new Node<>(null); }
public NodeList(E data) { 
    this.head = new Node<>(data); 
    this.last = head; 
    length++; 
}

尾插法 add(E)

public void add(E data) {
    if (isEmpty()) {
        head = new Node<>(data);
        last = head;
    } else {
        Node<E> n = new Node<>(data);
        last.next = n;
        last = n;
    }
    length++;
}

索引取值 get(int)

public E get(int index) {
    if (index < 0 || index >= length) 
        throw new IndexOutOfBoundsException("索引越界:" + index);
    Node<E> cur = head;
    for (int i = 0; i < index; i++) cur = cur.next;
    return cur.data;
}

指定值後插入 add(E target, E insert)

public boolean add(E target, E insert) {
    Node<E> cur = head;
    while (cur != null) {
        if (cur.data.equals(target)) {
            Node<E> n = new Node<>(insert);
            n.next = cur.next;
            cur.next = n;
            length++;
            return true;
        }
        cur = cur.next;
    }
    return false;
}

刪除指定值 remove(E)

public boolean remove(E data) {
    Node<E> cur = head, prev = head;
    while (cur != null) {
        if (cur.data.equals(data)) {
            prev.next = cur.next;
            if (cur == last) last = prev; // 維護尾指標
            length--;
            return true;
        }
        prev = cur;
        cur = cur.next;
    }
    return false;
}

其他實用方法

完整類別碼

public class NodeList<E> {
    private static class Node<E> { /* 略 */ }
    private Node<E> head, last, other;
    private int length = 0;
    /* 以上所有方法完整實作 */
}

教學重點提示

• 哨兵節點 vs 實際頭節點：本實作首節點即存資料，簡化邏輯但需注意空表處理
• 尾指標維護：插入、刪除尾節點時必須同步更新 last
• 泛型擦除：執行期 Node<E> 實為 Node，無法 new E[]，僅影響陣列建構