Java雙向鍊錶

Java雙向鍊錶是鍊錶的一種，其中每個節點除了儲存資料之外還有兩個連結。第一個連結指向前一個節點，另一個連結指向列表的下一個節點。雙鍊錶，也縮寫為 DLL，很像單鍊錶。兩個鍊錶都包含一個指向下一個節點的指標和一個表示要儲存在該節點中的實際值的資料欄位。主要差異在於 DLL 包含指向列表中前一個節點的指針，即 DLL 中的節點知道前一個節點和下一個節點。在本文中，我們將了解 Java 中的雙向鍊錶，探索一些範例，並了解其實作。

廣告 該類別中的熱門課程 JAVA 掌握 - 專業化 | 78 課程系列 | 15 次模擬測驗

開始您的免費軟體開發課程

網頁開發、程式語言、軟體測試及其他

文法

Java 中的雙向鍊錶沒有特定的語法，但我們將看到如何在 Java 中宣告雙向鍊錶。在研究雙向鍊錶的聲明之前，讓我們先來看看雙向鍊錶實作背後的概念。

雙鍊錶中的節點：

Prev Node

Data

Next Node

上一個節點 資料 下一個節點 表>

這裡上一個節點和下一個節點分別是指向節點上一個和下一個元素的指標。 ‘Data’是儲存資料的實際元素。

以下是我們需要理解的一些重要術語，

• Prev：鍊錶的每個連結都有一個指向前一個節點的鏈接，稱為Prev。
• Next：鍊錶的每個連結都有一個指向下一個節點的鏈接，稱為Next
• 連結：鍊錶的每個連結都可以儲存數據，稱為元素。
• 已連結 列表：包含第一個連結和最後一個連結的連結連結。

演算法

• 定義一個 Node 類，表示鍊錶中的一個節點。它應該有 3 個屬性，即前一個節點、資料和下一個節點
• 定義另一個類別來建立一個具有兩個節點（即頭和尾）的雙向鍊錶。最初，這些值將為空。
• 建立一個在鍊錶中加入節點的函數，
• 它會先檢查head是否為空，然後插入節點作為head。
• head 和 tail 都會指向新節點。
• 如果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中文網其他相關文章！