doubly linked list java implementation code examples
Dieses Tutorial erklärt die doppelt verknüpfte Liste in Java zusammen mit der Implementierung der doppelt verknüpften Liste, dem zirkulären doppelt verknüpften Java-Code und Beispielen:
Die verknüpfte Liste ist eine sequentielle Darstellung von Elementen. Jedes Element der verknüpften Liste wird als 'Knoten' bezeichnet. Eine Art von verknüpfter Liste wird als 'einfach verknüpfte Liste' bezeichnet.
Dabei enthält jeder Knoten einen Datenteil, in dem die tatsächlichen Daten gespeichert sind, und einen zweiten Teil, in dem der Zeiger auf den nächsten Knoten in der Liste gespeichert ist. Wir haben die Details der einfach verknüpften Liste bereits in unserem vorherigen Tutorial erfahren.
=> Überprüfen Sie ALLE Java-Tutorials hier.
Was du lernen wirst:
Doppelt verknüpfte Liste in Java
Eine verknüpfte Liste hat eine andere Variante, die als 'doppelt verknüpfte Liste' bezeichnet wird. Eine doppelt verknüpfte Liste hat einen zusätzlichen Zeiger, der als vorheriger Zeiger in ihrem Knoten bekannt ist, neben dem Datenteil und dem nächsten Zeiger wie in der einfach verknüpften Liste.
Ein Knoten in der doppelt verknüpften Liste sieht wie folgt aus:
Sie haben das Standard-Gateway in Ihrem Netzwerk ersetzt
Hier sind 'Zurück' und 'Weiter' Zeiger auf das vorherige bzw. das nächste Element des Knotens. Die 'Daten' sind das eigentliche Element, das im Knoten gespeichert ist.
Die folgende Abbildung zeigt eine doppelt verknüpfte Liste.
Das obige Diagramm zeigt die doppelt verknüpfte Liste. Diese Liste enthält vier Knoten. Wie Sie sehen können, wird der vorherige Zeiger des ersten Knotens und der nächste Zeiger des letzten Knotens auf null gesetzt. Der vorherige auf null gesetzte Zeiger zeigt an, dass dies der erste Knoten in der doppelt verknüpften Liste ist, während der nächste auf null gesetzte Zeiger anzeigt, dass der Knoten der letzte Knoten ist.
Vorteile
- Da jeder Knoten Zeiger hat, die auf den vorherigen und den nächsten Knoten zeigen, kann die doppelt verknüpfte Liste sowohl in Vorwärts- als auch in Rückwärtsrichtung leicht durchlaufen werden
- Sie können den neuen Knoten schnell hinzufügen, indem Sie die Zeiger ändern.
- In ähnlicher Weise ist das Löschen für Löschvorgänge einfacher, da wir sowohl vorherige als auch nächste Zeiger haben, und wir müssen nicht die gesamte Liste durchlaufen, um den vorherigen Knoten zu finden, wie im Fall der einfach verknüpften Liste.
Nachteile
- Da die doppelt verknüpfte Liste einen zusätzlichen Zeiger enthält, d. H. Den vorherigen Zeiger, ist zusätzlicher Speicherplatz erforderlich, um diesen Zeiger zusammen mit dem nächsten Zeiger und Datenelement zu speichern.
- Alle Operationen wie Hinzufügen, Löschen usw. erfordern, dass sowohl der vorherige als auch der nächste Zeiger manipuliert werden, wodurch ein Betriebsaufwand entsteht.
Implementierung in Java
Die Implementierung einer doppelt verknüpften Liste in Java umfasst das Erstellen einer doppelt verknüpften Listenklasse, der Knotenklasse, und das Hinzufügen von Knoten zur doppelt verknüpften Liste
Das Hinzufügen neuer Knoten erfolgt normalerweise am Ende der Liste. Das folgende Diagramm zeigt das Hinzufügen des neuen Knotens am Ende der doppelt verknüpften Liste.
Wie im obigen Diagramm gezeigt, zeigt der nächste Zeiger des letzten Knotens jetzt auf den neuen Knoten anstatt auf Null, um einen neuen Knoten am Ende der Liste hinzuzufügen. Der vorherige Zeiger des neuen Knotens zeigt auf den letzten Knoten. Außerdem zeigt der nächste Zeiger des neuen Knotens auf Null, wodurch er zu einem neuen letzten Knoten wird.
Das folgende Programm zeigt die Java-Implementierung einer doppelt verknüpften Liste mit dem Hinzufügen neuer Knoten am Ende der Liste.
class DoublyLinkedList { //A node class for doubly linked list class Node{ int item; Node previous; Node next; public Node(int item) { this.item = item; } } //Initially, heade and tail is set to null Node head, tail = null; //add a node to the list public void addNode(int item) { //Create a new node Node newNode = new Node(item); //if list is empty, head and tail points to newNode if(head == null) { head = tail = newNode; //head's previous will be null head.previous = null; //tail's next will be null tail.next = null; } else { //add newNode to the end of list. tail->next set to newNode tail.next = newNode; //newNode->previous set to tail newNode.previous = tail; //newNode becomes new tail tail = newNode; //tail's next point to null tail.next = null; } } //print all the nodes of doubly linked list public void printNodes() { //Node current will point to head Node current = head; if(head == null) { System.out.println('Doubly linked list is empty'); return; } System.out.println('Nodes of doubly linked list: '); while(current != null) { //Print each node and then go to next. System.out.print(current.item + ' '); current = current.next; } } } class Main{ public static void main(String() args) { //create a DoublyLinkedList object DoublyLinkedList dl_List = new DoublyLinkedList(); //Add nodes to the list dl_List.addNode(10); dl_List.addNode(20); dl_List.addNode(30); dl_List.addNode(40); dl_List.addNode(50); //print the nodes of DoublyLinkedList dl_List.printNodes(); } } Ausgabe:
Knoten der doppelt verknüpften Liste:
10 20 30 40 50
Neben dem Hinzufügen eines neuen Knotens am Ende der Liste können Sie auch einen neuen Knoten am Anfang der Liste oder zwischen den Listen hinzufügen. Wir überlassen diese Implementierung dem Leser, damit die Leser die Vorgänge besser verstehen können.
Zirkuläre doppelt verknüpfte Liste in Java
Eine zirkuläre doppelt verknüpfte Liste ist eine der komplexen Strukturen. In dieser Liste enthält der letzte Knoten der doppelt verknüpften Liste die Adresse des ersten Knotens und der erste Knoten die Adresse des letzten Knotens. Somit gibt es in einer kreisförmigen doppelt verknüpften Liste einen Zyklus und keiner der Knotenzeiger wird auf Null gesetzt.
Das folgende Diagramm zeigt die zirkuläre doppelt verknüpfte Liste.
Wie im obigen Diagramm gezeigt, zeigt der nächste Zeiger des letzten Knotens auf den ersten Knoten. Der vorherige Zeiger des ersten Knotens zeigt auf den letzten Knoten.
Zirkuläre doppelt verknüpfte Listen finden breite Anwendung in der Softwareindustrie. Eine solche Anwendung ist die Musik-App, die eine Wiedergabeliste hat. Wenn Sie in der Wiedergabeliste alle Titel abgespielt haben, kehren Sie am Ende des letzten Titels automatisch zum ersten Titel zurück. Dies erfolgt anhand von Rundschreiben.
Vorteile einer zirkulären doppelt verknüpften Liste:
- Die kreisförmige doppelt verknüpfte Liste kann von Kopf zu Schwanz oder von Schwanz zu Kopf durchlaufen werden.
- Das Gehen von Kopf zu Schwanz oder von Schwanz zu Kopf ist effizient und benötigt nur konstante Zeit O (1).
- Es kann zur Implementierung erweiterter Datenstrukturen einschließlich des Fibonacci-Heaps verwendet werden.
Nachteile:
- Da jeder Knoten Platz für den vorherigen Zeiger schaffen muss, ist zusätzlicher Speicher erforderlich.
- Wir müssen uns mit vielen Zeigern befassen, während wir Operationen an einer kreisförmigen doppelt verknüpften Liste ausführen. Wenn Zeiger nicht richtig behandelt werden, kann die Implementierung unterbrochen werden.
Das folgende Java-Programm zeigt die Implementierung der doppelt verknüpften Rundschreiben-Liste.
import java.util.*; class Main{ static Node head; // Doubly linked list node definition static class Node{ int data; Node next; Node prev; }; // Function to insert node in the list static void addNode(int value) { // List is empty so create a single node furst if (head == null) { Node new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; head = new_node; return; } // find last node in the list if list is not empty Node last = (head).prev; //previous of head is the last node // create a new node Node new_node = new Node(); new_node.data = value; // next of new_node will point to head since list is circular new_node.next = head; // similarly previous of head will be new_node (head).prev = new_node; // change new_node=>prev to last new_node.prev = last; // Make new node next of old last last.next = new_node; } static void printNodes() { Node temp = head; //traverse in forward direction starting from head to print the list while (temp.next != head) { System.out.printf('%d ', temp.data); temp = temp.next; } System.out.printf('%d ', temp.data); //traverse in backward direction starting from last node System.out.printf('
Circular doubly linked list travesed backward:
'); Node last = head.prev; temp = last; while (temp.prev != last) { System.out.printf('%d ', temp.data); temp = temp.prev; } System.out.printf('%d ', temp.data); } public static void main(String() args) { //the empty list Node l_list = null; // add nodes to the list addNode(40); addNode(50); addNode(60); addNode(70); addNode(80); //print the list System.out.printf('Circular doubly linked list: '); printNodes(); } } Ausgabe:
Rundschreiben doppelt verknüpfte Liste: 40 50 60 70 80
Rundschreiben doppelt verknüpfte Liste rückwärts durchlaufen:
80 70 60 50 40
Im obigen Programm haben wir den Knoten am Ende der Liste hinzugefügt. Da die Liste kreisförmig ist, zeigt der nächste Zeiger des neuen Knotens beim Hinzufügen des neuen Knotens auf den ersten Knoten und der vorherige Zeiger des ersten Knotens auf den neuen Knoten.
In ähnlicher Weise zeigt der vorherige Zeiger des neuen Knotens auf den aktuell letzten Knoten, der nun zum vorletzten Knoten wird. Wir überlassen die Implementierung des Hinzufügens eines neuen Knotens am Anfang der Liste und zwischen den Knoten den Lesern.
Häufig gestellte Fragen
F # 1) Kann die doppelt verknüpfte Liste kreisförmig sein?
bester youtube video downloader für pc
Antworten: Ja. Es ist eine komplexere Datenstruktur. In einer kreisförmigen doppelt verknüpften Liste enthält der vorherige Zeiger des ersten Knotens die Adresse des letzten Knotens und der nächste Zeiger des letzten Knotens die Adresse des ersten Knotens.
F # 2) Wie erstellen Sie eine doppelt kreisförmige verknüpfte Liste?
Antworten: Sie können eine Klasse für eine doppelt kreisförmige verknüpfte Liste erstellen. Innerhalb dieser Klasse gibt es eine statische Klasse, die den Knoten darstellt. Jeder Knoten enthält zwei Zeiger - den vorherigen und den nächsten sowie ein Datenelement. Anschließend können Sie Operationen ausführen, um Knoten zur Liste hinzuzufügen und die Liste zu durchlaufen.
F # 3) Ist die doppelt verknüpfte Liste linear oder kreisförmig?
Antworten: Die doppelt verknüpfte Liste ist eine lineare Struktur, aber eine kreisförmige doppelt verknüpfte Liste, deren Schwanz auf Kopf und Kopf auf Schwanz zeigt. Daher handelt es sich um eine zirkuläre Liste.
F # 4) Was ist der Unterschied zwischen der doppelt verknüpften Liste und der zirkular verknüpften Liste?
Antworten: Eine doppelt verknüpfte Liste enthält Knoten, die Informationen zu ihren vorherigen und nächsten Knoten unter Verwendung des vorherigen bzw. nächsten Zeigers speichern. Außerdem wird der vorherige Zeiger des ersten Knotens und der nächste Zeiger des letzten Knotens in der doppelt verknüpften Liste auf Null gesetzt.
In der zirkular verknüpften Liste gibt es keine Start- oder Endknoten und die Knoten bilden einen Zyklus. Außerdem wird keiner der Zeiger in der zirkular verknüpften Liste auf Null gesetzt.
F # 5) Was sind die Vorteile einer doppelt verknüpften Liste?
Antworten: Die Vorteile der doppelt verknüpften Liste sind:
- Es kann sowohl vorwärts als auch rückwärts gefahren werden.
- Das Einfügen ist einfacher, da wir nicht die gesamte Liste durchlaufen müssen, um das vorherige Element zu finden.
- Das Löschen ist effizient, da wir wissen, dass der vorherige und der nächste Knoten und das Bearbeiten einfacher sind.
Fazit
In diesem Tutorial haben wir die doppelt verknüpfte Liste in Java ausführlich besprochen. Eine doppelt verknüpfte Liste ist eine komplexe Struktur, bei der jeder Knoten Zeiger auf seinen vorherigen sowie den nächsten Knoten enthält. Die Verwaltung dieser Links ist manchmal schwierig und kann bei nicht ordnungsgemäßer Handhabung zum Zusammenbruch des Codes führen.
Insgesamt sind die Operationen einer doppelt verknüpften Liste effizienter, da wir Zeit für das Durchlaufen der Liste sparen können, da wir sowohl den vorherigen als auch den nächsten Zeiger haben.
Die kreisförmige doppelt verknüpfte Liste ist komplexer und sie bilden ein kreisförmiges Muster, wobei der vorherige Zeiger des ersten Knotens auf den letzten Knoten und der nächste Zeiger des letzten Knotens auf den ersten Knoten zeigt. Auch in diesem Fall sind die Operationen effizient.
Damit sind wir mit der verknüpften Liste in Java fertig. Weitere Tutorials zu Such- und Sortiertechniken in Java finden Sie hier.
=> Besuchen Sie hier für die exklusive Java Training Tutorial-Reihe.
Literatur-Empfehlungen
- Doppelt verknüpfte Listendatenstruktur in C ++ mit Abbildung
- Binärer Suchalgorithmus in Java - Implementierung und Beispiele
- Java-Liste - Erstellen, Initialisieren und Verwenden einer Liste in Java
- Java Interface und Abstract Class Tutorial mit Beispielen
- Java-Listenmethoden - Liste sortieren, Enthält, Liste hinzufügen, Liste entfernen
- Einfügungssortierung in Java - Einfügungssortierungsalgorithmus und Beispiele
- JAVA-Tutorial für Anfänger: Über 100 praktische Java-Video-Tutorials
- Blasensortierung in Java - Java-Sortieralgorithmen und Codebeispiele