Java实现双链表的示例代码

下面我将为您详细讲解Java实现双链表的示例代码的完整攻略。

什么是双链表

双链表是一种常见的数据结构，在链表中每个节点中都存储了前驱节点和后继节点的地址。与单链表相比，双链表能够更快速地进行双向遍历，但是需要更多的空间来存储节点的前驱和后继节点地址。

Java实现双链表的步骤

下面是实现双链表的步骤：

1. 定义节点类，该节点类应该包含前驱节点和后继节点的引用。

2. 定义双链表类，该类中应该包含头节点和尾节点的引用。

3. 定义添加节点的方法，该方法应该在双链表末尾添加节点。

4. 定义删除节点的方法，该方法应该根据节点的值在双链表中删除指定节点。

5. 定义遍历节点的方法，该方法应该可以实现正向和反向遍历。

下面我们将按照上述步骤逐步实现Java双链表的示例代码。

1. 定义节点类

public class DoublyLinkedListNode<T> {
    public T value;
    public DoublyLinkedListNode<T> prev;
    public DoublyLinkedListNode<T> next;

    public DoublyLinkedListNode(T value) {
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

节点类包含一个泛型的值，以及前驱节点和后继节点的引用。

1. 定义双链表类

public class DoublyLinkedList<T> {
    public DoublyLinkedListNode<T> head;
    public DoublyLinkedListNode<T> tail;

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

    public void add(T value) {
        DoublyLinkedListNode<T> node = new DoublyLinkedListNode<>(value);

        if (this.head == null) {
            this.head = node;
        } else {
            this.tail.next = node;
            node.prev = this.tail;
        }

        this.tail = node;
    }

    public void delete(T value) {
        DoublyLinkedListNode<T> current = this.head;

        while (current != null) {
            if (current.value.equals(value)) {
                if (current.prev != null) {
                    current.prev.next = current.next;
                } else {
                    this.head = current.next;
                }

                if (current.next != null) {
                    current.next.prev = current.prev;
                } else {
                    this.tail = current.prev;
                }
            }

            current = current.next;
        }
    }

    public void traverse(boolean reverse) {
        DoublyLinkedListNode<T> current = reverse ? this.tail : this.head;

        while (current != null) {
            System.out.println(current.value);
            current = reverse ? current.prev : current.next;
        }
    }
}

双链表类包含头节点和尾节点的引用。该类中定义了添加节点、删除节点和遍历节点的方法。其中，添加节点的方法将节点添加到链表末尾，删除节点的方法会根据节点的值删除指定的节点，而遍历节点的方法可以实现正向和反向遍历。

1. 测试示例1

DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
list.add(1);
list.add(2);
list.add(3);

list.traverse(false);  // 正向遍历，输出1、2、3

上述代码创建了一个双链表，并在其中分别添加了值为1、2、3的节点，然后正向遍历双链表并输出节点的值。

1. 测试示例2

DoublyLinkedList<String> list = new DoublyLinkedList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");

list.delete("b");

list.traverse(true);   // 反向遍历，输出d、c、a

上述代码创建了一个双链表，并在其中添加了值为"a"、"b"、"c"、"d"的节点，然后删除了节点值为"b"的节点，并反向遍历双链表并输出节点的值。

至此，我们已经完成了Java实现双链表的示例代码。