用Java學資料結構 - 雙向鏈結串列 Doubly Linked List

介紹與概念

雙向鏈結串列的定義

雙向鏈結串列 (Doubly Linked List) 是一種進階的鏈結串列，由節點 (Node) 組成，每個節點包含資料 (data)、指向下一個節點的指標 (next) 和指向前一個節點的指標 (prev)。透過這些指標，可以輕鬆地在正向和反向之間遍歷串列。

和單向鏈結串列的差異比較

特性	單向鏈結串列	雙向鏈結串列
節點結構	包含資料與下一個節點的指標	包含資料、前一個與下一個節點的指標
插入/刪除效率	相對簡單	需要更新前後節點的指標
記憶體使用	只需額外儲存一個指標	需額外儲存兩個指標
遍歷方向	僅能單向遍歷	可正向與反向遍歷

雙向鏈結串列雖然需要更多的記憶體來儲存指標，但它的雙向遍歷特性，使得操作更加靈活，適合某些需要快速插入、刪除以及雙向遍歷的應用場景。

使用場景與優缺點

✅ 雙向遍歷
- 雙向鏈結串列的最大優勢是可以從頭到尾，也可以從尾到頭遍歷，非常適合需要雙向操作的場景：
實際應用
- 音樂播放器的播放列表：支持上一首與下一首歌曲切換。
- 編輯器的撤銷與重做功能：需要追蹤前後狀態。

-✅ 插入與刪除效率高 - 和單向鏈結串列一樣，雙向鏈結串列在插入與刪除操作上也非常高效，因為只需要調整相關指標即可。

❌ 記憶體開銷
- 雙向鏈結串列需要額外的記憶體來儲存前一個節點的指標，因此在記憶體使用效率上不如單向鏈結串列與陣列。

結構與術語

節點 (Node) 的概念

雙向鏈結串列的節點由以下三部分組成：

資料 (data)：存放節點的值或資訊。
前指標 (prev)：指向前一個節點的指標。
後指標 (next)：指向下一個節點的指標。

class Node {
    int data;
    Node prev;
    Node next;

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

頭節點 (Head) 與尾節點 (Tail)

頭節點 (Head)：雙向鏈結串列的起始節點，prev 指標為 null。尾節點 (Tail)：雙向鏈結串列的結尾節點，next 指標為 null。

實作與程式碼範例

雙向鏈結串列 (Doubly Linked List) 的實作

class DoublyLinkedList {
    private Node head;
    private Node tail;

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }

    // 新增節點到頭部
    public void addFirst(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    // 新增節點到尾部
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (tail == null) {
            head = tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
    }

    // 插入節點到指定位置
    public void insert(int index, int data) {
        if (index < 0) {
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        Node current = head;
        for (int i = 0; i < index - 1 && current != null; i++) {
            current = current.next;
        }
        if (current == null) {
            return;
        }
        Node newNode = new Node(data);
        newNode.next = current.next;
        if (current.next != null) {
            current.next.prev = newNode;
        } else {
            tail = newNode;
        }
        newNode.prev = current;
        current.next = newNode;
    }

    // 刪除頭部節點
    public void removeFirst() {
        if (head == null) {
            return;
        }
        if (head.next == null) {
            head = tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
    }

    // 刪除尾部節點
    public void removeLast() {
        if (tail == null) {
            return;
        }
        if (tail.prev == null) {
            head = tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
    }

    // 刪除指定位置的節點
    public void remove(int index) {
        if (index < 0 || head == null) {
            return;
        }
        if (index == 0) {
            removeFirst();
            return;
        }
        Node current = head;
        for (int i = 0; i < index && current != null; i++) {
            current = current.next;
        }
        if (current == null) {
            return;
        }
        if (current.next != null) {
            current.next.prev = current.prev;
        } else {
            tail = current.prev;
        }
        if (current.prev != null) {
            current.prev.next = current.next;
        }
    }

    // 反向輸出鏈結串列
    public void printReverse() {
        Node current = tail;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }

    // 輸出鏈結串列
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

測試

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.addFirst(3);
        list.addFirst(2);
        list.addFirst(1);
        list.addLast(4);
        list.addLast(5);
        list.insert(2, 10);
        list.removeFirst();
        list.removeLast();
        list.remove(2);
        list.printList(); // 輸出: 2 3 4
        list.printReverse(); // 輸出: 4 3 2
    }
}

結論

雙向鏈結串列是單向鏈結串列的進階版本，適合需要雙向遍歷或頻繁插入/刪除的應用場景。雖然記憶體使用稍多，但帶來的靈活性在許多情況下是值得的。