Java实现双向链表(两个版本)

下面是详细讲解Java实现双向链表的完整攻略。

双向链表定义

双向链表是链表的一种，每个节点都包含两个指针，一个指向前一个节点，一个指向后一个节点。相对于单向链表，双向链表可以实现双向遍历，但是占用空间较大。

双向链表的实现

版本一

双向链表的每个节点需要维护前向指针和后向指针，因此我们可以定义一个Node类来封装节点信息，再定义一个双向链表类来封装链表信息。

Node类定义如下：

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

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

双向链表类定义如下：

class DoubleLinkedList {
    Node head;
    Node tail;

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

    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    public void printFromHead() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public void printFromTail() {
        Node current = tail;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }
}

这里定义了头节点和尾节点两个指针，add方法用于向链表中添加新节点，printFromHead和printFromTail方法用于从头节点和尾节点打印链表。

示例一：

DoubleLinkedList list = new DoubleLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.printFromHead(); // 1 2 3
list.printFromTail(); // 3 2 1

版本二

在版本一的实现中，我们每次在尾节点添加新节点时需要遍历整个链表，因此时间复杂度较高。我们可以在链表类中添加一个变量count，用于记录链表节点的数量，然后在添加新节点时直接将其插入到尾节点之后，省去了遍历的过程。

双向链表类定义如下：

class DoubleLinkedList {
    Node head;
    Node tail;
    int count;

    public DoubleLinkedList() {
        this.head = null;
        this.tail = null;
        this.count = 0;
    }

    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        count++;
    }

    public void printFromHead() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public void printFromTail() {
        Node current = tail;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }
}

示例二：

DoubleLinkedList list = new DoubleLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.printFromHead(); // 1 2 3
list.printFromTail(); // 3 2 1

总结

双向链表是一种非常常用的数据结构，在实际开发中也经常用到。上述是两种Java实现双向链表的方法，考虑实际情况和需求选择适合自己的实现方法。