Java 手寫單鏈表實現：從節點定義到增刪查改核心操作全解析

Java 手寫單鏈表實現：從節點定義到增刪查改核心操作全解析

單鏈表是數據結構入門必修課。本文通過完整 Java 代碼實現單鏈表核心功能：頭插法建表、頭刪除、指定位置插入/刪除、查找元素位置、獲取長度、遍歷打印，助你吃透指鏈表指針操作本質。

1. 節點類 Node

class Node {
    Node next; // 後繼指針
    int data;  // 數據域 (簡化為 int)

    public Node(int data) { this.data = data; }
}

2. 單鏈表類 LinkList 核心實現

class LinkList {
    private Node first; // 頭節點引用

    public LinkList() { this.first = null; }

    // --- 頭插法添加 (O(1)) ---
    public void addNode(Node node) {
        node.next = first;
        first = node;
    }

    // --- 頭刪除 (O(1)) ---
    public void deleteHead() {
        if (first != null) {
            first = first.next; // GC 自動回收原頭節點
        }
    }

    // --- 獲取長度 (O(n)) ---
    public int size() {
        int count = 0;
        Node curr = first;
        while (curr != null) {
            count++;
            curr = curr.next;
        }
        return count;
    }

    // --- 指定位置刪除 (1-based 索引) ---
    public void deleteAt(int pos) {
        if (pos <= 0 || first == null) return;
        if (pos == 1) { deleteHead(); return; }
        Node prev = first;
        for (int i = 1; i < pos - 1 && prev != null; i++) prev = prev.next;
        if (prev != null && prev.next != null) {
            prev.next = prev.next.next; // 跳過目標節點
        }
    }

    // --- 指定位置插入 (1-based 索引) ---
    public void insertAt(int pos, Node node) {
        if (pos <= 0) return;
        if (pos == 1) { addNode(node); return; }
        Node prev = first;
        for (int i = 1; i < pos - 1 && prev != null; i++) prev = prev.next;
        if (prev != null) {
            node.next = prev.next;
            prev.next = node;
        }
    }

    // --- 查找元素位置 (1-based)，未找到返回 -1 ---
    public int find(int value) {
        int pos = 1;
        Node curr = first;
        while (curr != null) {
            if (curr.data == value) return pos;
            curr = curr.next;
            pos++;
        }
        return -1;
    }

    // --- 遍歷打印 ---
    public void printAll() {
        Node curr = first;
        while (curr != null) {
            System.out.print(curr.data + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }
}

3. 測試驗證

public class LinkListDemo {
    public static void main(String[] args) {
        LinkList list = new LinkList();
        // 頭插: 20 -> 19 -> 18 -> 15 -> 12
        list.addNode(new Node(12));
        list.addNode(new Node(15));
        list.addNode(new Node(18));
        list.addNode(new Node(19));
        list.addNode(new Node(20));
        System.out.println("初始長度: " + list.size()); // 5
        list.printAll(); // 20 -> 19 -> 18 -> 15 -> 12 -> null

        list.deleteAt(3); // 刪除第3個 (18)
        list.insertAt(3, new Node(100)); // 第3位插入 100
        System.out.println("修改後長度: " + list.size()); // 5
        list.printAll(); // 20 -> 19 -> 100 -> 15 -> 12 -> null

        System.out.println("查找 100 位置: " + list.find(100)); // 3
        System.out.println("查找 999 位置: " + list.find(999)); // -1
    }
}

4. 核心操作複雜度與圖解要點

5. 進階擴展方向

• 虛擬頭節點 (Dummy Head)：統一頭節點與普通節點邏輯，簡化邊界判斷。
• 雙向鏈表：節點增加 prev 指針，支持雙向遍歷、O(1) 刪除已知節點。
• 循環鏈表：尾節點指向頭節點，適用於循環輪詢場景 (如 Josephus 問題)。
• 泛型化：class Node<E> { E data; Node<E> next; } 支持任意類型數據。
• 實現 Collection/Iterable 接口：融入 Java 集合框架體系。

手寫鏈表是理解引用操作、指針邏輯、邊界條件的最佳練習，**畫圖演示每一步指針變更** 是攻克難點的關鍵！