Java 手寫單鏈表、雙端鏈表與棧佇列應用完整教學

線性表與鏈表基礎知識

線性表：元素間一對一關係，除首尾節點外各有唯一前驅後繼。邏輯結構簡單，常以棧、佇列、字串等受限形式應用。

鏈表：物理存儲不連續，透過指標串聯邏輯順序。優勢在於頭部插入刪除 O(1)，劣勢在於隨機訪問 O(N)。

一、單鏈表兩種構建方式

1. 頭插法（後進先出）

新節點總是插在頭節點後，首個插入的節點成為尾節點。適合實現棧。

public class SingleLinkedList<T> {
    private Node<T> first;
    
    public void insertFirst(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = first;
        first = newNode;
    }
    
    public Node<T> deleteFirst() {
        if (first == null) return null;
        Node<T> temp = first;
        first = first.next;
        return temp;
    }
    // ... find, delete, display, reverse
    static class Node<T> { T data; Node<T> next; Node(T d){data=d;} }
}

2. 尾插法（先進先出）

維護尾指標 rear，新節點接在尾部。適合實現佇列。

public class SingleLinkedList2<T> {
    private Node<T> head, rear;
    
    public void insertLast(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) { head = rear = newNode; }
        else { rear.next = newNode; rear = newNode; }
    }
    // ... deleteLast, find, delete, display, reverse
}

3. 單鏈表就地反轉（三指針法）

public void reverse() {
    Node<T> prev = null, curr = first, next;
    while (curr != null) {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    first = prev;
}

二、雙端鏈表：同時擁有頭尾指標

在單鏈表基礎上增加 rear 指向尾節點，使尾部插入也能 O(1)。刪除尾部仍需 O(N)（需找前驅），除非改為雙向鏈表。

public class TwoEndpointList<T> {
    private Node<T> head, rear;
    
    public void insertFirst(T data) { /* 同單鏈表頭插 */ }
    public void insertLast(T data) { /* 利用 rear 直接尾插 O(1) */ }
    public T deleteHead() { /* 刪頭 O(1) */ }
    // 刪尾需遍歷找倒數第二個，O(N)
}

三、鏈表實現棧與佇列

1. 基於雙端鏈表的棧

棧只需單端操作，直接複用 insertFirst/deleteHead。

public class LinkStack<T> {
    private TwoEndpointList<T> list = new TwoEndpointList<>();
    public void push(T data) { list.insertFirst(data); }
    public T pop() { return list.deleteHead(); }
    public T peek() { return list.peekHead(); }
    public boolean isEmpty() { return list.isEmpty(); }
}

2. 基於雙端鏈表的佇列

佇列頭刪尾增，完美映射 deleteHead/insertLast。

public class LinkQueue<T> {
    private TwoEndpointList<T> list = new TwoEndpointList<>();
    public void insert(T data) { list.insertLast(data); }  // 入隊
    public T remove() { return list.deleteHead(); }        // 出隊
    public T peek() { return list.peekHead(); }
    public boolean isEmpty() { return list.isEmpty(); }
}

四、有序鏈表與插入排序

維持節點按關鍵字有序。插入需查找位置 O(N)，刪除最小值（頭節點）O(1)。適用於優先權佇列、頻繁存取極值場景。

public class SortedLinkedList<T extends Comparable<T>> {
    public void insert(T data) {
        Node<T> newNode = new Node<>(data), curr = first, prev = null;
        while (curr != null && data.compareTo(curr.data) > 0) {
            prev = curr; curr = curr.next;
        }
        if (prev == null) first = newNode;
        else prev.next = newNode;
        newNode.next = curr;
    }
    // 可用於鏈表插入排序：遍歷陣列插入有序鏈表，再遍歷輸出
}

總結對比表

* 需維護 rear 指標

避坑指南

• 空鏈表邊界：所有操作首檢 first == null
• 單節點特殊處理：刪除後 first = rear = null
• 反轉時斷鏈：原頭節點 next 必須置 null
• 泛型比較：有序鏈表要求 T extends Comparable<T>

手寫鏈表是理解指標、記憶體模型、遞迴的最佳練習。建議在紙上畫圖推演每個操作的指標變化，再敲代碼驗證。