Doppelt verknüpfte Java-Liste

Java Double Linked List ist eine Art verknüpfte Liste, bei der jeder Knoten außer der Speicherung von Daten zwei Links hat. Der erste Link zeigt auf den vorherigen Knoten und der andere Link zeigt auf den nächsten Knoten der Liste. Eine doppelt verknüpfte Liste, auch als DLL abgekürzt, ähnelt stark einer einfach verknüpften Liste. Beide verknüpften Listen enthalten einen Zeiger auf den nächsten Knoten und ein Datenfeld zur Darstellung des tatsächlichen Werts, der im Knoten gespeichert werden soll. Der Hauptunterschied besteht darin, dass DLL einen Zeiger auf den vorherigen Knoten in der Liste enthält, d. h. Knoten in DLL kennen sowohl den vorherigen als auch den nächsten Knoten. In diesem Artikel werfen wir einen Blick auf die doppelt verknüpfte Liste in Java, untersuchen einige Beispiele und lernen ihre Implementierung kennen.

WERBUNG Beliebter Kurs in dieser Kategorie JAVA MASTERY - Spezialisierung | 78 Kursreihe | 15 Probetests

Starten Sie Ihren kostenlosen Softwareentwicklungskurs

Webentwicklung, Programmiersprachen, Softwaretests und andere

Syntax

Es gibt keine bestimmte Syntax für die doppelt verknüpfte Liste in Java, aber wir werden sehen, wie man die doppelt verknüpfte Liste in Java deklariert. Bevor wir uns mit der Deklaration einer doppelt verknüpften Liste befassen, wollen wir uns das Konzept hinter der Implementierung einer doppelt verknüpften Liste ansehen.

Knoten in doppelt verknüpfter Liste:

Prev Node

Data

Next Node

Vorheriger Knoten Daten Nächster Knoten

Hier sind „Vorheriger Knoten“ und „Nächster Knoten“ Zeiger auf das vorherige bzw. nächste Element des Knotens. „Daten“ ist das eigentliche Element, in dem Daten gespeichert werden.

Im Folgenden finden Sie einige wichtige Begriffe, die wir verstehen müssen,

• Prev: Jeder Link der verknüpften Liste hat einen Link zum vorherigen Knoten namens Prev.
• Weiter: Jeder Link der verknüpften Liste verfügt über einen Link zum nächsten Knoten namens „Weiter“
• Link: Jeder Link einer verknüpften Liste kann Daten speichern, die als Elemente bezeichnet werden.
• Verknüpfte Liste: Sie enthält den Verbindungslink zum ersten Link und zum letzten Link.

Algorithmus

• Definieren Sie eine Node-Klasse, die einen Knoten in der verknüpften Liste darstellt. Es sollte 3 Eigenschaften haben, d. h. vorheriger Knoten, Daten und nächster Knoten
• Definieren Sie eine weitere Klasse, um eine doppelt verknüpfte Liste mit zwei Knoten, d. h. Kopf und Ende, zu erstellen. Anfangs sind diese Werte null.
• Erstellen Sie eine Funktion zum Hinzufügen von Knoten in der verknüpften Liste,
• Zuerst wird geprüft, ob der Kopf null ist, und dann wird der Knoten als Kopf eingefügt.
• Kopf und Schwanz zeigen dann auf den neuen Knoten.
• Wenn das Ende nicht null ist, wird der neue Knoten am Ende der Liste so eingefügt, dass der Zeiger des neuen Knotens auf das Ende zeigt.
• Somit wird der neue Knoten zu einem neuen Schwanz.

Knotendeklaration für doppelt verknüpfte Liste in Java:

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

Wie wir sehen können, gibt es im Fall einer doppelt verknüpften Liste eine zusätzliche Deklaration oder einen Verweis (Node prev).

Grundfunktionen einer doppelt verknüpften Liste

Im Folgenden sind die grundlegenden Operationen aufgeführt, die für doppelt verknüpfte Listen verfügbar sind.

• Einfügung:Hinzufügen eines Elements am Anfang der verknüpften Liste
• Löschen:Löschen eines Elements am Anfang der verknüpften Liste
• Einfügen nach:Hinzufügen eines Elements nach einem Element der verknüpften Liste
• Letztes einfügen:Ein Element am Ende der verknüpften Liste hinzufügen
• Letztes löschen:Löschen eines Elements am Ende der verknüpften Liste
• Löschen:Löschen eines Elements aus der verknüpften Liste mit einer Taste.
• Vorwärts anzeigen:Komplette Liste vorwärts anzeigen
• Rückwärts anzeigen: Komplette Liste rückwärts anzeigen

Beispiele für doppelt verknüpfte Java-Listen

Im Folgenden finden Sie verschiedene Beispiele für doppelt verknüpfte Java-Listen:

Beispiel Nr. 1: Deklaration eines Knotens und Hinzufügen von Knoten zur Anzeige

Code:

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

Ausgabe:

Hier erstellen wir also eine Node-Klasse, um eine doppelt verknüpfte Liste zu deklarieren und die Werte der DLL anzuzeigen.

Beispiel #2: Am Anfang der verknüpften Liste löschen und anzeigen

Code:

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

Ausgabe:

Hier wird also der Knoten am Anfang der verknüpften Liste gelöscht, d. h. Knoten 3 wird gelöscht/entfernt.

DLL kann in Vorwärts- und Rückwärtsrichtung durchlaufen werden. Der Löschvorgang in der DLL kann effizienter sein, wenn der zu löschende Knotenzeiger angegeben wird. Jeder Knoten in der DLL benötigt zusätzlichen Platz für den vorherigen Zeiger. Für alle Vorgänge muss ein zusätzlicher Zeiger verwaltet werden.

Damit schließen wir unser Thema „Java Double Linked List“ ab. Wir haben anhand einiger Beispiele gesehen, was eine doppelt verknüpfte Java-Liste ist und wie sie in der Java-Programmierung implementiert wird. Wir haben auch den Algorithmus für doppelt verknüpfte Listen gesehen und einige auf DLL anwendbare Vorgänge aufgelistet. Wir haben die Vorgänge „Einfügen“ und „Auf Anhieb löschen“ implementiert. Darüber hinaus stehen Ihnen auch andere Vorgänge zur Verfügung, an denen Sie arbeiten können.

Das obige ist der detaillierte Inhalt vonDoppelt verknüpfte Java-Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!