Dvojno povezan seznam v Javi

doubly linked list java implementation code examples

Preizkusite Naš Instrument Za Odpravo Težav

Izberite Operacijski Sistem Izberite Program Projekcije (Neobvezno)

Opišite Svoj Problem

Ta vadnica pojasnjuje dvojno povezan seznam v Javi, skupaj z izvajanjem dvojno povezanega seznama, krog Java kode in primeri:

Povezani seznam je zaporedna predstavitev elementov. Vsak element povezanega seznama se imenuje 'vozlišče'. Ena vrsta povezanega seznama se imenuje 'Singlely linked list'.

Pri tem vsako vozlišče vsebuje podatkovni del, ki hrani dejanske podatke, in drugi del, ki shrani kazalec na naslednje vozlišče na seznamu. Podrobnosti posamezno povezanega seznama smo že izvedeli v prejšnji vadnici.

=> Tukaj preverite VSE Vadnice za Java.

Dvojno povezan seznam v Javi

Kaj se boste naučili:

Dvojno povezan seznam v Javi
Krožni dvojno povezan seznam v Javi
- Pogosto zastavljena vprašanja
Zaključek
- Priporočeno branje

Povezani seznam ima še eno različico, imenovano 'dvojno povezan seznam'. Dvopovezan seznam ima v vozlišču poleg podatkovnega dela in naslednjega kazalca, kot na posamezno povezanem seznamu, dodaten kazalec, znan kot prejšnji kazalec.

Vozlišče na dvojno povezanem seznamu je videti tako:

prednostna vrsta izvedbe c ++

vozlišče na dvojno povezanem seznamu

Tu sta “Prev” in “Next” kazalca na prejšnji oziroma naslednji element vozlišča. 'Podatki' so dejanski elementi, ki so shranjeni v vozlišču.

Naslednja slika prikazuje dvojno povezan seznam.

dvojno povezan seznam

Zgornji diagram prikazuje dvojno povezan seznam. Na tem seznamu so štiri vozlišča. Kot lahko vidite, je prejšnji kazalec prvega vozlišča in naslednji kazalec zadnjega vozlišča nastavljen na nič. Prejšnji kazalec, nastavljen na nič, pomeni, da je to prvo vozlišče na dvojno povezanem seznamu, medtem ko naslednji kazalec, nastavljen na nič, pomeni, da je vozlišče zadnje vozlišče.

Prednosti

Ker ima vsako vozlišče kazalce, ki kažejo na prejšnje in naslednje vozlišče, lahko dvostransko povezan seznam enostavno prehodite tako naprej kot nazaj.
Novo vozlišče lahko hitro dodate samo s spreminjanjem kazalcev.
Podobno je pri operaciji brisanja, saj imamo predhodne in naslednje kazalce, brisanje lažje in ni nam treba prečkati celotnega seznama, da bi našli prejšnje vozlišče, kot v primeru posamezno povezanega seznama.

Slabosti

Ker je na dvojno povezanem seznamu dodaten kazalec, tj. Prejšnji kazalec, je potreben dodaten pomnilniški prostor za shranjevanje tega kazalca skupaj z naslednjim kazalcem in podatkovno postavko.
Vse operacije, kot so dodajanje, brisanje itd., Zahtevajo manipulacijo s prejšnjimi in naslednjimi kazalci, kar nalaga operativne režijske stroške.

Izvajanje v Javi

Izvedba dvojno povezanega seznama v Javi zajema ustvarjanje dvojno povezanega razreda seznama, razreda vozlišč in dodajanje vozlišč na dvojno povezan seznam

Dodajanje novih vozlišč je običajno na koncu seznama. Spodnji diagram prikazuje dodajanje novega vozlišča na koncu dvojno povezanega seznama.

Izvedba dvojno povezanega seznama v Javi

Kot je prikazano na zgornjem diagramu, za dodajanje novega vozlišča na koncu seznama naslednji kazalec zadnjega vozlišča zdaj kaže na novo vozlišče namesto na nulo. Prejšnji kazalec novega vozlišča kaže na zadnje vozlišče. Naslednji kazalec novega vozlišča kaže tudi na nulo in tako postane novo zadnje vozlišče.

Spodnji program prikazuje izvajanje Java dvojno povezanega seznama z dodajanjem novih vozlišč na koncu seznama.

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

Izhod:

Vozlišča dvojno povezanega seznama:
10 20 30 40 50

Izhod - dodajanje novih vozlišč

Poleg dodajanja novega vozlišča na koncu seznama lahko novo vozlišče dodate tudi na začetku seznama ali med njim. To izvedbo prepuščamo bralcu, da lahko bralci bolje razumejo delovanje.

Krožni dvojno povezan seznam v Javi

Krožno dvojno povezan seznam je ena zapletenih struktur. Na tem seznamu zadnje vozlišče dvojno povezanega seznama vsebuje naslov prvega vozlišča, prvo vozlišče pa naslov zadnjega vozlišča. Tako na krožnem dvojno povezanem seznamu obstaja cikel in noben kazalec vozlišča ni nastavljen na nič.

Naslednji diagram prikazuje krožno dvojno povezan seznam.

krožno dvojno povezan seznam

Kot je prikazano na zgornjem diagramu, naslednji kazalec zadnjega vozlišča kaže na prvo vozlišče. Prejšnji kazalec prvega vozlišča kaže na zadnje vozlišče.

Krožni dvojno povezani seznami imajo široko uporabo v industriji programske opreme. Ena takih aplikacij je glasbena aplikacija s seznamom predvajanja. Na seznamu predvajanja, ko končate s predvajanjem vseh skladb, se na koncu zadnje pesmi samodejno vrnete na prvo skladbo. To se naredi s pomočjo krožnih seznamov.

Prednosti krožnega dvojno povezanega seznama:

Krožno dvojno povezan seznam lahko prehodite od glave do repa ali repa do glave.
Prehod od glave do repa ali repa do glave je učinkovit in traja le konstanten čas O (1).
Uporablja se lahko za izvajanje naprednih podatkovnih struktur, vključno s Fibonaccijevim kupom.

Slabosti:

Ker mora vsako vozlišče narediti prostor za prejšnji kazalec, je potreben dodaten pomnilnik.
Pri izvajanju operacij na krožnem dvojno povezanem seznamu moramo obravnavati veliko kazalcev. Če s kazalci ne ravnamo pravilno, se lahko izvedba pokvari.

Spodnji program Java prikazuje izvajanje dvojno povezanega seznama Circular.

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

Izhod:

Krožno dvojno povezan seznam: 40 50 60 70 80
Krožni dvojno povezan seznam je potoval nazaj:
80 70 60 50 40

izhod - krožni dvojno povezan seznam

V zgornjem programu smo na koncu seznama dodali vozlišče. Ker je seznam krožen, bo ob dodajanju novega vozlišča naslednji kazalnik novega vozlišča kazal na prvo vozlišče, prejšnji kazalec prvega vozlišča pa na novo vozlišče.

Podobno bo prejšnji kazalec novega vozlišča kazal na trenutno zadnje vozlišče, ki bo zdaj postalo drugo zadnje vozlišče. Izvajanje dodajanja novega vozlišča prepustimo bralcem na začetku seznama in med vozlišči.

Pogosto zastavljena vprašanja

V # 1) Ali je lahko dvojno povezan seznam krožen?

Odgovor: Da. Gre za bolj zapleteno strukturo podatkov. Na krožnem dvojno povezanem seznamu prejšnji kazalec prvega vozlišča vsebuje naslov zadnjega vozlišča, naslednji kazalnik zadnjega vozlišča pa naslov prvega vozlišča.

V # 2) Kako ustvarite dvojno krožno povezan seznam?

Odgovor: Ustvarite lahko razred za dvojno krožno povezan seznam. V tem razredu bo statični razred, ki predstavlja vozlišče. Vsako vozlišče bo vsebovalo dva kazalca - prejšnji in naslednji ter podatkovni element. Nato lahko izvedete operacije dodajanja vozlišč na seznam in prehod po seznamu.

V # 3) Ali je dvojno povezan seznam linearni ali krožni?

Odgovor: Dvojno povezan seznam je linearna struktura, vendar krožni dvojno povezan seznam, katerega rep je usmerjen proti glavi, glava pa proti repu. Zato je to krožni seznam.

V # 4) Kakšna je razlika med dvojno povezanim seznamom in krožno povezanim seznamom?

Vprašanja in odgovori na razgovore za razvijalce sql pdf

Odgovor: Dvojno povezan seznam ima vozlišča, ki hranijo informacije o svojih prejšnjih in naslednjih vozliščih z uporabo prejšnjih in naslednjih kazalcev. Prav tako je prejšnji kazalec prvega vozlišča in naslednji kazalec zadnjega vozlišča nastavljen na nič na dvojno povezanem seznamu.

Na krožno povezanem seznamu ni začetnega ali končnega vozlišča in vozlišča tvorijo cikel. Prav tako noben od kazalcev ni nastavljen na nič na krožno povezanem seznamu.

V # 5) Kakšne so prednosti dvojno povezanega seznama?

Odgovor: Prednosti dvojno povezanega seznama so:

Lahko se premika tako v smeri naprej kot nazaj.
Postopek vstavljanja je enostavnejši, saj nam ni treba prečkati celotnega seznama, da bi našli prejšnji element.
Izbris je učinkovit, saj vemo, da je prejšnje in naslednje vozlišče ter manipulacija lažja.

Zaključek

V tej vadnici smo podrobno razpravljali o dvojno povezanem seznamu v Javi. Dvojno povezan seznam je zapletena struktura, v kateri vsako vozlišče vsebuje kazalce na prejšnja in naslednja vozlišča. Upravljanje teh povezav je včasih težko in lahko vodi do okvare kode, če z njo ne ravnamo pravilno.

Na splošno so operacije dvojno povezanega seznama učinkovitejše, saj lahko prihranimo čas za prehod po seznamu, saj imamo tako prejšnje kot naslednje napotke.

Krožno dvojno povezan seznam je bolj zapleten in tvorijo krožni vzorec s prejšnjim kazalcem prvega vozlišča, ki kaže na zadnje vozlišče, naslednji kazalec zadnjega vozlišča pa na prvo vozlišče. Tudi v tem primeru so operacije učinkovite.

S tem smo končali s povezanim seznamom v Javi. Spremljajte še veliko vadnic o tehnikah iskanja in razvrščanja v Javi.

=> Obiščite tukaj za ekskluzivno serijo vadnic Java.

Dvojno povezan seznam v Javi - primeri izvajanja in kode