java模擬實現雙向鏈表的方法

Java模擬實現雙向鏈表的方法

雙向鏈表（Doubly Linked List）是一種常見的數據結構，它允許在鏈表中進行雙向遍歷。與單向鏈表不同，雙向鏈表的每個節點不僅包含指向下一個節點的指針，還包含指向前一個節點的指針。這使得在雙向鏈表中插入、刪除和遍歷操作更加靈活。

本文將介紹如何使用Java語言模擬實現一個簡單的雙向鏈表，并實現一些基本的操作，如插入、刪除和遍歷。

1. 雙向鏈表的節點定義

首先，我們需要定義一個表示雙向鏈表節點的類。每個節點包含三個部分：

• data：存儲節點的數據。
• prev：指向前一個節點的指針。
• next：指向下一個節點的指針。

class Node<T> {
    T data;
    Node<T> prev;
    Node<T> next;

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

2. 雙向鏈表的實現

接下來，我們實現一個雙向鏈表類 DoublyLinkedList，它包含以下基本操作：

• addFirst(T data)：在鏈表頭部插入一個新節點。
• addLast(T data)：在鏈表尾部插入一個新節點。
• removeFirst()：刪除鏈表頭部的節點。
• removeLast()：刪除鏈表尾部的節點。
• printList()：遍歷并打印鏈表中的所有節點。

public class DoublyLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;

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

    // 在鏈表頭部插入節點
    public void addFirst(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

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

    // 刪除鏈表頭部的節點
    public void removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("鏈表為空，無法刪除");
        }
        if (head == tail) {
            head = tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
    }

    // 刪除鏈表尾部的節點
    public void removeLast() {
        if (tail == null) {
            throw new NoSuchElementException("鏈表為空，無法刪除");
        }
        if (head == tail) {
            head = tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
    }

    // 遍歷并打印鏈表
    public void printList() {
        Node<T> current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

3. 測試雙向鏈表

為了驗證我們的雙向鏈表實現是否正確，我們可以編寫一個簡單的測試程序。

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();

        list.addFirst(1);
        list.addLast(2);
        list.addLast(3);
        list.addFirst(0);

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

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

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

4. 總結

通過以上代碼，我們實現了一個簡單的雙向鏈表，并實現了基本的插入、刪除和遍歷操作。雙向鏈表相比于單向鏈表，提供了更多的靈活性，尤其是在需要頻繁進行雙向遍歷的場景中。然而，雙向鏈表也帶來了額外的內存開銷，因為每個節點需要存儲兩個指針（prev 和 next）。

在實際應用中，雙向鏈表常用于實現雙向隊列（Deque）等數據結構。通過理解雙向鏈表的實現原理，我們可以更好地掌握鏈表這一基礎數據結構，并為后續學習更復雜的數據結構打下堅實的基礎。