Java數據結構之雙向鏈表如何實現

Java數據結構之雙向鏈表如何實現

雙向鏈表（Doubly Linked List）是一種常見的數據結構，它由一系列節點組成，每個節點包含數據域和兩個指針域，分別指向前一個節點和后一個節點。與單向鏈表相比，雙向鏈表可以雙向遍歷，因此在某些場景下具有更高的靈活性。

1. 雙向鏈表的基本結構

雙向鏈表的每個節點包含三個部分： - 數據域（data）：存儲節點的數據。 - 前驅指針（prev）：指向前一個節點。 - 后繼指針（next）：指向后一個節點。

雙向鏈表的頭節點的prev指針為null，尾節點的next指針為null。

2. 雙向鏈表的Java實現

下面是一個簡單的雙向鏈表的Java實現：

// 定義雙向鏈表的節點類
class Node<T> {
    T data;
    Node<T> prev;
    Node<T> next;

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

// 定義雙向鏈表類
class DoublyLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;

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

    // 在鏈表尾部添加節點
    public void add(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    // 刪除鏈表中的節點
    public void remove(T data) {
        Node<T> current = head;
        while (current != null) {
            if (current.data.equals(data)) {
                if (current.prev != null) {
                    current.prev.next = current.next;
                } else {
                    head = current.next;
                }
                if (current.next != null) {
                    current.next.prev = current.prev;
                } else {
                    tail = current.prev;
                }
                return;
            }
            current = current.next;
        }
    }

    // 打印鏈表中的所有節點
    public void printList() {
        Node<T> 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<Integer> list = new DoublyLinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.printList(); // 輸出: 1 2 3

        list.remove(2);
        list.printList(); // 輸出: 1 3
    }
}

3. 雙向鏈表的操作

3.1 添加節點

在雙向鏈表中添加節點時，通常有以下幾種情況： - 鏈表為空：直接將新節點設置為頭節點和尾節點。 - 鏈表不為空：將新節點添加到鏈表尾部，并更新尾節點的next指針和新節點的prev指針。

3.2 刪除節點

刪除節點時，需要考慮以下幾種情況： - 刪除頭節點：將頭節點的下一個節點設置為新的頭節點，并更新新頭節點的prev指針為null。 - 刪除尾節點：將尾節點的前一個節點設置為新的尾節點，并更新新尾節點的next指針為null。 - 刪除中間節點：更新被刪除節點的前驅節點的next指針和后繼節點的prev指針。

3.3 遍歷鏈表

雙向鏈表可以從頭節點開始遍歷，也可以從尾節點開始遍歷。遍歷時，可以通過next指針或prev指針依次訪問每個節點。

4. 雙向鏈表的優缺點

4.1 優點

• 雙向遍歷：可以從頭到尾或從尾到頭遍歷鏈表，靈活性更高。
• 刪除操作更高效：在已知節點的情況下，刪除操作的時間復雜度為O(1)。

4.2 缺點

• 占用更多內存：每個節點需要額外的指針來存儲前驅節點的引用。
• 實現復雜度較高：相比單向鏈表，雙向鏈表的實現和維護更為復雜。

5. 總結

雙向鏈表是一種功能強大的數據結構，適用于需要頻繁插入、刪除和雙向遍歷的場景。通過Java實現雙向鏈表，可以更好地理解其內部工作原理，并在實際開發中靈活運用。