Dobbeltkoblet liste i Java

doubly linked list java implementation code examples

Prøv Vores Instrument Til At Fjerne Problemer

Vælg Operativsystemet Vælg Et Projektionsprojekt (Valgfrit)

Beskriv Dit Problem

Denne vejledning forklarer den dobbeltkoblede liste i Java sammen med implementering af dobbeltkædet liste, cirkulær dobbeltkædet liste Java-kode og eksempler:

Den sammenkædede liste er en sekventiel gengivelse af elementer. Hvert element på den sammenkædede liste kaldes en 'Node'. En type sammenkædet liste kaldes “Enkeltkædet liste”.

I dette indeholder hver node en datadel, der gemmer faktiske data, og en anden del, der gemmer markøren til den næste node på listen. Vi har allerede lært detaljerne i den enkeltlinkede liste i vores tidligere tutorial.

=> Tjek ALLE Java-tutorials her.

Dobbelt sammenkædet liste i Java

Hvad du lærer:

Dobbeltkoblet liste i Java
Cirkulær dobbeltkoblet liste i Java
- Ofte stillede spørgsmål
Konklusion
- Anbefalet læsning

En sammenkædet liste har en anden variant kaldet “dobbeltkoblet liste”. En dobbeltkoblet liste har en ekstra markør kendt som den foregående markør i dens knude bortset fra datadelen og den næste markør som i den enkeltkædede liste.

En knude på den dobbeltkoblede liste ser således ud:

c ++ dato og klokkeslæt

på den dobbeltkoblede liste

Her er 'Prev' og 'Next' henvisninger til henholdsvis de forrige og næste elementer i noden. 'Data' er det faktiske element, der er gemt i noden.

Følgende figur viser en dobbeltkoblet liste.

dobbeltkoblet liste

Ovenstående diagram viser den dobbeltkoblede liste. Der er fire noder på denne liste. Som du kan se, er den forrige markør i den første node og den næste markør i den sidste node sat til null. Den forrige markør indstillet til null angiver, at dette er den første node i den dobbeltkoblede liste, mens den næste markør, der er indstillet til null, angiver, at node er den sidste node.

Fordele

Da hver knude har markører, der peger på de forrige og næste knudepunkter, kan den dobbeltkoblede liste let krydses fremad såvel som bagud.
Du kan hurtigt tilføje den nye knude bare ved at ændre markørerne.
Til sletning er sletningen lettere, da vi har såvel tidligere som næste markører, og vi behøver ikke at krydse hele listen for at finde den forrige node som i tilfælde af den enkelt linkede liste.

Ulemper

Da der er en ekstra markør på den dobbeltkoblede liste, dvs. den forrige markør, kræves der yderligere hukommelsesplads for at gemme denne markør sammen med den næste markør og dataelementet.
Alle operationer som tilføjelse, sletning osv. Kræver, at både forrige og næste pegefinger manipuleres, hvilket pålægger operationelle omkostninger.

Implementering i Java

Implementeringen af dobbeltkoblet liste i Java består i at oprette en dobbeltkoblet listeklasse, nodeklassen og tilføje noder til den dobbeltkoblede liste

Tilføjelsen af nye noder sker normalt i slutningen af listen. Nedenstående diagram viser tilføjelsen af den nye knude i slutningen af den dobbeltkoblede liste.

Dobbelt sammenkædet listeimplementering i Java

Som vist i ovenstående diagram, for at tilføje en ny node i slutningen af listen, peger den næste markør på den sidste node nu på den nye node i stedet for null. Den forrige markør for den nye node peger på den sidste node. Også den næste markør i den nye node peger på null, hvilket gør den til en ny sidste node.

Programmet nedenfor viser Java-implementering af en dobbeltkoblet liste med tilføjelse af nye noder i slutningen af listen.

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

Produktion:

Noder på dobbeltkoblet liste:
10 20 30 40 50

Output - tilføjelse af nye noder

Udover at tilføje en ny node i slutningen af listen, kan du også tilføje en ny node i begyndelsen af listen eller imellem listen. Vi overlader denne implementering til læseren, så læserne kan forstå operationerne på en bedre måde.

Cirkulær dobbeltkoblet liste i Java

En cirkulær dobbeltkoblet liste er en af de komplekse strukturer. I denne liste indeholder den sidste node på den dobbeltkoblede liste adressen på den første node, og den første node indeholder adressen på den sidste node. Således er der i en cirkulær dobbeltkoblet liste en cyklus, og ingen af nodepegerne er indstillet til null.

Følgende diagram viser den cirkulære dobbeltkoblede liste.

cirkulær dobbeltkoblet liste

Som vist i ovenstående diagram peger den næste markør på den sidste node til den første node. Den forrige markør for den første node peger på den sidste node.

Cirkulære dobbeltkoblede lister har brede applikationer i softwareindustrien. En sådan applikation er den musikalske app, der har en playliste. Når du er færdig med at afspille alle sangene i afspilningslisten, går du automatisk tilbage til den første sang i slutningen af den sidste sang. Dette gøres ved hjælp af cirkulære lister.

Fordele ved en cirkulær dobbeltkoblet liste:

Den cirkulære dobbeltkoblede liste kan krydses fra hoved til hale eller hale til hoved.
At gå fra hoved til hale eller hale til hoved er effektivt og tager kun konstant tid O (1).
Det kan bruges til implementering af avancerede datastrukturer inklusive Fibonacci-bunke.

Ulemper:

dijkstras algoritme ved hjælp af prioritetskø java

Da hver node skal have plads til den forrige markør, kræves der ekstra hukommelse.
Vi er nødt til at beskæftige os med en række henvisninger, mens vi udfører operationer på en cirkulær dobbeltkoblet liste. Hvis markører ikke håndteres korrekt, kan implementeringen gå i stykker.

Nedenstående Java-program viser implementeringen af den dobbeltkoblede cirkulære 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(); } }

Produktion:

Cirkulær dobbeltkoblet liste: 40 50 60 70 80
Cirkulær dobbeltkoblet liste kørt bagud:
80 70 60 50 40

output - Cirkulær dobbeltkoblet liste

I ovenstående program har vi tilføjet noden i slutningen af listen. Da listen er cirkulær, når den nye knude tilføjes, peger den næste markør i den nye knude på den første knude, og den tidligere knap i den første knude peger på den nye knude.

På samme måde vil den forrige markør i den nye node pege på den aktuelle sidste node, som nu bliver den næstsidste node. Vi overlader implementeringen af at tilføje en ny node i begyndelsen af listen og imellem noderne til læserne.

Ofte stillede spørgsmål

Q # 1) Kan den dobbeltkoblede liste være cirkulær?

Svar: Ja. Det er en mere kompleks datastruktur. I en cirkulær dobbeltkoblet liste indeholder den forrige markør i den første node adressen til den sidste node, og den næste pointer i den sidste node indeholder adressen på den første node.

Spørgsmål nr. 2) Hvordan opretter du en dobbelt cirkulær sammenkædet liste?

Svar: Du kan oprette en klasse til en dobbelt cirkulær sammenkædet liste. Inde i denne klasse vil der være en statisk klasse, der repræsenterer noden. Hver node vil indeholde to markører - forrige og næste og et dataelement. Derefter kan du have operationer for at føje noder til listen og krydse listen.

Spørgsmål nr. 3) Er dobbeltkoblet liste lineær eller cirkulær?

Svar: Den dobbeltkoblede liste er en lineær struktur, men en cirkulær dobbeltkædet liste, der har halen peget på hovedet og hovedet peget på halen. Derfor er det en cirkulær liste.

Spørgsmål nr. 4) Hvad er forskellen mellem listen Dobbeltkædet og listen Kredsløbskoblet?

Svar: En dobbeltkoblet liste har noder, der holder oplysninger om dens tidligere såvel som de næste noder ved hjælp af henholdsvis de forrige og næste pegepinde. Også den forrige markør for den første node og den næste markør for den sidste node er indstillet til null på den dobbeltkoblede liste.

I den cirkulære sammenkædede liste er der ingen start- eller slutknudepunkter, og knudepunkterne danner en cyklus. Ingen af markørerne er også indstillet til null på den cirkulære sammenkædede liste.

Spørgsmål nr. 5) Hvad er fordelene ved en dobbeltkoblet liste?

Svar: Fordelene ved den dobbeltkoblede liste er:

Det kan krydses fremad såvel som bagud.
Indsættelse er lettere, da vi ikke behøver at krydse hele listen for at finde det forrige element.
Sletning er effektiv, da vi ved, at de forrige og næste noder og manipulering er lettere.

Konklusion

I denne vejledning diskuterede vi den dobbeltkoblede liste i Java detaljeret. En dobbeltkoblet liste er en kompleks struktur, hvor hvert knudepunkt indeholder markører til dets tidligere såvel som de næste knudepunkter. Styringen af disse links er undertiden vanskelig og kan føre til nedbrydning af kode, hvis den ikke håndteres korrekt.

Samlet set er operationerne på en dobbeltkoblet liste mere effektiv, da vi kan spare tid til at krydse listen, da vi har fået både den forrige og den næste pege.

Den cirkulære dobbeltkoblede liste er mere kompleks, og de danner et cirkulært mønster med den forrige markør af den første node, der peger på den sidste node og den næste markør af den sidste node, der peger mod den første node. I dette tilfælde er operationerne også effektive.

Med dette er vi færdige med den linkede liste i Java. Hold øje med mange flere tutorials om søgning og sorteringsteknikker i Java.

=> Besøg her for den eksklusive Java-træningsundervisningsserie.

Dobbeltkoblet liste i Java - Implementering og kodeeksempler