Popis dvostruko povezanih na Javi

doubly linked list java implementation code examples

Isprobajte Naš Instrument Za Uklanjanje Problema

Odaberite Operativni Sustav Odaberite Program Projekcije (Po Želji)

Opišite Svoj Problem

Ovaj vodič objašnjava dvostruko povezani popis na Javi, zajedno s implementacijom dvostruko povezanog popisa, kružni dvostruko povezan popis Java koda i primjeri:

Povezani popis je sekvencijalni prikaz elemenata. Svaki se element povezanog popisa naziva „čvor”. Jedna vrsta povezanog popisa naziva se 'Pojedinačno povezani popis'.

U tome svaki čvor sadrži podatkovni dio koji pohranjuje stvarne podatke i drugi dio koji pohranjuje pokazivač na sljedeći čvor na popisu. Pojedinosti pojedinačno povezanog popisa već smo naučili u našem prethodnom vodiču.

=> Ovdje provjerite SVE Java tutorijale.

Popis dvostruko povezanih na Javi

Što ćete naučiti:

Popis dvostruko povezanih na Javi
Kružni dvostruko povezani popis na Javi
- Često postavljana pitanja
Zaključak
- Preporučena literatura

Povezani popis ima još jednu varijaciju koja se naziva 'dvostruko povezani popis'. Dvostruko povezani popis u svom čvoru ima dodatni pokazivač poznat kao prethodni pokazivač, osim dijela podataka i sljedeći pokazivač kao na pojedinačno povezanom popisu.

Čvor na dvostruko povezanom popisu izgleda kako slijedi:

koji je najbolji račun e-pošte

čvor na dvostruko povezanom popisu

Ovdje su 'Prev' i 'Next' pokazivači na prethodni i sljedeći elementi čvora. ‘Podaci’ su stvarni element koji je pohranjen u čvoru.

Sljedeća slika prikazuje dvostruko povezan popis.

dvostruko povezana lista

Gornji dijagram prikazuje dvostruko povezan popis. Na ovom su popisu četiri čvora. Kao što vidite, prethodni pokazivač prvog čvora i sljedeći pokazivač zadnjeg čvora postavljeni su na nulu. Prethodni pokazivač postavljen na nulu označava da je ovo prvi čvor na dvostruko povezanom popisu, dok sljedeći pokazivač postavljen na nulu označava da je čvor posljednji čvor.

Prednosti

Kako svaki čvor ima pokazivače koji upućuju na prethodni i sljedeći čvor, dvostruko povezani popis može se lako prelaziti u smjeru naprijed, kao i natrag
Možete brzo dodati novi čvor samo promjenom pokazivača.
Slično tome, za operaciju brisanja budući da imamo prethodne, kao i sljedeće pokazivače, brisanje je lakše i ne trebamo prelaziti cijeli popis da bismo pronašli prethodni čvor kao u slučaju pojedinačno povezanog popisa.

Mane

Budući da se na dvostruko povezanom popisu nalazi dodatni pokazivač, tj. Prethodni pokazivač, potreban je dodatni prostor memorije za spremanje ovog pokazivača zajedno sa sljedećim pokazivačem i stavkom podataka.
Sve operacije poput dodavanja, brisanja itd. Zahtijevaju da se manipulira i prethodnim i sljedećim pokazivačima, namećući tako operativne režijske troškove.

Implementacija u Javi

Implementacija dvostruko povezanog popisa u Javi sastoji se od stvaranja dvostruko povezane klase popisa, klase čvorova i dodavanja čvorova na dvostruko povezanu listu

Dodavanje novih čvorova obično se vrši na kraju popisa. Dijagram u nastavku prikazuje dodavanje novog čvora na kraju dvostruko povezanog popisa.

Implementacija dvostruko povezanog popisa u Javi

Kao što je prikazano na gornjem dijagramu, da biste na kraj popisa dodali novi čvor, sljedeći pokazivač zadnjeg čvora sada usmjerava na novi čvor umjesto na nulu. Prethodni pokazivač novog čvora pokazuje na posljednji čvor. Također, sljedeći pokazivač novog čvora pokazuje nulu, čineći ga time novim posljednjim čvorom.

Program u nastavku prikazuje Java implementaciju dvostruko povezanog popisa s dodatkom novih čvorova na kraju popisa.

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

Izlaz:

Čvorovi dvostruko povezanog popisa:
10 20 30 40 50

Izlaz - dodavanje novih čvorova

Osim dodavanja novog čvora na kraju popisa, možete dodati i novi čvor na početku popisa ili između popisa. Ovu provedbu prepuštamo čitatelju kako bi čitatelji mogli bolje razumjeti radnje.

Kružni dvostruko povezani popis na Javi

Kružni dvostruko povezani popis jedna je od složenih struktura. Na ovom popisu posljednji čvor dvostruko povezanog popisa sadrži adresu prvog čvora, a prvi čvor sadrži adresu posljednjeg čvora. Dakle, na kružnom dvostruko povezanom popisu postoji ciklus i niti jedan od pokazivača na čvor nije postavljen na nulu.

Sljedeći dijagram prikazuje kružni dvostruko povezan popis.

kružni dvostruko povezani popis

Kao što je prikazano na gornjem dijagramu, sljedeći pokazivač zadnjeg čvora pokazuje na prvi čvor. Prethodni pokazivač prvog čvora pokazuje na posljednji čvor.

Kružni dvostruko povezani popisi imaju široku primjenu u softverskoj industriji. Jedna od takvih aplikacija je glazbena aplikacija koja ima popis za reprodukciju. Na popisu pjesama, kada završite s reprodukcijom svih pjesama, na kraju posljednje pjesme automatski se vraćate na prvu pjesmu. To se radi pomoću kružnih popisa.

Prednosti kružnog dvostruko povezanog popisa:

Kružnim dvostruko povezanim popisom može se prelaziti od glave do repa ili repa do glave.
Prijelaz od glave do repa ili repa do glave učinkovit je i traje samo stalno vrijeme O (1).
Može se koristiti za implementaciju naprednih struktura podataka, uključujući Fibonaccijevu hrpu.

Mane:

Kako svaki čvor treba osloboditi prostor za prethodni pokazivač, potrebna je dodatna memorija.
Moramo se nositi s puno pokazivača dok izvodimo operacije na kružnom dvostruko povezanom popisu. Ako se s pokazivačima ne rukuje pravilno, implementacija se može prekinuti.

Sljedeći Java program prikazuje provedbu dvostruko povezanog popisa 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(); } }

Izlaz:

Kružni dvostruko povezani popis: 40 50 60 70 80
Kružni dvostruko povezani popis kretao se unatrag:
80 70 60 50 40

izlaz - kružni dvostruko povezani popis

razlika između ponovnog ispitivanja i regresijskog ispitivanja

U gornji program dodali smo čvor na kraju popisa. Kako je popis kružan, kad se doda novi čvor, sljedeći pokazivač novog čvora ukazat će na prvi čvor, a prethodni pokazivač prvog čvora na novi čvor.

Slično tome, prethodni pokazivač novog čvora ukazat će na trenutni posljednji čvor koji će sada postati drugi posljednji čvor. Implementaciju dodavanja novog čvora ostavljamo na početku popisa i između čvorova čitateljima.

Često postavljana pitanja

P # 1) Može li dvostruko povezani popis biti kružan?

Odgovor: Da. To je složenija struktura podataka. U kružnom dvostruko povezanom popisu, prethodni pokazivač prvog čvora sadrži adresu posljednjeg čvora, a sljedeći pokazivač posljednjeg čvora sadrži adresu prvog čvora.

P # 2) Kako stvoriti dvostruko kružno povezan popis?

Odgovor: Možete stvoriti predavanje za dvostruko kružni povezani popis. Unutar ove klase nalazit će se statička klasa koja predstavlja čvor. Svaki čvor sadržavat će dva pokazivača - prethodni i sljedeći te stavku podataka. Tada možete imati operacije dodavanja čvorova na popis i prelaska po popisu.

P # 3) Je li dvostruko povezan popis linearni ili kružni?

Odgovor: Dvostruko povezan popis linearna je struktura, ali kružni dvostruko povezan popis čiji je rep usmjeren prema glavi, a glava usmjerena prema repu. Stoga je to kružni popis.

P # 4) Koja je razlika između dvostruko povezanog popisa i kružno povezanog popisa?

Odgovor: Dvostruko povezani popis ima čvorove koji čuvaju informacije o svojim prethodnim, kao i o sljedećim čvorovima koristeći prethodne i sljedeće pokazivače. Također, prethodni pokazivač prvog čvora i sljedeći pokazivač zadnjeg čvora postavljeni su na nulu na dvostruko povezanom popisu.

Na kružno povezanom popisu nema početnog ili završnog čvora i čvorovi čine ciklus. Također, niti jedan od pokazivača nije postavljen na nulu na kružno povezanom popisu.

P # 5) Koje su prednosti dvostruko povezanog popisa?

Odgovor: Prednosti dvostruko povezanog popisa su:

Može se kretati u smjeru prema naprijed, kao i prema natrag.
Operacija umetanja je lakša jer ne trebamo prelaziti cijeli popis da bismo pronašli prethodni element.
Brisanje je učinkovito jer znamo da su prethodni i sljedeći čvorovi i upravljanje njima lakši.

Zaključak

U ovom uputstvu detaljno smo razgovarali o dvostruko povezanom popisu na Javi. Dvostruko povezan popis složena je struktura u kojoj svaki čvor sadrži pokazivače na svoje prethodne, kao i na sljedeće čvorove. Upravljanje tim vezama ponekad je teško i može dovesti do sloma koda ako se s njim ne postupa pravilno.

Sve u svemu, operacije dvostruko povezanog popisa učinkovitije su jer možemo uštedjeti vrijeme za prelazak popisa jer imamo i prethodne i sljedeće smjernice.

Dvostruko kružni popis složeniji je i čine kružni uzorak s prethodnim pokazivačem prvog čvora koji pokazuje na posljednji čvor i sljedećim pokazivačem posljednjeg čvora koji pokazuje na prvi čvor. U ovom su slučaju i operacije učinkovite.

S ovim smo završili s povezanim popisom u Javi. Pratite još mnogo vodiča o tehnikama pretraživanja i sortiranja na Javi.

=> Posjetite ovdje za ekskluzivnu seriju udžbenika za Java.

Popis dvostruko povezanih na Javi - primjeri implementacije i koda