Menu

Dvojnásobne prepojený zoznam v prostredí Java - implementácia a príklady kódov

  • Hlavná
  • Iné
  • Dvojnásobne prepojený zoznam v prostredí Java - implementácia a príklady kódov

doubly linked list java implementation code examples

V tomto výučbe sa vysvetľuje zoznam dvojnásobne prepojených v jazyku Java spolu s implementáciou dvojitého prepojeného zoznamu, kód Java v kruhovom dvojitom prepojení a príklady:

Prepojený zoznam je postupným znázornením prvkov. Každý prvok prepojeného zoznamu sa nazýva „Uzol“. Jeden typ prepojeného zoznamu sa nazýva „Singly linked list“.

V tomto každý uzol obsahuje dátovú časť, ktorá uchováva skutočné údaje, a druhú časť, ktorá uchováva ukazovateľ na ďalší uzol v zozname. Podrobnosti o jednotlivo prepojenom zozname sme sa už dozvedeli v našom predchádzajúcom tutoriáli.

=> Skontrolujte VŠETKY návody Java tu.

Dvojnásobne prepojený zoznam v Jave

Čo sa dozviete:

Dvojnásobne prepojený zoznam v Jave

Prepojený zoznam má ďalšiu variáciu nazvanú „dvojnásobne prepojený zoznam“. Zoznam, ktorý je dvojnásobne prepojený, má vo svojom uzle ďalší ukazovateľ známy ako predchádzajúci ukazovateľ okrem dátovej časti a ďalší ukazovateľ ako v jednotlivo prepojenom zozname.

Uzol v zozname, ktorý je dvakrát prepojený, vyzerá takto:

uzol v zozname, ktorý je dvojnásobne prepojený

rýchle triedenie pseudokódu c ++

Tu sú „Predchádzajúci“ a „Ďalej“ ukazovateľmi na predchádzajúci a nasledujúci prvok uzla. „Údaje“ sú skutočným prvkom, ktorý je uložený v uzle.

Nasledujúci obrázok zobrazuje zoznam, ktorý je dvojnásobne prepojený.

dvojnásobne prepojený zoznam

Vyššie uvedený diagram zobrazuje dvojnásobne prepojený zoznam. V tomto zozname sú štyri uzly. Ako vidíte, predchádzajúci ukazovateľ prvého uzla a nasledujúci ukazovateľ posledného uzla sú nastavený na hodnotu null. Predchádzajúci ukazovateľ nastavený na hodnotu null označuje, že ide o prvý uzol v zozname dvojnásobne prepojených, zatiaľ čo ďalší ukazovateľ nastavený na hodnotu null označuje, že uzol je posledným uzlom.

Výhody

  1. Pretože každý uzol má ukazovatele smerujúce na predchádzajúci a nasledujúci uzol, v dvojito prepojenom zozname je možné ľahko prechádzať smerom dopredu aj dozadu
  2. Nový uzol môžete rýchlo pridať jednoduchou zmenou ukazovateľov.
  3. Podobne pre operáciu mazania, pretože máme predchádzajúce aj nasledujúce ukazovatele, je mazanie jednoduchšie a nemusíme prechádzať celým zoznamom, aby sme našli predchádzajúci uzol, ako v prípade jednotlivo prepojeného zoznamu.

Nevýhody

  1. Pretože v zozname, ktorý je dvojnásobne prepojený, t. J. V predchádzajúcom ukazovateli, je ďalší ukazovateľ, je potrebný ďalší pamäťový priestor na uloženie tohto ukazovateľa spolu s ďalším ukazovateľom a údajovou položkou.
  2. Všetky operácie, ako je pridávanie, mazanie atď., Vyžadujú, aby sa manipulovalo s predchádzajúcim aj nasledujúcim ukazovateľom, čo si vyžaduje prevádzkovú réžiu.

Implementácia v Jave

Implementácia dvojnásobne prepojeného zoznamu v Jave spočíva v vytvorení triedy dvojnásobne prepojeného zoznamu, triedy uzlov a pridania uzlov do dvojnásobne prepojeného zoznamu.

Pridanie nových uzlov sa zvyčajne vykonáva na konci zoznamu. Nasledujúci diagram zobrazuje pridanie nového uzla na koniec dvojnásobne prepojeného zoznamu.

Implementácia dvojnásobne prepojeného zoznamu v Jave

Ako je znázornené na vyššie uvedenom diagrame, pre pridanie nového uzla na koniec zoznamu ďalší ukazovateľ posledného uzla ukazuje na nový uzol namiesto hodnoty null. Predchádzajúci ukazovateľ nového uzla smeruje na posledný uzol. Nasledujúci ukazovateľ nového uzla tiež ukazuje na nulu, čím sa stáva novým posledným uzlom.

Nasledujúci program ukazuje implementáciu Java zoznamu s dvojnásobným prepojením s pridaním nových uzlov na konci zoznamu.

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

Výkon:

Uzly dvojnásobne prepojeného zoznamu:
10 20 30 40 50

Výstup - pridanie nových uzlov

Okrem pridania nového uzla na koniec zoznamu môžete pridať nový uzol aj na začiatok zoznamu alebo medzi zoznam. Túto implementáciu prenecháme čitateľovi, aby čitatelia mohli operáciám lepšie porozumieť.

Kruhový dvojnásobne prepojený zoznam v Jave

Kruhový dvojnásobne prepojený zoznam je jednou zo zložitých štruktúr. V tomto zozname obsahuje posledný uzol dvojnásobne prepojeného zoznamu adresu prvého uzla a prvý uzol obsahuje adresu posledného uzla. Takže v kruhovom dvojnásobne prepojenom zozname existuje cyklus a žiadny z ukazovateľov uzlov nie je nastavený na hodnotu null.

Nasledujúci diagram zobrazuje kruhový dvojnásobne prepojený zoznam.

kruhový dvojnásobne prepojený zoznam

Ako je zrejmé z vyššie uvedeného diagramu, ďalší ukazovateľ posledného uzla smeruje k prvému uzlu. Predchádzajúci ukazovateľ prvého uzla smeruje na posledný uzol.

Kruhové zoznamy s dvojitým prepojením majú široké uplatnenie v softvérovom priemysle. Jednou z takýchto aplikácií je hudobná aplikácia so zoznamom skladieb. Po dokončení prehrávania všetkých skladieb v zozname skladieb sa na konci poslednej skladby automaticky vrátite na prvú skladbu. To sa deje pomocou kruhových zoznamov.

Výhody kruhového dvojitého prepojeného zoznamu:

  1. Kruhový dvojnásobne prepojený zoznam je možné prechádzať od hlavy po chvost alebo od chvosta k hlave.
  2. Prechod z hlavy na chvost alebo z chvosta na hlavu je efektívny a trvá len konštantný čas O (1).
  3. Môže byť použitý na implementáciu pokročilých dátových štruktúr vrátane haldy Fibonacci.

Nevýhody:

  1. Pretože každý uzol potrebuje uvoľniť miesto pre predchádzajúci ukazovateľ, je potrebná ďalšia pamäť.
  2. Musíme robiť veľa ukazovateľov pri vykonávaní operácií na kruhovom dvojnásobne prepojenom zozname. Ak ukazovatele nebudú spracované správne, implementácia sa môže prerušiť.

Nižšie uvedený program Java ukazuje implementáciu zoznamu Circular dvojnásobne prepojených.

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

Výkon:

Kruhový dvojnásobne prepojený zoznam: 40 50 60 70 80
Kruhový dvojnásobne prepojený zoznam trasovaný dozadu:
80 70 60 50 40

výstup - kruhový dvojnásobne prepojený zoznam

Vo vyššie uvedenom programe sme pridali uzol na koniec zoznamu. Pretože je zoznam kruhový, po pridaní nového uzla bude ďalší ukazovateľ nového uzla ukazovať na prvý uzol a predchádzajúci ukazovateľ prvého uzla bude ukazovať na nový uzol.

Podobne predchádzajúci ukazovateľ nového uzla bude ukazovať na posledný posledný uzol, ktorý sa teraz stane druhým posledným uzlom. Implementáciu pridania nového uzla ponechávame na začiatku zoznamu a medzi uzlami čitateľom.

často kladené otázky

Otázka č. 1) Môže byť zoznam s dvojnásobným prepojením kruhový?

Odpoveď: Áno. Je to zložitejšia dátová štruktúra. V kruhovom dvojnásobne prepojenom zozname obsahuje predchádzajúci ukazovateľ prvého uzla adresu posledného uzla a nasledujúci ukazovateľ posledného uzla obsahuje adresu prvého uzla.

Otázka 2) Ako vytvoríte zoznam, ktorý je nepochybne kruhový?

Odpoveď: Môžete vytvoriť triedu pre dvojnásobne kruhový prepojený zoznam. Vo vnútri tejto triedy bude statická trieda predstavujúca uzol. Každý uzol bude obsahovať dva ukazovatele - predchádzajúci a nasledujúci a údajovú položku. Potom môžete vykonať operácie na pridanie uzlov do zoznamu a na prechádzanie zoznamu.

Otázka č. 3) Je zoznam s dvojnásobným prepojením lineárny alebo kruhový?

najlepší softvér na konverziu videa pre Mac

Odpoveď: Dvojnásobne prepojený zoznam je lineárna štruktúra, ale kruhový dvojito prepojený zoznam, ktorý má chvost smerujúci k hlave a smerujúci k chvostu. Preto je to kruhový zoznam.

Otázka č. 4) Aký je rozdiel medzi zoznamom s dvojitým prepojením a zoznamom s kruhovým prepojením?

Odpoveď: Zoznam, ktorý je dvojnásobne prepojený, má uzly, ktoré uchovávajú informácie o svojich predchádzajúcich aj nasledujúcich uzloch pomocou predchádzajúceho a nasledujúceho ukazovateľa. Predošlý ukazovateľ prvého uzla a nasledujúci ukazovateľ posledného uzla sú tiež v zozname dvojnásobne prepojených na nulu.

V kruhovo prepojenom zozname nie sú žiadne začiatočné ani koncové uzly a uzly tvoria cyklus. Ani jeden z ukazovateľov nie je v kruhovom prepojenom zozname nastavený na hodnotu null.

Otázka č. 5) Aké sú výhody nepochybne prepojeného zoznamu?

Odpoveď: Výhody zoznamu, ktorý je nepochybne prepojený, sú:

  1. Dá sa s ním prechádzať v smere dopredu aj dozadu.
  2. Operácia vloženia je jednoduchšia, pretože na nájdenie predchádzajúceho prvku nemusíme prechádzať celým zoznamom.
  3. Vymazanie je efektívne, pretože vieme, že predchádzajúci a nasledujúci uzol a manipulácia s ním je ľahšia.

Záver

V tomto tutoriáli sme sa podrobne zaoberali zoznamom Doubly linked link v Jave. Zoznam, ktorý je dvojnásobne prepojený, je zložitá štruktúra, v ktorej každý uzol obsahuje ukazovatele na jeho predchádzajúce aj nasledujúce uzly. Správa týchto odkazov je niekedy zložitá a môže viesť k poruchám kódu, ak sa s nimi nebude narábať správne.

Celkovo sú operácie dvojnásobne prepojeného zoznamu efektívnejšie, pretože môžeme ušetriť čas na prechádzanie zoznamu, pretože máme predchádzajúci aj nasledujúci ukazovateľ.

Kruhový dvojnásobne prepojený zoznam je zložitejší a tvoria kruhový vzor, ​​pričom predchádzajúci ukazovateľ prvého uzla smeruje k poslednému uzlu a ďalší ukazovateľ posledného uzla smeruje k prvému uzlu. Aj v tomto prípade sú operácie efektívne.

Týmto sme dokončili prepojený zoznam v Jave. Zostaňte naladení na ďalšie výukové programy o technikách vyhľadávania a triedenia v prostredí Java.

=> Navštívte tu sériu exkluzívnych výukových programov Java.

Odporúčané čítanie

^