Java 手寫單向鏈表與雙向鏈表完整實現教學

前言

鏈表是基礎數據結構，理解其指針操作對掌握集合框架源碼 (如 LinkedList) 至關重要。本文提供教學級完整實現代碼。

單向鏈表實現

public class SinglyLinkedList {
    private static class Node {
        int data;
        Node next;
        Node(int data) { this.data = data; }
    }
    
    private Node head; // 頭節點
    
    // 頭插法 O(1)
    public void addFirst(int data) {
        Node node = new Node(data);
        node.next = head;
        head = node;
    }
    
    // 尾插法 O(n) - 無尾指針
    public void addLast(int data) {
        Node node = new Node(data);
        if (head == null) { head = node; return; }
        Node cur = head;
        while (cur.next != null) cur = cur.next;
        cur.next = node;
    }
    
    // 指定位置插入 (1-based)
    public void insert(int index, int data) {
        if (index <= 1) { addFirst(data); return; }
        Node prev = getNode(index - 1);
        if (prev == null) throw new IndexOutOfBoundsException();
        Node node = new Node(data);
        node.next = prev.next;
        prev.next = node;
    }
    
    // 刪除指定位置
    public void delete(int index) {
        if (head == null) return;
        if (index <= 1) { head = head.next; return; }
        Node prev = getNode(index - 1);
        if (prev == null || prev.next == null) return;
        prev.next = prev.next.next;
    }
    
    // 查找節點 (1-based)
    private Node getNode(int index) {
        Node cur = head;
        for (int i = 1; cur != null && i < index; i++) cur = cur.next;
        return cur;
    }
    
    public void print() {
        for (Node cur = head; cur != null; cur = cur.next) {
            System.out.print(cur.data + " -> ");
        }
        System.out.println("null");
    }
}

雙向鏈表實現

public class DoublyLinkedList {
    private static class Node {
        int data;
        Node prev, next;
        Node(int data) { this.data = data; }
    }
    
    private Node head, tail; // 頭尾指針
    
    // 頭插
    public void addFirst(int data) {
        Node node = new Node(data);
        if (head == null) { head = tail = node; }
        else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }
    
    // 尾插 O(1)
    public void addLast(int data) {
        Node node = new Node(data);
        if (tail == null) { head = tail = node; }
        else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }
    
    // 正序遍歷
    public void printForward() {
        for (Node cur = head; cur != null; cur = cur.next) {
            System.out.print(cur.data + " <-> ");
        }
        System.out.println("null");
    }
    
    // 逆序遍歷
    public void printBackward() {
        for (Node cur = tail; cur != null; cur = cur.prev) {
            System.out.print(cur.data + " <-> ");
        }
        System.out.println("null");
    }
    
    // 指定位置插入 (雙向指針修正關鍵：4 個指針)
    public void insert(int index, int data) {
        if (index <= 1) { addFirst(data); return; }
        Node prev = getNode(index - 1);
        if (prev == null) { addLast(data); return; }
        
        Node node = new Node(data);
        Node next = prev.next;
        
        // 核心四步指針重連
        node.prev = prev;
        node.next = next;
        prev.next = node;
        if (next != null) next.prev = node;
        else tail = node; // 插在尾部
    }
    
    private Node getNode(int index) {
        Node cur = head;
        for (int i = 1; cur != null && i < index; i++) cur = cur.next;
        return cur;
    }
}

核心區別對比

學習要點總結

1. 畫圖：動手畫指針變化圖，特別是插入/刪除的 4 步重連
2. 邊界：空表、頭尾、越界情況必測
3. 遞歸/迭代：嘗試用遞歸實現反轉、合併等進階操作
4. 對比源碼：閱讀 java.util.LinkedList 源碼驗證理解