您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

Java 鏈表結構完整實現指南：從節點定義到核心操作詳解

編輯：Java 綜合教學

Java 鏈表結構完整實現指南

鏈表作為基礎數據結構之一，在 Java 開發中雖然不如 ArrayList 常用，但理解其底層實現對於掌握集合框架原理、面試準備以及解決特定性能場景至關重要。本文將從零開始，手把手帶你實現一個功能完整的單向鏈表，涵蓋節點定義、增刪改查等核心操作，並附帶完整代碼示例。

一、數據結構設計：節點與鏈表類

鏈表的核心在於「節點」。每個節點包含兩部分：數據域與指向下一個節點的引用（指針）。在 Java 中，我們通過類來封裝這一結構。

1. 定義數據載體

首先定義一個簡單的數據類，用於存儲節點承載的業務信息，例如鍵值、姓名、年齡等。

class DataNode {
    String key;    // 唯一標識，用於查找
    String name;
    int age;
    
    // 建議添加構造函數、Getter/Setter 及 toString 方法
}

2. 定義鏈表節點

節點類持有數據對象，並包含一個指向同類型下一個節點的引用 next。

class ListNode {
    DataNode data;
    ListNode next;

    public ListNode(DataNode data) {
        this.data = data;
        this.next = null;
    }
}

二、核心操作實現

以下所有操作均基於頭節點 head 進行，若鏈表為空則 head == null。

1. 尾部追加節點

邏輯：創建新節點 → 遍歷至尾節點 → 將尾節點的 next 指向新節點。

public ListNode append(ListNode head, DataNode data) {
    ListNode newNode = new ListNode(data);
    if (head == null) {
        return newNode; // 空鏈表，新節點即為頭節點
    }
    ListNode current = head;
    while (current.next != null) { // 找到最後一個節點
        current = current.next;
    }
    current.next = newNode;
    return head;
}

2. 頭部插入節點

邏輯：創建新節點 → 新節點的 next 指向原頭節點 → 返回新節點作為新頭節點。時間複雜度 O(1)。

public ListNode addFirst(ListNode head, DataNode data) {
    ListNode newNode = new ListNode(data);
    newNode.next = head;
    return newNode;
}

3. 按鍵值查找節點

遍歷鏈表，比對節點數據中的 key 字段（注意：字符串比較應用 .equals()）。

public ListNode find(ListNode head, String key) {
    ListNode current = head;
    while (current != null) {
        if (current.data != null && current.data.key.equals(key)) {
            return current;
        }
        current = current.next;
    }
    return null; // 未找到
}

4. 指定節點後插入

先查找目標節點，再調整指針：新節點.next = 目標節點.next；目標節點.next = 新節點。

public ListNode insertAfter(ListNode head, String targetKey, DataNode data) {
    ListNode target = find(head, targetKey);
    if (target == null) {
        System.out.println("未找到插入位置: " + targetKey);
        return head;
    }
    ListNode newNode = new ListNode(data);
    newNode.next = target.next;
    target.next = newNode;
    return head;
}

5. 刪除指定鍵值節點

需維護前驅節點引用。若刪除頭節點，直接返回 head.next；否則將前驅節點.next 指向被刪節點.next。

public ListNode delete(ListNode head, String key) {
    if (head == null) return null;
    
    // 處理頭節點刪除
    if (head.data != null && head.data.key.equals(key)) {
        return head.next;
    }
    
    ListNode prev = head;
    ListNode current = head.next;
    while (current != null) {
        if (current.data != null && current.data.key.equals(key)) {
            prev.next = current.next; // 跳過當前節點
            return head;
        }
        prev = current;
        current = current.next;
    }
    return head; // 未找到
}

6. 獲取鏈表長度

public int length(ListNode head) {
    int count = 0;
    ListNode current = head;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}

7. 遍歷打印所有節點

public void printAll(ListNode head) {
    System.out.println("鏈表長度: " + length(head));
    ListNode current = head;
    while (current != null) {
        DataNode d = current.data;
        System.out.printf("Key: %s, Name: %s, Age: %d%n", 
            d.key, d.name, d.age);
        current = current.next;
    }
}

三、完整測試示例

public class LinkedListDemo {
    public static void main(String[] args) {
        ListNode head = null;
        LinkedListDemo demo = new LinkedListDemo();
        
        // 測試尾插
        head = demo.append(head, new DataNode("1", "Alice", 25));
        head = demo.append(head, new DataNode("2", "Bob", 30));
        
        // 測試頭插
        head = demo.addFirst(head, new DataNode("0", "HeadNode", 20));
        
        // 測試中間插入
        head = demo.insertAfter(head, "1", new DataNode("1.5", "Middle", 28));
        
        // 打印
        demo.printAll(head);
        
        // 測試刪除
        head = demo.delete(head, "1.5");
        System.out.println("\n--- 刪除後 ---");
        demo.printAll(head);
    }
}