Java 手寫單向鏈表：從節點設計到完整 CRUD

鏈表 vs 陣列

鏈表適合**頻繁頭部操作、未知資料量、不需隨機存取**的場景 (如 LRU Cache、檔案系統目錄)。

節點設計

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

完整 NodeList 實作

public class NodeList<E> {
    private Node<E> head;      // 虛擬頭節點 (哨兵)，簡化邊界條件
    private Node<E> tail;      // 尾指針，支援 O(1) 尾插
    private int size;          // 節點數

    public NodeList() { head = new Node<>(null); }

    // ---- 尾插 O(1) ----
    public void add(E data) {
        Node<E> node = new Node<>(data);
        if (tail == null) { head.next = tail = node; }
        else { tail.next = node; tail = node; }
        size++;
    }

    // ---- 指定元素後插入 ----
    public boolean addAfter(E target, E data) {
        Node<E> cur = head.next;
        while (cur != null) {
            if (eq(cur.data, target)) {
                Node<E> node = new Node<>(data);
                node.next = cur.next;
                cur.next = node;
                if (cur == tail) tail = node;
                size++; return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // ---- 獲取索引元素 ----
    public E get(int index) {
        checkIndex(index);
        Node<E> cur = head.next;
        for (int i = 0; i < index; i++) cur = cur.next;
        return cur.data;
    }

    // ---- 修改元素 ----
    public boolean set(E oldVal, E newVal) {
        Node<E> cur = head.next;
        while (cur != null) {
            if (eq(cur.data, oldVal)) { cur.data = newVal; return true; }
            cur = cur.next;
        }
        return false;
    }

    // ---- 刪除元素 (首次出現) ----
    public boolean remove(E data) {
        Node<E> prev = head;
        Node<E> cur = head.next;
        while (cur != null) {
            if (eq(cur.data, data)) {
                prev.next = cur.next;
                if (cur == tail) tail = prev == head ? null : prev;
                size--; return true;
            }
            prev = cur;
            cur = cur.next;
        }
        return false;
    }

    // ---- 查詢 ----
    public boolean contains(E data) {
        Node<E> cur = head.next;
        while (cur != null) { if (eq(cur.data, data)) return true; cur = cur.next; }
        return false;
    }

    public boolean isEmpty() { return size == 0; }
    public int size() { return size; }
    public void clear() { head.next = null; tail = null; size = 0; }

    // ---- 列印 ----
    public void print() {
        if (isEmpty()) { System.out.println("空鏈表"); return; }
        Node<E> cur = head.next;
        while (cur != null) { System.out.print(cur.data + " -> "); cur = cur.next; }
        System.out.println("null");
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index);
    }
    private boolean eq(Object a, Object b) { return a == null ? b == null : a.equals(b); }
}

關鍵設計亮點

1. 虛擬頭節點 (Sentinel)：head 不存資料，head.next 指向真實首節點。刪除首節點、空表操作無需特判，程式碼極度簡潔。
2. 尾指針 tail：尾插、指定元素後插入更新尾部皆 O(1)。
3. 統一 eq() 比較：正確處理 null 元素比較，避免 NullPointerException。
4. 刪除更新 tail：刪除尾節點時正確回退 tail 指針。

測試驗證

public static void main(String[] args) {
    NodeList list = new NodeList<>();
    list.add("A"); list.add("B"); list.add("C");
    list.print(); // A -> B -> C -> null

    list.addAfter("B", "B2");
    list.print(); // A -> B -> B2 -> C -> null

    list.set("B2", "B_NEW");
    list.print(); // A -> B -> B_NEW -> C -> null

    list.remove("B");
    list.print(); // A -> B_NEW -> C -> null

    System.out.println("Size: " + list.size()); // 3
    System.out.println("Contains C: " + list.contains("C")); // true
    System.out.println("Get(1): " + list.get(1)); // B_NEW
}

進階延伸

• 🔄 雙向鏈表：節點增 prev，支援雙向遍歷、O(1) 刪除任意節點 (Java LinkedList 即雙向)。
• 🔁 循環鏈表：tail.next = head，適用於輪詢調度、Josephus 問題。
• ⚡ 無鎖並發鏈表：CAS 操作 next 指針，參考 ConcurrentLinkedQueue 實現。

手寫鏈表是理解指標/引用操作、遞歸與迴圈轉換的最佳練習，也是面試高頻考點。

1. 上一篇文章： Java 分布式唯一 ID 生成：時間戳 + 原子計數器實作
2. 下一篇文章： Java HttpURLConnection 發送 GET/POST 請求工具類

Java 相關知識

Spring 整合 Shiro 權限管理與資料庫設計完整實戰指南

前言：細粒度權限控制的必要性 現代後台管理系統需實現「從選單

Java 反射機制工程實戰：從核心 API 到框架級應用模式

本文結合企業級框架 (Hotweb MVC) 實際代碼，系統

基於 Swing 的圖書館系統 XML 框架設計

緊縮的市場倒逼開發效率提升。標準 GUI 應用以面板流轉為核

Spring IoC 入門實戰：從工廠模式到依賴注入的完整演進

Spring 模組化與 IoC 核心概念 Spring 模組