doubly linked list java implementation code examples
Denne opplæringen forklarer dobbeltkoblet liste i Java sammen med implementering av dobbeltkoblet liste, sirkulær dobbeltkoblet liste Java-kode og eksempler:
Den koblede listen er en sekvensiell fremstilling av elementer. Hvert element i den koblede listen kalles en ‘Node’. En type koblet liste kalles “Singly linked list”.
I dette inneholder hver node en datadel som lagrer faktiske data og en andre del som lagrer pekeren til neste node i listen. Vi har allerede lært detaljene i den enkeltkoblede listen i vår forrige opplæring.
=> Sjekk ALLE Java-opplæringsprogrammer her.
Hva du vil lære:
Dobbeltkoblet liste i Java
En koblet liste har en annen variant kalt “dobbeltkoblet liste”. En dobbeltkoblet liste har en ekstra peker kjent som den forrige pekeren i noden bortsett fra datadelen og den neste pekeren som i den enkeltkoblede listen.
En node i den dobbeltkoblede listen ser slik ut:
hvilken av følgende operasjoner ikke kunne brukes på pekere
Her er 'Prev' og 'Next' pekepinner til henholdsvis forrige og neste element i noden. ‘Data’ er det faktiske elementet som er lagret i noden.
Følgende figur viser en dobbelt koblet liste.
Ovenstående diagram viser den dobbeltkoblede listen. Det er fire noder i denne listen. Som du kan se, er den forrige pekeren til den første noden og den neste pekeren til den siste noden satt til null. Den forrige pekeren satt til null indikerer at dette er den første noden i den dobbeltkoblede listen, mens den neste pekeren satt til null indikerer at noden er den siste noden.
Fordeler
- Ettersom hver node har pekere som peker mot forrige og neste noder, kan den dobbeltkoblede listen lett krysses fremover og tilbakeover
- Du kan raskt legge til den nye noden bare ved å endre pekerne.
- På samme måte, for sletteoperasjoner siden vi har både tidligere og neste pekere, er slettingen enklere, og vi trenger ikke å krysse hele listen for å finne den forrige noden som i tilfelle den enkeltkoblede listen.
Ulemper
- Siden det er en ekstra peker i den dobbeltkoblede listen, dvs. den forrige pekeren, kreves det ekstra minne for å lagre denne pekeren sammen med neste peker og dataelement.
- Alle operasjoner som tillegg, sletting osv. Krever at både forrige og neste pekepinn manipuleres og dermed pålegger operasjonelle omkostninger.
Implementering i Java
Implementeringen av dobbeltkoblet liste i Java består i å opprette en dobbeltkoblet listeklasse, nodeklassen og legge til noder i den dobbeltkoblede listen
Tillegg av nye noder gjøres vanligvis på slutten av listen. Diagrammet nedenfor viser tillegget til den nye noden på slutten av den dobbeltkoblede listen.
Som vist i diagrammet ovenfor, for å legge til en ny node på slutten av listen, peker neste peker på den siste noden nå til den nye noden i stedet for null. Den forrige pekeren til den nye noden peker til den siste noden. Dessuten peker neste peker på den nye noden til null, og gjør den til en ny siste node.
Programmet nedenfor viser Java-implementering av en dobbeltkoblet liste med tillegg av nye noder på slutten av 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(); } } Produksjon:
Noder med dobbelt koblet liste:
10 20 30 40 50
Bortsett fra å legge til en ny node på slutten av listen, kan du også legge til en ny node i begynnelsen av listen eller i mellom listen. Vi overlater denne implementeringen til leseren slik at leserne kan forstå operasjonene på en bedre måte.
Sirkulær dobbeltkoblet liste i Java
En sirkulær dobbeltkoblet liste er en av de komplekse strukturene. I denne listen inneholder den siste noden til den dobbeltkoblede listen adressen til den første noden, og den første noden inneholder adressen til den siste noden. I en sirkulær dobbeltkoblet liste er det således en syklus, og ingen av nodepekerne er satt til null.
Følgende diagram viser den sirkulære dobbeltkoblede listen.
Som vist i diagrammet ovenfor, peker neste peker på den siste noden til den første noden. Den forrige pekeren til den første noden peker til den siste noden.
Sirkulære dobbeltkoblede lister har brede applikasjoner i programvareindustrien. En slik applikasjon er den musikalske appen som har en spilleliste. I spillelisten, når du er ferdig med å spille alle sangene, og på slutten av den siste sangen, går du automatisk tilbake til den første sangen. Dette gjøres ved hjelp av sirkulære lister.
Fordeler med en sirkulær dobbeltkoblet liste:
- Den sirkulære dobbeltkoblede listen kan krysses fra hode til hale eller hale til hode.
- Å gå fra hode til hale eller hale til hode er effektivt og tar bare konstant tid O (1).
- Den kan brukes til å implementere avanserte datastrukturer, inkludert Fibonacci-heap.
Ulemper:
- Siden hver node trenger å gi plass til den forrige pekeren, kreves ekstra minne.
- Vi må håndtere mange pekere mens vi utfører operasjoner på en sirkulær dobbeltkoblet liste. Hvis pekere ikke blir håndtert riktig, kan implementeringen gå i stykker.
Java-programmet nedenfor viser implementeringen av den sirkulære dobbeltkoblede listen.
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(); } } Produksjon:
Sirkulær dobbeltkoblet liste: 40 50 60 70 80
Sirkulær dobbeltkoblet liste traversert bakover:
80 70 60 50 40
I programmet ovenfor har vi lagt til noden på slutten av listen. Når listen er sirkulær, når den nye noden legges til, vil neste peker til den nye noden peke til den første noden, og den forrige pekeren til den første noden vil peke mot den nye noden.
Tilsvarende vil den forrige pekeren til den nye noden peke på den nåværende siste noden som nå blir den nest siste noden. Vi overlater implementeringen av å legge til en ny node i begynnelsen av listen og mellom nodene til leserne.
ofte stilte spørsmål
Q # 1) Kan den dobbeltkoblede listen være sirkulær?
Svar: Ja. Det er en mer kompleks datastruktur. I en sirkulær dobbeltkoblet liste inneholder den forrige pekeren til den første noden adressen til den siste noden, og den neste pekeren til den siste noden inneholder adressen til den første noden.
Spørsmål nr. 2) Hvordan oppretter du en dobbel sirkulær koblet liste?
Svar: Du kan opprette en klasse for en dobbelt sirkulær koblet liste. Inne i denne klassen vil det være en statisk klasse som representerer noden. Hver node vil inneholde to pekere - forrige og neste og et dataelement. Deretter kan du gjøre operasjoner for å legge til noder i listen og for å krysse listen.
Q # 3) Er dobbeltkoblet liste lineær eller sirkulær?
Svar: Den dobbeltkoblede listen er en lineær struktur, men en sirkulær dobbeltkoblet liste som har halen pekende mot hodet og hodet pekt mot halen. Derfor er det en sirkulær liste.
vanlige uttrykk i c ++
Q # 4) Hva er forskjellen mellom listen Dobbeltkoblet og den sirkulærkoblede listen?
Svar: En dobbeltkoblet liste har noder som holder informasjon om forrige så vel som neste noder ved bruk av forrige og neste pekere. Også den forrige pekeren til den første noden og den neste pekeren til den siste noden er satt til null i den dobbeltkoblede listen.
I den sirkulære koblede listen er det ingen start- eller sluttnoder, og nodene danner en syklus. Ingen av pekerne er også satt til null i den sirkulære koblede listen.
Q # 5) Hva er fordelene med en dobbeltkoblet liste?
Svar: Fordelene med den dobbeltkoblede listen er:
- Det kan krysses både fremover og bakover.
- Innsettingsoperasjonen er lettere da vi ikke trenger å krysse hele listen for å finne forrige element.
- Sletting er effektiv da vi vet at forrige og neste noder og manipulering er enklere.
Konklusjon
I denne opplæringen diskuterte vi den Dobbeltkoblede listen i Java i detalj. En dobbelt koblet liste er en kompleks struktur der hver node inneholder pekere til forrige så vel som neste noder. Administrasjonen av disse koblingene er noen ganger vanskelig og kan føre til sammenbrudd av koden hvis den ikke håndteres riktig.
Samlet sett er operasjonene til en dobbeltkoblet liste mer effektive, ettersom vi kan spare tid for å krysse listen ettersom vi har både forrige og neste pekepinn.
Den sirkulære dobbeltkoblede listen er mer kompleks, og de danner et sirkulært mønster med den forrige pekeren til den første noden som peker mot den siste noden og den neste pekeren til den siste noden som peker mot den første noden. I dette tilfellet er også operasjonene effektive.
Med dette er vi ferdige med den koblede listen i Java. Følg med for mange flere opplæringsprogrammer om søk og sorteringsteknikker i Java.
=> Besøk her for den eksklusive opplæringsserien for Java Training.
Anbefalt lesing
- Dobbeltkoblet listedatastruktur i C ++ med illustrasjon
- Binær søkealgoritme i Java - implementering og eksempler
- Java List - Hvordan lage, initialisere og bruke listen i Java
- Java-grensesnitt og abstrakt klasseopplæring med eksempler
- Java-listemetoder - Sorteringsliste, Inneholder, Legg til liste, Fjern liste
- Insertion Sort In Java - Insertion Sort Algorithm & Eksempler
- JAVA-opplæring for nybegynnere: 100+ praktiske Java-videoveiledninger
- Boblesortering i Java - Eksempler på Java-sorteringsalgoritmer og kode