Meniu

Lista dublă legată în Java - Exemple de implementare și cod

  • Principal
  • Alte
  • Lista dublă legată în Java - Exemple de implementare și cod

doubly linked list java implementation code examples

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Acest tutorial explică lista dublă legată în Java împreună cu implementarea listei dublă legată, lista circulară legată dublu cod Java și exemple:

Lista legată este o reprezentare secvențială a elementelor. Fiecare element al listei conectate se numește „Nod”. Un tip de listă legată se numește „Listă legată individual”.

În aceasta, fiecare nod conține o parte de date care stochează date reale și o a doua parte care stochează indicatorul către următorul nod din listă. Am aflat deja detaliile listei conectate individual în tutorialul nostru anterior.

=> Verificați TOATE Tutorialele Java aici.

Lista dublă legată în Java

Ce veți învăța:

Listă dublă legată în Java

O listă legată are o altă variantă numită „listă dublă legătură”. O listă dublă legată are un indicator suplimentar cunoscut ca indicatorul anterior în nodul său, în afară de partea de date și următorul indicator ca în lista legată individual.

Un nod din lista dublu legată arată după cum urmează:

îmbinarea interioară stângă vs îmbinarea exterioară stângă

nod din lista dublu legată

Aici, „Prev” și „Next” sunt indicatori către elementele anterioare și respectiv următoare ale nodului. „Date” este elementul real care este stocat în nod.

Figura următoare prezintă o listă dublă legată.

listă dublu legată

Diagrama de mai sus arată lista dublu legată. Există patru noduri în această listă. După cum puteți vedea, indicatorul anterior al primului nod și următorul indicator al ultimului nod sunt setate la nul. Pointerul anterior setat la nul indică faptul că acesta este primul nod din lista dublă legată, în timp ce următorul pointer setat la nul indică faptul că nodul este ultimul nod.

Avantaje

  1. Deoarece fiecare nod are indicii care indică nodurile anterioare și următoare, lista dublă legată poate fi parcursă cu ușurință în direcția înainte și înapoi
  2. Puteți adăuga rapid noul nod doar schimbând pointerele.
  3. În mod similar, pentru operația de ștergere, deoarece avem indicații anterioare și următoare, ștergerea este mai ușoară și nu trebuie să parcurgem întreaga listă pentru a găsi nodul anterior, ca în cazul listei conectate individual.

Dezavantaje

  1. Deoarece există un indicator suplimentar în lista dublu legată, adică indicatorul anterior, este necesar spațiu de memorie suplimentar pentru a stoca acest indicator împreună cu următorul indicator și element de date.
  2. Toate operațiunile, cum ar fi adăugarea, ștergerea etc. necesită manipularea atât a pointerilor anteriori, cât și a celor următoare, impunând astfel o cheltuială operativă.

Implementare în Java

Implementarea listei dublu legate în Java cuprinde crearea unei clase de listă dublă legătură, clasa nodurilor și adăugarea de noduri la lista dublă legată

Adăugarea de noi noduri se face de obicei la sfârșitul listei. Diagrama de mai jos arată adăugarea noului nod la sfârșitul listei dublu legate.

Implementarea listei în legătură dublă în Java

Așa cum se arată în diagrama de mai sus, pentru a adăuga un nou nod la sfârșitul listei, următorul indicator al ultimului nod indică acum noul nod în loc de nul. Pointerul anterior al noului nod indică ultimul nod. De asemenea, următorul indicator al noului nod indică spre nul, făcându-l astfel un nou ultim nod.

Programul de mai jos prezintă implementarea Java a unei liste dublă legată cu adăugarea de noi noduri la sfârșitul listei.

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

Ieșire:

Noduri ale listei dublu conectate:
10 20 30 40 50

Ieșire - adăugarea de noi noduri

În afară de adăugarea unui nod nou la sfârșitul listei, puteți adăuga și un nod nou la începutul listei sau între listă. Lăsăm această implementare în seama cititorului, astfel încât cititorii să poată înțelege operațiunile într-un mod mai bun.

Listă circulară legată dublu în Java

O listă circulară dublă legată este una dintre structurile complexe. În această listă, ultimul nod din lista dublă legată conține adresa primului nod, iar primul nod conține adresa ultimului nod. Astfel, într-o listă circulară dublă legată, există un ciclu și niciunul dintre indicii nodului nu este setat la nul.

Următoarea diagramă arată lista circulară dublă legată.

listă circulară dublă legată

Așa cum se arată în diagrama de mai sus, următorul indicator al ultimului nod indică primul nod. Pointerul anterior al primului nod indică ultimul nod.

Listele circulare dublu legate au aplicații largi în industria software-ului. O astfel de aplicație este aplicația muzicală care are o listă de redare. În lista de redare, când ați terminat de redat toate melodiile, apoi la sfârșitul ultimei melodii, reveniți automat la prima melodie. Acest lucru se face folosind liste circulare.

Avantajele unei liste circulare dublu conectate:

  1. Lista circulară dublă legată poate fi traversată de la cap la coadă sau coadă la cap.
  2. Trecerea de la cap la coadă sau coadă la cap este eficientă și necesită doar timp constant O (1).
  3. Poate fi folosit pentru implementarea structurilor de date avansate, inclusiv heap-ul Fibonacci.

Dezavantaje:

gateway implicit nu este disponibil Windows 10 2019
  1. Deoarece fiecare nod trebuie să facă spațiu pentru indicatorul anterior, este necesară memorie suplimentară.
  2. Trebuie să avem de-a face cu o mulțime de indicatori în timp ce efectuăm operațiuni pe o listă circulară dublă legată. Dacă indicii nu sunt tratați corect, atunci implementarea se poate întrerupe.

Programul Java de mai jos prezintă implementarea listei circulare dublu legată.

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

Ieșire:

Lista circulară dublă legată: 40 50 60 70 80
Listă circulară dublă legată înapoi:
80 70 60 50 40

ieșire - Listă circulară dublă legată

În programul de mai sus, am adăugat nodul la sfârșitul listei. Deoarece lista este circulară, când se adaugă noul nod, următorul indicator al noului nod va indica primul nod, iar indicatorul anterior al primului nod va indica noul nod.

În mod similar, indicatorul anterior al noului nod va indica ultimul nod curent care va deveni acum al doilea ultim nod. Lăsăm implementarea adăugării unui nou nod la începutul listei și între noduri cititorilor.

întrebări frecvente

Q # 1) Lista dublă legată poate fi circulară?

Răspuns: Da. Este o structură de date mai complexă. Într-o listă circulară dublu legată, indicatorul anterior al primului nod conține adresa ultimului nod, iar următorul indicator al ultimului nod conține adresa primului nod.

Q # 2) Cum creați o listă legată în mod circular dublu?

Răspuns: Puteți crea o clasă pentru o listă legată dublu circular. În interiorul acestei clase, va exista o clasă statică pentru a reprezenta nodul. Fiecare nod va conține doi indicatori - anterior și următor și un element de date. Apoi, puteți efectua operațiuni pentru a adăuga noduri în listă și pentru a traversa lista.

Î. # 3) Lista dublă este liniară sau circulară?

Răspuns: Lista dublu legată este o structură liniară, dar o listă circulară dublă legată, care are coada îndreptată spre cap și capul îndreptat spre coadă. Prin urmare, este o listă circulară.

Q # 4) Care este diferența dintre lista cu legături duble și lista cu legături circulare?

Răspuns: O listă dublă legată are noduri care păstrează informații despre nodurile sale anterioare și următoare folosind pointerele anterioare și respectiv următoare. De asemenea, indicatorul anterior al primului nod și următorul indicator al ultimului nod sunt setate la nul în lista dublu legată.

În lista circulară legată, nu există noduri de început sau de sfârșit, iar nodurile formează un ciclu. De asemenea, niciunul dintre indicatori nu este setat la nul în lista circulară legată.

Î # 5) Care sunt avantajele unei liste dublu legate?

Răspuns: Avantajele listei cu legături duble sunt:

  1. Poate fi parcurs în direcția înainte și înapoi.
  2. Operația de inserare este mai ușoară, deoarece nu este necesar să traversăm întreaga listă pentru a găsi elementul anterior.
  3. Ștergerea este eficientă, deoarece știm că nodurile anterioare și următoare și manipularea sunt mai ușoare.

Concluzie

În acest tutorial, am discutat în detaliu lista cu legături duble în Java. O listă dublă legată este o structură complexă în care fiecare nod conține indicatori către nodurile sale anterioare și următoare. Gestionarea acestor legături este uneori dificilă și poate duce la defalcarea codului dacă nu este tratată corespunzător.

În general, operațiunile unei liste dublă sunt mai eficiente, deoarece putem economisi timp pentru parcurgerea listei, deoarece avem atât indicatorii anteriori, cât și următorii.

Lista circulară dublă legată este mai complexă și formează un model circular cu indicatorul anterior al primului nod îndreptat către ultimul nod și următorul indicator al ultimului nod care indică primul nod. În acest caz, de asemenea, operațiunile sunt eficiente.

Cu aceasta, am terminat cu lista legată în Java. Rămâneți la curent cu multe alte tutoriale despre căutarea și sortarea tehnicilor în Java.

=> Vizitați aici pentru seria exclusivă de instruiri Java.

Lectură recomandată

^