Java双向链表

Java双向链表是链表的一种，其中每个节点除了存储数据之外还有两个链接。第一个链接指向前一个节点，另一个链接指向列表的下一个节点。双链表，也缩写为 DLL，很像单链表。两个链表都包含一个指向下一个节点的指针和一个表示要存储在该节点中的实际值的数据字段。主要区别在于 DLL 包含指向列表中前一个节点的指针，即 DLL 中的节点知道前一个节点和下一个节点。在本文中，我们将了解 Java 中的双向链表，探索一些示例，并了解其实现。

广告 该类别中的热门课程 JAVA 掌握 - 专业化 | 78 课程系列 | 15 次模拟测试

开始您的免费软件开发课程

网络开发、编程语言、软件测试及其他

语法

Java 中的双向链表没有特定的语法，但我们将看到如何在 Java 中声明双向链表。在研究双向链表的声明之前，让我们先看看双向链表实现背后的概念。

双链表中的节点：

Prev Node

Data

Next Node

上一个节点 数据 下一个节点 表>

这里上一个节点和下一个节点分别是指向节点上一个和下一个元素的指针。 ‘Data’是存储数据的实际元素。

以下是我们需要理解的一些重要术语，

• Prev：链表的每个链接都有一个指向前一个节点的链接，称为Prev。
• Next：链表的每个链接都有一个指向下一个节点的链接，称为Next
• 链接：链表的每个链接都可以存储数据，称为元素。
• 已链接 列表：包含第一个链接和最后一个链接的连接链接。

算法

• 定义一个 Node 类，表示链表中的一个节点。它应该有 3 个属性，即前一个节点、数据和下一个节点
• 定义另一个类来创建一个具有两个节点（即头和尾）的双向链表。最初，这些值将为空。
• 创建一个在链表中添加节点的函数，
• 它会首先检查head是否为null，然后插入节点作为head。
• 头和尾都会指向新节点。
• 如果tail不为null，则将新节点插入链表末尾，新节点的指针指向tail。
• 这样，新节点就会成为新的尾部。

Java 中双向链表的节点声明：

class Node {
public int data;
public Node prev;
public Node next;
public void displayData() {
//content of the function}
}

正如我们所看到的，在双向链表的情况下有一个额外的声明或引用（Node prev）。

双向链表的基本操作

以下是双向链表的基本操作，

• 插入： 在链表开头添加元素
• 删除：删除链表开头的元素
• 在之后插入： 在链表的一项之后添加元素
• 插入最后一个：将元素添加到链表的末尾
• 删除最后一个：删除链表末尾的元素
• 删除：使用键从链表中删除元素。
• 向前显示：向前显示完整列表
• 向后显示：向后显示完整列表

Java双向链表示例

下面是 Java 双向链表的不同示例：

示例#1：节点声明和添加节点以显示

代码：

public class DLL {
class Node{
public int data;
public Node prevNode;
public Node nextNode;
public Node(int data) {
this.data = data;
}
}
Node headNode, tailNode = null;
public void addDLLNode(int data) {
Node newDLLNode = new Node(data);
if(headNode == null) {
headNode = tailNode = newDLLNode;
headNode.prevNode = null;
tailNode.nextNode = null;
}
else {
tailNode.nextNode = newDLLNode;
newDLLNode.prevNode = tailNode;
tailNode = newDLLNode;
tailNode.nextNode = null;
}
}
public void displayNode() {
Node currentNode = headNode;
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
System.out.println("Nodes in Doubly Linked List: ");
while(currentNode != null) {
System.out.print(currentNode.data + " ");
currentNode = currentNode.nextNode;
}
}
public static void main(String[] args) {
DLL dLinkedList = new DLL();
dLinkedList.addDLLNode(9);
dLinkedList.addDLLNode(7);
dLinkedList.addDLLNode(5);
dLinkedList.addDLLNode(3);
dLinkedList.addDLLNode(1);
dLinkedList.addDLLNode(3);
dLinkedList.addDLLNode(5);
dLinkedList.addDLLNode(7);
dLinkedList.displayNode();
}
}

输出：

所以这里我们创建一个 Node 类来声明一个双向链表并显示 DLL 的值。

示例#2：删除链表开头并显示

代码：

public class DLL {
class Node{
public int data;
public Node prevNode;
public Node nextNode;
public Node(int data) {
this.data = data;
}
}
public void displayNode() {
Node tempNode = headNode;
while (tempNode != null) {
System.out.print(tempNode.data + "–>");
tempNode = tempNode.nextNode;
}
System.out.println("END");
}
Node headNode, tailNode = null;
public void addNode(int data) {
Node newNode = new Node(data);
if(headNode == null) {
headNode = tailNode = newNode;
headNode.prevNode = null;
tailNode.nextNode = null;
}
else {
tailNode.nextNode = newNode;
newNode.prevNode = tailNode;
tailNode = newNode;
tailNode.nextNode = null;
}
}
public void deleteInitialNode() {
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
else {
if(headNode != tailNode) {
headNode = headNode.nextNode;
}
else {
headNode = tailNode = null;
}
}
}
void printNode() {
Node currNode = headNode;
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
while(currNode != null)
{
System.out.print(currNode.data + " ");
currNode = currNode.nextNode;
}
System.out.println();
}
public static void main(String[] args) {
DLL doublyLL = new DLL();
doublyLL.addNode(3);
doublyLL.addNode(5);
doublyLL.addNode(7);
doublyLL.addNode(9);
doublyLL.addNode(11);
System.out.println("Doubly linked list: ");
doublyLL.printNode();
doublyLL.addNode(15);
doublyLL.addNode(17);
doublyLL.addNode(19);
doublyLL.deleteInitialNode();
doublyLL.addNode(21);
System.out.println("Doubly Linked List after deleting at the beginning: ");
doublyLL.printNode();
}
}

输出：

所以在这里，节点在链表的开头被删除，即节点 3 被删除/移除。

DLL可以向前和向后遍历。如果给出要删除的节点指针，DLL 中的删除操作会更加高效。 DLL 中的每个节点都需要额外的空间来存放前一个指针。所有操作都需要维护一个额外的指针。

至此，我们的主题“Java双向链表”就结束了。我们已经通过一些示例了解了 Java 双向链表是什么以及它是如何在 Java 编程中实现的。我们还看到了双向链表算法，并列出了一些适用于 DLL 的操作。我们已经在首次操作中实现了插入和删除，同样，还有其他操作可供您使用。

以上是Java双向链表的详细内容。更多信息请关注PHP中文网其他相关文章！