Java 双向链表入门

双向链表是一种数据结构，它包含对列表中前一个节点和后一个节点的引用。它为我们在列表中双向遍历、插入和删除节点提供了便利。

在双向链表中，每个节点包含三个数据成员：

• data: 节点中存储的数据
• next: 指向下一个节点的引用
• prev: 指向前一个节点的引用

在 Java 中创建双向链表：

要创建一个双向链表，首先我们需要定义一个 Node 类，它包含三个数据成员，分别用于存储节点中的数据、指向下一个节点的引用以及指向前一个节点的引用。

Java


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

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


现在我们需要创建一个双向链表类，其中包含两个变量 head 和 tail，它们分别引用列表的第一个和最后一个节点，同时还需要一个构造函数，将 head 和 tail 都初始化为 null。

Java


public class DoublyLinkedList {
Node head;
Node tail;

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


在 Java 中遍历双向链表：

> 要在双向链表中遍历，我们可以从头节点开始，沿着 next 引询直到到达列表的末尾；类似地，我们也可以从尾节点开始，沿着 prev 引询直到到达头节点。

下面是遍历链表的代码：

Java


// 从头节点遍历到列表末尾
public void traverseForward()
{
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
}
// 从尾节点反向遍历到头节点
public void traverseBackward()
{
Node current = tail;
while (current != null) {
System.out.print(current.data + " ");
current = current.prev;
}
}


在 Java 中的双向链表中插入节点：

> 要在双向链表中插入一个节点，首先我们需要创建一个将要插入的新节点，并更新相邻节点的引用以添加这个新节点。如果新节点是插入到列表的开头或结尾，我们还需要更新列表的 head 或 tail。

可以通过三种方式向双向链表添加节点：

• 在列表的开头插入
• 在列表中的特定位置插入
• 在列表的末尾插入

1) 在列表的开头插入：

创建一个待插入的新节点。将新节点的 next 指针指向双向链表当前的 head。将新节点的 prev 指针设置为 null，因为它将成为新的 head。如果双向链表不为空（即当前的 head 不为 null），则将当前的 head 的 prev 指针指向新节点。

!<a href="https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2014/03/DLLaddfront1.png"> 在列表的开头插入 在列表的开头插入

下面是在链表前面插入节点的代码：

Java


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

2) 在列表中的特定位置插入：

创建一个包含待插入数据的新节点。将新节点的 next 指针设置为给定位置节点的 next 节点。将新节点的 prev 指针设置为给定位置的节点。将给定位置节点的 next 指针指向新节点。如果新节点的 next 节点不为 null，则将其 prev 指针指向新节点。

!<a href="https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2014/03/DLLaddmiddle1.png">在列表中的特定位置插入在列表中的特定位置插入

下面是在链表的特定位置插入节点的代码：

Java


public void insertAtPosition(int data, int position)
{
Node temp = new Node(data);
if (position == 1) {
insertAtBeginning(data);
}
else {
Node current = head;
int currPosition = 1;
while (current != null && currPosition < position) {
current = current.next;
currPosition++;
}
if (current == null) {
insertAtEnd(data);
}
else {
temp.next = current;
temp.prev = current.prev;
current.prev.next = temp;
current.prev = temp;
}
}
}

3) 在列表的末尾插入：

首先，我们创建一个包含给定数据的新节点 temp