Java双向链表-java教程-PHP中文网

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();
}
}

登录后复制

输出：

Java双向链表

所以这里我们创建一个 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();
}
}

登录后复制

输出：

Java双向链表