【Java数据结构】链表(Linked List)-双向链表

双向链表（Linked List）是一种常用的数据结构，它允许在所有节点中快速添加或删除元素，并且可以有效地实现反向遍历。本篇文章将介绍双向链表的基础知识，并提供使用Java语言实现该数据结构的示例代码。

一、双向链表的基础知识

一个双向链表由多个节点组成，每个节点包含两个指针，分别指向前驱节点和后继节点。首节点的前驱节点为null，尾节点的后继节点为null。

下面是一个示意图：

null <- A <-> B <-> C <-> D -> null

 上述图中，A为首节点，D为尾节点。每个节点都有一个值域（value），这个值域可以存储任意类型的数据。在双向链表中，我们通常只需要保存首节点的引用，即可轻松访问整个链表。

二、双向链表的操作

• 添加节点

为了在链表中添加新节点，我们需要指定插入节点的位置。假设我们要在节点B之后插入一个新节点E，则需要进行以下操作：

1. 创建一个新节点E，并将其值域设置为目标元素。
2. 将新节点E的前驱指针指向节点B，将新节点E的后继指针指向节点C。
3. 将节点B的后继指针指向新节点E，将节点C的前驱指针指向新节点E。

下面是上述操作的示意图：

null <- A <-> B <-> E <-> C <-> D -> null

• 删除节点

要从双向链表中删除节点，我们需要知道目标节点的位置。假设我们要删除节点C，则需要进行以下操作：

1. 将节点C的前驱节点（即节点B）的后继指针指向节点D。
2. 将节点D的前驱指针指向节点B。

下面是上述操作的示意图：

null <- A <-> B <-> E <-> D -> null

• 遍历节点

由于双向链表中每个节点都有一个指向后继节点和前驱节点的引用，因此可以非常容易地实现正向和反向遍历。

下面是一个遍历链表并打印所有元素值的示例代码：

public class DoublyLinkedList<T> {private Node<T> head;private Node<T> tail;private static class Node<T> {private T data;private Node<T> prev;private Node<T> next;public Node(T data) {this.data = data;this.prev = null;this.next = null;}}public void addFirst(T data) {Node<T> newNode = new Node<>(data);if (head == null) {head = newNode;tail = newNode;} else {head.prev = newNode;newNode.next = head;head = newNode;}}public void addLast(T data) {Node<T> newNode = new Node<>(data);if (tail == null) {head = newNode;tail = newNode;} else {tail.next = newNode;newNode.prev = tail;tail = newNode;}}public void removeFirst() {if (head == null) {throw new NoSuchElementException();} else if (head == tail) {head = null;tail = null;} else {head.next.prev = null;head = head.next;}}public void removeLast() {if (tail == null) {throw new NoSuchElementException();} else if (head == tail) {head = null;tail = null;} else {tail.prev.next = null;tail = tail.prev;}}/*为了实现反向遍历，我们只需要替换current.next为current.prev，同时从尾节点开始遍历即可。*/public void traverse() {Node<T> current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();}
}

上述实现定义了一个 DoublyLinkedList 类，其中包含一个嵌套的 Node 类，用于表示双向链表中的节点。通过 addFirst 和 addLast 方法可以在链表的头部和尾部添加元素，通过 removeFirst 和 removeLast 方法可以删除链表中的第一个和最后一个元素。traverse方法用于遍历链表并打印所有元素值