Java 單向鏈表手寫實現：從節點定義到增刪查遍歷完整教學

資料結構基礎

單向鏈表由節點組成，每個節點包含：

• 資料域：存儲元素值
• 指針域：指向下一個節點（尾節點指向 null）

節點類定義

public class Node {
    E data;
    Node next;
    
    public Node(E data) {
        this.data = data;
    }
    
    public Node(E data, Node next) {
        this.data = data;
        this.next = next;
    }
}

鏈表核心操作實現

public class SinglyLinkedList {
    private Node head;  // 虛擬頭節點（哨兵），簡化邊界處理
    private int size;
    
    public SinglyLinkedList() {
        head = new Node<>(null);  // 哨兵節點不存儲數據
        size = 0;
    }
    
    // 獲取長度
    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }
    
    // 索引合法性檢查
    private void checkIndex(int index) {
        if (index < 0 || index >= size) 
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    private void checkIndexForAdd(int index) {
        if (index < 0 || index > size) 
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    
    // 獲取 index 位置的前驅節點（哨兵頭節點索引為 -1）
    private Node getPrevNode(int index) {
        Node prev = head;
        for (int i = -1; i < index; i++) {
            prev = prev.next;
        }
        return prev;
    }
    
    // 在 index 處插入元素
    public void add(int index, E element) {
        checkIndexForAdd(index);
        Node prev = getPrevNode(index - 1);
        prev.next = new Node<>(element, prev.next);
        size++;
    }
    
    // 尾部新增
    public void add(E element) {
        add(size, element);
    }
    
    // 獲取 index 位置元素
    public E get(int index) {
        checkIndex(index);
        return getPrevNode(index).next.data;
    }
    
    // 設置 index 位置元素
    public E set(int index, E element) {
        checkIndex(index);
        Node node = getPrevNode(index).next;
        E old = node.data;
        node.data = element;
        return old;
    }
    
    // 刪除 index 位置元素
    public E remove(int index) {
        checkIndex(index);
        Node prev = getPrevNode(index - 1);
        Node removed = prev.next;
        prev.next = removed.next;
        removed.next = null;  // 幫助 GC
        size--;
        return removed.data;
    }
    
    // 查找元素首次出現索引
    public int indexOf(E element) {
        Node cur = head.next;
        for (int i = 0; i < size; i++) {
            if (Objects.equals(element, cur.data)) return i;
            cur = cur.next;
        }
        return -1;
    }
    
    // 清空
    public void clear() {
        head.next = null;
        size = 0;
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        Node cur = head.next;
        while (cur != null) {
            sb.append(cur.data);
            if (cur.next != null) sb.append(", ");
            cur = cur.next;
        }
        sb.append(']');
        return sb.toString();
    }
}

測試驗證

public class LinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList<>();
        
        // 新增測試
        list.add(10);
        list.add(20);
        list.add(30);
        list.add(1, 15);  // [10, 15, 20, 30]
        System.out.println("插入後: " + list);
        
        // 獲取測試
        System.out.println("索引 2: " + list.get(2));  // 20
        
        // 修改測試
        list.set(1, 99);  // [10, 99, 20, 30]
        System.out.println("修改後: " + list);
        
        // 刪除測試
        list.remove(2);   // [10, 99, 30]
        System.out.println("刪除後: " + list);
        
        // 查找測試
        System.out.println("99 索引: " + list.indexOf(99));  // 1
        System.out.println("100 索引: " + list.indexOf(100)); // -1
        
        // 邊界測試
        list.add(0, 1);   // 頭部插入
        list.add(list.size(), 999); // 尾部插入
        System.out.println("邊界插入: " + list);
    }
}

進階話題

遞歸實現（教學用，生產慎用）

// 遞歸反轉
public void reverse() {
    head.next = reverseRecursive(head.next);
}

private Node reverseRecursive(Node node) {
    if (node == null || node.next == null) return node;
    Node newHead = reverseRecursive(node.next);
    node.next.next = node;
    node.next = null;
    return newHead;
}

快慢指針技巧

• 找中點：快指針走 2 步，慢指針走 1 步
• 檢測環：快慢指針相遇即有環
• 倒數第 k 個：快指針先走 k 步

效能對比：ArrayList vs LinkedList

生產環境建議

1. 99% 場景用 ArrayList：現代 CPU 緩存讓連續記憶體存取極快
2. 真正需要 LinkedList 時：極頻繁頭部操作、不可預知大小且記憶體受限、需實現隊列/棧且不想用 ArrayDeque
3. 隊列/棧首選：ArrayDeque（雙端隊列、陣列實現、無容量限制、非同步、效能優於 LinkedList）

總結

手寫鏈表是理解指針、引用、邊界條件、遞歸的最佳練習。**哨兵節點（虛擬頭節點）是簡化邊界邏輯的關鍵技巧**。生產代碼請直接使用 JDK 集合框架，但面試與底層原理理解請務必親手實現一次。

1. 上一篇文章： Java 核心類庫精選：開發者必知的 10 大高頻類深度解析
2. 下一篇文章： Java 順序表（動態陣列）手寫實現：泛型、擴容、增刪查完整源碼解析

Java 程式設計入門

Eclipse XML 開發利器：XMLBuddy 外掛安裝與實戰指南

認識 XMLBuddy XMLBuddy 是 Eclipse

Java 並發編程核心：線程池原理、配置參數與最佳實踐全解析

為什麼需要線程池？ 頻繁創建/銷毀線程開銷大，且無限制創建會

JConsole 可視化監控實戰：JVM 內存、線程、死鎖診斷全流程

一、JConsole 快速入門 啟動：JDK bin/jc

Java Web Filter 完整指南：核心概念、生命週期與鏈式調用實戰

什麼是 Filter？ 在 Java Web 開發中，Fil