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

Java 單鏈表完整實現：從節點定義到增刪查改核心操作

編輯：Java 相關知識

數據結構基礎：單鏈表結構圖解

[Head] → [Node: data=10 | next] → [Node: data=20 | next] → [Node: data=30 | next] → null
           ▲                      ▲                      ▲
        first (引用)           節點 2                 節點 3

頭節點：不存儲數據，僅指向首個數據節點
數據節點：包含 data (數據域) 與 next (指針域)
尾節點：next == null

核心類設計

1. 節點類

public class Node {
    public int data;      // 數據域（示例用 int，實際可泛型化）
    public Node next;     // 指針域
    
    public Node(int data) {
        this.data = data;
    }
    
    public void display() {
        System.out.print(data + " ");
    }
}

2. 單鏈表類

public class SinglyLinkedList {
    private Node head;    // 頭節點引用
    private int size;     // 尺寸計數器
    
    public SinglyLinkedList() {
        this.head = null;
        this.size = 0;
    }
    
    // ========== 核心操作 ==========
    
    // 头插法：O(1)
    public void addFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    // 尾插法：O(n) - 無尾指針情況
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node cur = head;
            while (cur.next != null) cur = cur.next;
            cur.next = newNode;
        }
        size++;
    }
    
    // 指定位置插入：O(n)
    public void add(int index, int data) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException();
        if (index == 0) { addFirst(data); return; }
        
        Node newNode = new Node(data);
        Node prev = getNode(index - 1);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }
    
    // 刪除首節點：O(1)
    public Node removeFirst() {
        if (head == null) return null;
        Node removed = head;
        head = head.next;
        removed.next = null; // 幫助 GC
        size--;
        return removed;
    }
    
    // 指定位置刪除：O(n)
    public Node remove(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        if (index == 0) return removeFirst();
        
        Node prev = getNode(index - 1);
        Node removed = prev.next;
        prev.next = removed.next;
        removed.next = null;
        size--;
        return removed;
    }
    
    // 按值刪除首個匹配：O(n)
    public boolean removeByValue(int data) {
        if (head == null) return false;
        if (head.data == data) { removeFirst(); return true; }
        
        Node prev = head;
        while (prev.next != null) {
            if (prev.next.data == data) {
                Node removed = prev.next;
                prev.next = removed.next;
                removed.next = null;
                size--;
                return true;
            }
            prev = prev.next;
        }
        return false;
    }
    
    // 按位置查找：O(n)
    public Node get(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        return getNode(index);
    }
    
    // 按值查找：O(n)
    public Node findByValue(int data) {
        Node cur = head;
        while (cur != null) {
            if (cur.data == data) return cur;
            cur = cur.next;
        }
        return null;
    }
    
    // 遍歷輸出
    public void displayAll() {
        Node cur = head;
        while (cur != null) {
            cur.display();
            cur = cur.next;
        }
        System.out.println();
    }
    
    // 獲取長度
    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }
    
    // 內部輔助：獲取第 index 個節點 (0-based)
    private Node getNode(int index) {
        Node cur = head;
        for (int i = 0; i < index; i++) cur = cur.next;
        return cur;
    }
}

測試驗證

public class LinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        
        // 头插：30 → 20 → 10
        list.addFirst(10);
        list.addFirst(20);
        list.addFirst(30);
        System.out.print("头插後: "); list.displayAll(); // 30 20 10
        
        // 尾插：30 20 10 40 50
        list.addLast(40);
        list.addLast(50);
        System.out.print("尾插後: "); list.displayAll(); // 30 20 10 40 50
        
        // 指定位置插入：索引 2 插入 99 → 30 20 99 10 40 50
        list.add(2, 99);
        System.out.print("索引2插入99: "); list.displayAll();
        
        // 刪除首節點
        list.removeFirst();
        System.out.print("刪除首節點: "); list.displayAll(); // 20 99 10 40 50
        
        // 刪除索引 2
        list.remove(2);
        System.out.print("刪除索引2: "); list.displayAll(); // 20 99 40 50
        
        // 按值刪除
        list.removeByValue(99);
        System.out.print("刪除值99: "); list.displayAll(); // 20 40 50
        
        // 查找
        System.out.println("索引1元素: " + list.get(1).data); // 40
        System.out.println("查找值50: " + (list.findByValue(50) != null ? "存在" : "不存在"));
        System.out.println("鏈表長度: " + list.size());
    }
}

性能複雜度總結

操作	時間複雜度	空間複雜度	說明
頭插/頭刪	O(1)	O(1)	僅修改 head 指針
尾插(無尾指針)	O(n)	O(1)	需遍歷尋找尾節點
尾插(有尾指針)	O(1)	O(1)	維護 tail 引用
指定位置增/刪/查	O(n)	O(1)	需從頭遍歷至目標位置
按值查找/刪除	O(n)	O(1)	最壞情況遍歷全表