Menu

Elenco doppiamente collegato in Java - Esempi di implementazione e codice

  • Principale
  • Altro
  • Elenco doppiamente collegato in Java - Esempi di implementazione e codice

doubly linked list java implementation code examples

Prova Il Nostro Strumento Per Eliminare I Problemi

Questo tutorial spiega l'elenco a doppio collegamento in Java insieme all'implementazione dell'elenco a doppio collegamento, il codice Java dell'elenco a doppio collegamento circolare ed esempi:

L'elenco collegato è una rappresentazione sequenziale di elementi. Ogni elemento dell'elenco collegato è chiamato 'Nodo'. Un tipo di elenco collegato è denominato 'Elenco collegato singolarmente'.

In questo, ogni nodo contiene una parte dati che memorizza i dati effettivi e una seconda parte che memorizza il puntatore al nodo successivo nell'elenco. Abbiamo già imparato i dettagli dell'elenco collegato singolarmente nel nostro precedente tutorial.

=> Controlla TUTTI i tutorial Java qui.

Elenco doppiamente collegato in Java

Cosa imparerai:

Elenco doppiamente collegato in Java

Una lista collegata ha un'altra variante chiamata 'lista doppiamente collegata'. Una lista doppiamente collegata ha un puntatore aggiuntivo noto come puntatore precedente nel suo nodo oltre alla parte dati e il puntatore successivo come nella lista collegata singolarmente.

Un nodo nell'elenco a doppio collegamento ha il seguente aspetto:

come rimuovere un elemento da un array in java

nodo nella lista doppiamente collegata

Qui, 'Prev' e 'Next' sono puntatori rispettivamente agli elementi precedente e successivo del nodo. I 'Dati' sono l'elemento effettivo archiviato nel nodo.

La figura seguente mostra un elenco a doppio collegamento.

lista doppiamente collegata

Il diagramma sopra mostra l'elenco a doppio collegamento. Ci sono quattro nodi in questo elenco. Come puoi vedere, il puntatore precedente del primo nodo e il puntatore successivo dell'ultimo nodo sono impostati su null. Il puntatore precedente impostato su null indica che questo è il primo nodo nell'elenco a doppio collegamento mentre il puntatore successivo impostato su null indica che il nodo è l'ultimo nodo.

Vantaggi

  1. Poiché ogni nodo ha puntatori che puntano al nodo precedente e successivo, l'elenco a doppio collegamento può essere attraversato facilmente sia in avanti che all'indietro
  2. Puoi aggiungere rapidamente il nuovo nodo semplicemente cambiando i puntatori.
  3. Allo stesso modo, per l'operazione di eliminazione poiché abbiamo puntatori precedenti e successivi, l'eliminazione è più semplice e non è necessario attraversare l'intero elenco per trovare il nodo precedente come nel caso dell'elenco collegato singolarmente.

Svantaggi

  1. Poiché è presente un puntatore aggiuntivo nell'elenco a doppio collegamento, ovvero il puntatore precedente, è necessario ulteriore spazio di memoria per memorizzare questo puntatore insieme al puntatore e all'elemento dati successivo.
  2. Tutte le operazioni come l'aggiunta, l'eliminazione, ecc. Richiedono che sia i puntatori precedenti che quelli successivi vengano manipolati imponendo un sovraccarico operativo.

Implementazione in Java

L'implementazione di una lista doppiamente collegata in Java comprende la creazione di una classe di lista doppiamente collegata, la classe del nodo e l'aggiunta di nodi alla lista doppiamente collegata

L'aggiunta di nuovi nodi viene solitamente eseguita alla fine dell'elenco. Il diagramma seguente mostra l'aggiunta del nuovo nodo alla fine dell'elenco a doppio collegamento.

Implementazione di elenchi doppiamente collegati in Java

Come mostrato nel diagramma sopra, per aggiungere un nuovo nodo alla fine dell'elenco, il puntatore successivo dell'ultimo nodo punta ora al nuovo nodo invece che a null. Il puntatore precedente del nuovo nodo punta all'ultimo nodo. Inoltre, il puntatore successivo del nuovo nodo punta a null, rendendolo così un nuovo ultimo nodo.

Il programma seguente mostra l'implementazione Java di un elenco a doppio collegamento con l'aggiunta di nuovi nodi alla fine dell'elenco.

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

Produzione:

Nodi di lista doppiamente collegata:
10 20 30 40 50

Output: aggiunta di nuovi nodi

Oltre ad aggiungere un nuovo nodo alla fine dell'elenco, puoi anche aggiungere un nuovo nodo all'inizio dell'elenco o tra l'elenco. Lasciamo questa implementazione al lettore in modo che i lettori possano capire le operazioni in un modo migliore.

Elenco circolare doppiamente collegato in Java

Una lista circolare doppiamente concatenata è una delle strutture complesse. In questa lista, l'ultimo nodo della lista doppiamente collegata contiene l'indirizzo del primo nodo e il primo nodo contiene l'indirizzo dell'ultimo nodo. Pertanto, in una lista circolare doppiamente concatenata, c'è un ciclo e nessuno dei puntatori del nodo è impostato su null.

Il diagramma seguente mostra l'elenco circolare a doppio collegamento.

lista circolare doppiamente collegata

Come mostrato nel diagramma sopra, il puntatore successivo dell'ultimo nodo punta al primo nodo. Il puntatore precedente del primo nodo punta all'ultimo nodo.

Gli elenchi circolari doppiamente concatenati hanno ampie applicazioni nell'industria del software. Una di queste applicazioni è l'app musicale che ha una playlist. Nella playlist, quando finisci di riprodurre tutti i brani, quindi alla fine dell'ultimo brano, torni automaticamente al primo brano. Questo viene fatto utilizzando elenchi circolari.

Vantaggi di un elenco circolare a doppio collegamento:

  1. La lista circolare doppiamente concatenata può essere attraversata dalla testa alla coda o dalla coda alla testa.
  2. Passare dalla testa alla coda o dalla coda alla testa è efficiente e richiede solo un tempo costante O (1).
  3. Può essere utilizzato per implementare strutture dati avanzate, incluso l'heap di Fibonacci.

Svantaggi:

domande e risposte dell'intervista all'analista qa
  1. Poiché ogni nodo deve fare spazio per il puntatore precedente, è necessaria memoria aggiuntiva.
  2. Abbiamo bisogno di gestire molti puntatori durante l'esecuzione di operazioni su un elenco circolare a doppia connessione. Se i puntatori non vengono gestiti correttamente, l'implementazione potrebbe interrompersi.

Il seguente programma Java mostra l'implementazione della lista Circolare doppiamente collegata.

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

Produzione:

Lista circolare doppiamente concatenata: 40 50 60 70 80
La lista circolare doppiamente concatenata scorre all'indietro:
80 70 60 50 40

output - Lista circolare doppiamente concatenata

Nel programma sopra, abbiamo aggiunto il nodo alla fine dell'elenco. Poiché l'elenco è circolare, quando viene aggiunto il nuovo nodo, il puntatore successivo del nuovo nodo punterà al primo nodo e il puntatore precedente del primo nodo punterà al nuovo nodo.

Allo stesso modo, il puntatore precedente del nuovo nodo punterà all'ultimo nodo corrente che ora diventerà il penultimo nodo. Lasciamo l'implementazione dell'aggiunta di un nuovo nodo all'inizio dell'elenco e tra i nodi ai lettori.

Domande frequenti

D # 1) La lista doppiamente collegata può essere circolare?

Risposta: Sì. È una struttura dati più complessa. In una lista circolare doppiamente concatenata, il puntatore precedente del primo nodo contiene l'indirizzo dell'ultimo nodo e il puntatore successivo dell'ultimo nodo contiene l'indirizzo del primo nodo.

D # 2) Come si crea un elenco collegato doppiamente circolare?

Risposta: Puoi creare una classe per un elenco collegato doppiamente circolare. All'interno di questa classe, ci sarà una classe statica per rappresentare il nodo. Ogni nodo conterrà due puntatori: precedente e successivo e un elemento di dati. Quindi puoi avere operazioni per aggiungere nodi all'elenco e per attraversare l'elenco.

D # 3) La lista doppiamente collegata è lineare o circolare?

Risposta: La lista doppiamente concatenata è una struttura lineare ma una lista circolare doppiamente concatenata che ha la coda puntata alla testa e la testa alla coda. Quindi è un elenco circolare.

D # 4) Qual è la differenza tra la lista collegata doppiamente e la lista collegata circolare?

Risposta: Una lista doppiamente collegata ha nodi che conservano le informazioni sui suoi nodi precedenti e successivi usando rispettivamente i puntatori precedente e successivo. Inoltre, il puntatore precedente del primo nodo e il puntatore successivo dell'ultimo nodo sono impostati su null nell'elenco a doppia connessione.

Nell'elenco collegato circolare, non ci sono nodi di inizio o fine ei nodi formano un ciclo. Inoltre, nessuno dei puntatori è impostato su null nell'elenco collegato circolare.

D # 5) Quali sono i vantaggi di un elenco a doppio collegamento?

Risposta: I vantaggi della lista doppiamente collegata sono:

  1. Può essere attraversato sia in avanti che all'indietro.
  2. L'operazione di inserimento è più semplice in quanto non è necessario attraversare l'intera lista per trovare l'elemento precedente.
  3. L'eliminazione è efficiente poiché sappiamo che i nodi precedenti e successivi e la manipolazione sono più facili.

Conclusione

In questo tutorial, abbiamo discusso in dettaglio l'elenco Doubly linkato in Java. Una lista doppiamente collegata è una struttura complessa in cui ogni nodo contiene puntatori ai suoi nodi precedenti e successivi. La gestione di questi collegamenti a volte è difficile e può portare alla rottura del codice se non gestita correttamente.

Nel complesso, le operazioni di una lista doppiamente collegata sono più efficienti in quanto possiamo risparmiare tempo per attraversare la lista poiché abbiamo sia il puntatore precedente che quello successivo.

La lista circolare doppiamente concatenata è più complessa e formano uno schema circolare con il puntatore precedente del primo nodo che punta all'ultimo nodo e il puntatore successivo dell'ultimo nodo che punta al primo nodo. Anche in questo caso le operazioni sono efficienti.

Con questo, abbiamo finito con l'elenco collegato in Java. Restate sintonizzati per molti altri tutorial sulle tecniche di ricerca e ordinamento in Java.

=> Visita qui per l'esclusiva serie di tutorial di formazione Java.

Lettura consigliata

^