您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 單向鏈表核心操作完整實現指南

編輯：Java 相關知識

前言：為何要掌握鏈表？

在 Java 開發中，ArrayList 底層基於動態數組，隨機存取極快，但頻繁在中間插入、刪除元素時需大量搬移資料，效能較差。相反，LinkedList 採用鏈表結構，犧牲隨機存取速度，換取 O(1) 級別的頭尾增刪優勢。本文將從零開始，手把手帶你實現一個功能完整的單向鏈表，包含節點定義、增刪改查、遍歷等核心操作，並附帶完整可運行代碼。

核心概念：節點與鏈表結構

單向鏈表由一系列節點串聯而成。每個節點包含兩部分：

數據域：儲存實際業務資料（如 int、String 或泛型對象）。
指針域：指向下一個節點的引用，末尾節點指向 null。

鏈表對外僅暴露 頭節點，所有操作均從頭節點出發，順着 next 引用向後遍歷。

代碼實現：分模組講解

1. 節點類

package com.tyxh.link;

public class Node {
    Node next;           // 指針域
    int data;            // 數據域（示例用 int，實際可用泛型）

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

    public void display() {
        System.out.print(data + " ");
    }
}

2. 單向鏈表核心類

package com.tyxh.link;

public class LinkList {
    public Node first;   // 頭節點
    private int pos = 0; // 輔助定位變量

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

    // --- 頭插法 ---
    public void addFirstNode(int data) {
        Node node = new Node(data);
        node.next = first;
        first = node;
    }

    // --- 刪除頭節點 ---
    public Node deleteFirstNode() {
        if (first == null) return null;
        Node temp = first;
        first = first.next;
        return temp;
    }

    // --- 指定位置插入 (index 之前) ---
    public void add(int index, int data) {
        if (index <= 0) { addFirstNode(data); return; }
        Node node = new Node(data);
        Node current = first, previous = first;
        pos = 0;
        while (current != null && pos != index) {
            previous = current;
            current = current.next;
            pos++;
        }
        node.next = current;
        previous.next = node;
        pos = 0;
    }

    // --- 按位置刪除 ---
    public Node deleteByPos(int index) {
        if (first == null) return null;
        Node current = first, previous = first;
        pos = 0;
        while (current != null && pos != index) {
            previous = current;
            current = current.next;
            pos++;
        }
        if (current == null) return null; // 越界
        if (current == first) first = first.next;
        else previous.next = current.next;
        pos = 0;
        return current;
    }

    // --- 按數據值刪除首個匹配節點 ---
    public Node deleteByData(int data) {
        Node current = first, previous = first;
        while (current != null && current.data != data) {
            previous = current;
            current = current.next;
        }
        if (current == null) return null;
        if (current == first) first = first.next;
        else previous.next = current.next;
        return current;
    }

    // --- 遍歷輸出 ---
    public void displayAllNodes() {
        Node current = first;
        while (current != null) {
            current.display();
            current = current.next;
        }
        System.out.println();
    }

    // --- 按位置查找 ---
    public Node findByPos(int index) {
        Node current = first;
        pos = 0;
        while (current != null && pos != index) {
            current = current.next;
            pos++;
        }
        return current;
    }

    // --- 按數據查找 ---
    public Node findByData(int data) {
        Node current = first;
        while (current != null && current.data != data) {
            current = current.next;
        }
        return current;
    }
}

3. 測試驗證

package com.tyxh.link;

public class TestLinkList {
    public static void main(String[] args) {
        LinkList list = new LinkList();
        list.addFirstNode(20);
        list.addFirstNode(21);
        list.addFirstNode(19);      // 19 -> 21 -> 20
        list.add(1, 22);            // 19 -> 22 -> 21 -> 20
        list.add(2, 23);            // 19 -> 22 -> 23 -> 21 -> 20
        list.add(3, 99);            // 19 -> 22 -> 23 -> 99 -> 21 -> 20
        list.displayAllNodes();

        Node del = list.deleteByData(19);
        System.out.println("刪除節點: " + (del != null ? del.data : "null"));
        list.displayAllNodes();

        System.out.println("位置 0: " + list.findByPos(0).data);
        System.out.println("數值 22: " + list.findByData(22).data);
    }
}

效能對比與避坑指南

操作	ArrayList (數組)	LinkedList (鏈表)
隨機存取 get(i)	O(1)	O(n)
頭部插入/刪除	O(n)	O(1)
尾部插入	O(1) 均攤	O(1) 或 O(n) 視是否維護 tail
中間插入/刪除	O(n) 搬移	O(n) 定位 + O(1) 操作
記憶體開銷	低 (連續空間)	高 (額外引用)