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

Java 資料結構：單向與雙向鏈結串列完整實作指南

編輯：Java 相關知識

鏈結串列基礎概念

鏈結串列由節點組成，每個節點包含資料域與指標域。依指標方向分為：

單向鏈結串列：節點僅有 next 指向後繼節點
雙向鏈結串列：節點同時有 prev (前驅) 與 next (後繼)
循環鏈結串列：尾節點指向頭節點 (單向/雙向皆可)

統一介面定義

package list;

import java.util.Map;

public interface IListOps<T> {
    boolean insertNode(T node);                    // 尾部插入
    boolean insertPosNode(int pos, T node);        // 指定位置插入 (1-based)
    boolean deleteNode(int pos);                   // 指定位置刪除
    boolean updateNode(int pos, Map<String, Object> data); // 更新節點資料
    T getNode(int pos, Map<String, Object> data); // 取得節點
    void printList();                              // 列印整個串列
    int getSize();                                 // 取得長度
}

一、單向鏈結串列實作

節點類別

package list;

public class SNode {
    private String data;
    private SNode next;

    public SNode() {}
    public SNode(String data) { this.data = data; }

    public String getData() { return data; }
    public void setData(String data) { this.data = data; }
    public SNode getNext() { return next; }
    public void setNext(SNode next) { this.next = next; }

    @Override
    public String toString() { return "SNode[data=" + data + "]"; }
}

核心操作類別

package list;

import java.util.HashMap;
import java.util.Map;

public class SinglyLinkedList implements IListOps<SNode> {
    private final SNode head = new SNode("HEAD"); // 虛擬頭節點，不存資料
    private int size = 0;

    @Override
    public int getSize() { return size; }

    /** 尾部插入 O(n) - 若維護 tail 指標可優化為 O(1) */
    @Override
    public boolean insertNode(SNode node) {
        SNode curr = head;
        while (curr.getNext() != null) curr = curr.getNext();
        curr.setNext(node);
        node.setNext(null);
        size++;
        return true;
    }

    /** 指定位置插入 (1-based) */
    @Override
    public boolean insertPosNode(int pos, SNode node) {
        if (pos <= 0 || pos > size + 1) return false; // 允許 pos = size+1 (尾插)
        
        SNode prev = head;
        for (int i = 1; i < pos; i++) prev = prev.getNext();
        
        node.setNext(prev.getNext());
        prev.setNext(node);
        size++;
        return true;
    }

    /** 指定位置刪除 */
    @Override
    public boolean deleteNode(int pos) {
        if (pos <= 0 || pos > size) return false;
        
        SNode prev = head;
        for (int i = 1; i < pos; i++) prev = prev.getNext();
        
        prev.setNext(prev.getNext().getNext()); // 跳過被刪節點
        size--;
        System.gc(); // 提示 GC 回收 (非強制)
        return true;
    }

    /** 更新節點資料 */
    @Override
    public boolean updateNode(int pos, Map<String, Object> data) {
        SNode node = getNode(pos, null);
        if (node != null && data != null) {
            node.setData((String) data.get("data"));
            return true;
        }
        return false;
    }

    /** 取得節點 (1-based) */
    @Override
    public SNode getNode(int pos, Map<String, Object> data) {
        if (pos <= 0 || pos > size) return null;
        SNode curr = head.getNext();
        for (int i = 1; i < pos; i++) curr = curr.getNext();
        return curr;
    }

    /** 列印串列 */
    @Override
    public void printList() {
        System.out.println("=== 單向鏈結串列 (長度: " + size + ") ===");
        SNode curr = head.getNext();
        int idx = 1;
        while (curr != null) {
            System.out.println("第 " + idx++ + " 節點: " + curr);
            curr = curr.getNext();
        }
    }

    // 測試主程式
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.insertNode(new SNode("節點1"));
        list.insertNode(new SNode("節點2"));
        list.insertNode(new SNode("節點3"));
        list.insertPosNode(2, new SNode("插入節點"));
        list.printList();
        list.deleteNode(2);
        list.printList();
        list.updateNode(1, Map.of("data", "已修改"));
        list.printList();
    }
}

二、雙向鏈結串列實作

節點類別

package list;

public class DNode {
    private DNode prev;
    private String data;
    private DNode next;

    public DNode() {}
    public DNode(String data) { this.data = data; }

    public DNode getPrev() { return prev; }
    public void setPrev(DNode prev) { this.prev = prev; }
    public String getData() { return data; }
    public void setData(String data) { this.data = data; }
    public DNode getNext() { return next; }
    public void setNext(DNode next) { this.next = next; }

    @Override
    public String toString() { return "DNode[data=" + data + "]"; }
}

核心操作類別

package list;

import java.util.HashMap;
import java.util.Map;

public class DoublyLinkedList implements IListOps<DNode> {
    private final DNode head = new DNode("HEAD");
    private int size = 0;

    @Override
    public int getSize() { return size; }

    @Override
    public boolean insertNode(DNode node) {
        DNode curr = head;
        while (curr.getNext() != null) curr = curr.getNext();
        curr.setNext(node);
        node.setPrev(curr);
        node.setNext(null);
        size++;
        return true;
    }

    @Override
    public boolean insertPosNode(int pos, DNode node) {
        if (pos <= 0 || pos > size + 1) return false;
        
        DNode curr = head.getNext();
        // 找到插入位置的「後繼節點」 (若 pos=size+1 則 curr=null)
        for (int i = 1; i < pos && curr != null; i++) curr = curr.getNext();
        
        if (curr == null) { // 尾插
            DNode tail = head;
            while (tail.getNext() != null) tail = tail.getNext();
            tail.setNext(node);
            node.setPrev(tail);
            node.setNext(null);
        } else { // 中間插入
            DNode prev = curr.getPrev();
            prev.setNext(node);
            node.setPrev(prev);
            node.setNext(curr);
            curr.setPrev(node);
        }
        size++;
        return true;
    }

    @Override
    public boolean deleteNode(int pos) {
        if (pos <= 0 || pos > size) return false;
        
        DNode curr = head.getNext();
        for (int i = 1; i < pos; i++) curr = curr.getNext();
        
        DNode prev = curr.getPrev();
        DNode next = curr.getNext();
        
        prev.setNext(next);
        if (next != null) next.setPrev(prev); // 非尾節點才需設定
        
        size--;
        System.gc();
        return true;
    }

    @Override
    public boolean updateNode(int pos, Map<String, Object> data) {
        DNode node = getNode(pos, null);
        if (node != null && data != null) {
            node.setData((String) data.get("data"));
            return true;
        }
        return false;
    }

    @Override
    public DNode getNode(int pos, Map<String, Object> data) {
        if (pos <= 0 || pos > size) return null;
        DNode curr = head.getNext();
        for (int i = 1; i < pos; i++) curr = curr.getNext();
        return curr;
    }

    @Override
    public void printList() {
        System.out.println("=== 雙向鏈結串列 (長度: " + size + ") ===");
        DNode curr = head.getNext();
        int idx = 1;
        while (curr != null) {
            System.out.println("第 " + idx++ + " 節點: " + curr);
            curr = curr.getNext();
        }
    }

    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.insertPosNode(1, new DNode("節點1"));
        list.insertPosNode(2, new DNode("節點2"));
        list.insertPosNode(3, new DNode("節點3"));
        list.insertPosNode(2, new DNode("插入節點"));
        list.printList();
        list.deleteNode(4);
        list.printList();
    }
}

三、核心操作複雜度比較

操作	單向鏈結串列	雙向鏈結串列	陣列
尾部插入	O(n) / O(1)*	O(n) / O(1)*	O(1) 擴容
頭部插入	O(1)	O(1)	O(n)
指定位置插入	O(n)	O(n)	O(n)
指定位置刪除	O(n)	O(n)	O(n)
指定位置查詢	O(n)	O(n)	O(1)
反向遍歷	不可 / O(n)	O(n)	O(1)
記憶體開銷	1 指標/節點	2 指標/節點	連續記憶體

* 維護 tail 指標時

四、實際應用場景

LRU Cache：雙向鏈結串列 + HashMap (O(1) 存取、更新、淘汰)
瀏覽器歷史/前進後退：雙向鏈結串列
音樂播放清單：循環雙向鏈結串列 (上一首/下一首/循環播放)
記憶體管理：自由區鏈結串列 (配置/釋放記憶體塊)
編輯器 Undo/Redo：雙向鏈結串列 (或兩個堆疊)
HashMap 桶位 (JDK 8+)：單向鏈結串列 → 紅黑樹 (解決碰撞)

五、Java 內建實作對比

// java.util.LinkedList - 雙向鏈結串列 (實作 List + Deque)
LinkedList<String> list = new LinkedList<>();
list.add("A");           // 尾部插入
list.addFirst("B");      // 頭部插入
list.addLast("C");       // 尾部插入
list.add(1, "D");        // 指定位置插入
list.removeFirst();      // 移除頭部
list.get(0);             // 索引存取 (O(n))
list.listIterator(2);    // 從指定位置雙向迭代

// 適用場景：頻繁頭尾操作、佇列/棧、迭代器雙向遍歷
// 不適用：大量隨機存取 (用 ArrayList)

六、常見錯誤與避坑

空指標異常：未檢查 head.next == null 直接存取
斷鏈：插入/刪除時指標更新順序錯誤 (先斷後連 vs 先連後斷)
雙向串列 prev 未更新：插入/刪除忘記設定 prev
索引越界：1-based vs 0-based 混淆，邊界條件 pos > size vs pos >= size
記憶體洩漏：刪除節點後未斷開引用 (Java 有 GC 較不嚴重，C/C++ 嚴重)
併發修改：多執行緒操作非執行緒安全串列 (用 Collections.synchronizedList 或 ConcurrentLinkedQueue)

七、進階優化技巧

1. 維護尾指標 (O(1) 尾插)

private Node tail = head;
public boolean insertNode(Node node) {
    tail.setNext(node);
    tail = node;
    size++;
    return true;
}

2. 快慢指標 (找中點、檢測環、倒數第 k 個)

// 找中點
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow 即中點 (偶數長度取偏前/偏後視條件而定)

3. 虛擬頭節點 (統一邊界處理)

本文所有實作均採用 head = new Node("HEAD")，使頭部操作與中間操作邏輯一致，避免大量 if (head == null) 判斷。

總結

單向鏈結串列：結構簡單、記憶體省、適用單向遍歷、堆疊/佇列基礎
雙向鏈結串列：支援雙向遍歷、O(1) 刪除已知節點、LRU/Deque 核心結構
虛擬頭節點：簡化邊界條件處理，強烈建議採用
實務開發：優先使用 java.util.LinkedList 或 ArrayList，手寫鏈結串列僅用於面試、教學、特殊演算法 (LRU、跳表、並發結構)

掌握指標操作邏輯 (先連後斷、prev/next 對稱更新) 是鏈結串列實作的核心，多畫圖推演可避免邏輯錯誤。