doubly linked list java implementation code examples
Aquest tutorial explica la llista doblement enllaçada a Java juntament amb la implementació de la llista doblement enllaçada, el codi Java de la llista doblement enllaçada circular i exemples:
La llista enllaçada és una representació seqüencial d’elements. Cada element de la llista enllaçada s’anomena ‘node’. Un tipus de llista enllaçada es diu 'Llista enllaçada individualment'.
En això, cada node conté una part de dades que emmagatzema dades reals i una segona part que emmagatzema el punter al següent node de la llista. Ja hem après els detalls de la llista enllaçada individualment al nostre tutorial anterior.
=> Consulteu TOTS els tutorials de Java aquí.
Què aprendreu:
Llista doblement enllaçada a Java
Una llista enllaçada té una altra variació anomenada 'llista doblement enllaçada'. Una llista doblement enllaçada té un punter addicional conegut com a punter anterior al seu node, a part de la part de dades i el següent, com a la llista enllaçada individualment.
Un node de la llista doblement enllaçada té el següent aspecte:
tutorial de llista doblement enllaçada de c ++
Aquí, 'Anterior' i 'Següent' són indicadors dels elements anterior i següent del node respectivament. Les 'dades' són l'element real que s'emmagatzema al node.
La següent figura mostra una llista doblement enllaçada.
El diagrama anterior mostra la llista doblement enllaçada. Hi ha quatre nodes en aquesta llista. Com podeu veure, el punter anterior del primer node i el següent del darrer node es defineixen com a nul. El punter anterior establert a null indica que aquest és el primer node de la llista doblement enllaçat, mentre que el següent punter establert a null indica que el node és l'últim node.
Avantatges
- Com que cada node té indicadors que apunten als nodes anterior i següent, la llista doblement enllaçada es pot recórrer fàcilment tant en direcció endavant com en sentit invers.
- Podeu afegir ràpidament el nou node només canviant els indicadors.
- De la mateixa manera, per a l'operació de supressió ja que tenim punteres anteriors i següents, la supressió és més fàcil i no hem de recórrer tota la llista per trobar el node anterior com en el cas de la llista enllaçada individualment.
Desavantatges
- Com que hi ha un punter addicional a la llista doblement enllaçada, és a dir, el punter anterior, es requereix espai de memòria addicional per emmagatzemar aquest punter juntament amb el següent punter i element de dades.
- Totes les operacions com l'addició, la supressió, etc. requereixen que es manipulin tant els punters anteriors com els següents, cosa que imposa una sobrecàrrega operativa.
Implementació a Java
La implementació de la llista doblement enllaçada a Java consisteix en crear una classe de llista doblement enllaçada, la classe de node i afegir nodes a la llista doblement enllaçada.
L’addició de nodes nous es fa generalment al final de la llista. El diagrama següent mostra l’addició del nou node al final de la llista doblement enllaçada.
Com es mostra al diagrama anterior, per afegir un nou node al final de la llista, el següent punter de l'últim node ara apunta al nou node en lloc de nul. El punter anterior del nou node apunta a l'últim node. A més, el següent punter del nou node apunta a nul, convertint-lo en un nou darrer node.
El programa següent mostra la implementació de Java d'una llista doblement enllaçada amb l'addició de nous nodes al final de la llista.
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(); } }
Sortida:
Nodes de la llista doblement enllaçada:
10 20 30 40 50
A part d'afegir un nou node al final de la llista, també podeu afegir un node nou al principi de la llista o entre la llista. Deixem aquesta implementació al lector perquè els lectors puguin entendre millor les operacions.
Llista circular doblement enllaçada a Java
Una llista circular doblement enllaçada és una de les estructures complexes. En aquesta llista, l'últim node de la llista doblement enllaçada conté l'adreça del primer node i el primer node conté l'adreça del darrer node. Així, en una llista circular doblement enllaçada, hi ha un cicle i cap dels indicadors de node es defineix com a nul.
El diagrama següent mostra la llista circular doblement enllaçada.
Com es mostra al diagrama anterior, el següent punter de l'últim node apunta al primer node. El punter anterior del primer node apunta a l'últim node.
Les llistes circulars doblement enllaçades tenen àmplies aplicacions a la indústria del programari. Una d'aquestes aplicacions és l'aplicació musical que té una llista de reproducció. A la llista de reproducció, quan acabeu de reproduir totes les cançons i, al final de la darrera cançó, torneu a la primera cançó automàticament. Això es fa mitjançant llistes circulars.
Avantatges d'una llista circular enllaçada doble:
- La llista circular doblement enllaçada es pot recórrer de cap a cua o de cua a cap.
- Anar de cap a cua o cua a cap és eficient i només necessita temps constant O (1).
- Es pot utilitzar per implementar estructures de dades avançades, inclòs el munt de Fibonacci.
Desavantatges:
- Com que cada node necessita fer espai per al punter anterior, es necessita memòria addicional.
- Hem de tractar molts indicadors mentre realitzem operacions en una llista circular doblement enllaçada. Si els indicadors no es gestionen correctament, la implementació es pot trencar.
El programa Java següent mostra la implementació de la llista doblement enllaçada 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(); } }
Sortida:
Llista circular doblement enllaçada: 40 50 60 70 80
Llista circular doblement enllaçada retrocedida:
80 70 60 50 40
Al programa anterior, hem afegit el node al final de la llista. Com que la llista és circular, quan s'afegeix el nou node, el següent punter del nou node assenyalarà el primer node i el punter anterior del primer node assenyalarà el nou node.
De la mateixa manera, el punter anterior del nou node assenyalarà l'últim node actual, que ara es convertirà en el segon darrer node. Deixem la implementació d’afegir un nou node al principi de la llista i entre els nodes als lectors.
Preguntes freqüents
P # 1) La llista doblement enllaçada pot ser circular?
com es converteix en un provador de productes
Resposta: Sí. És una estructura de dades més complexa. En una llista circular doblement enllaçada, el punter anterior del primer node conté l'adreça del darrer node i el següent del darrer node conté l'adreça del primer node.
Q # 2) Com es crea una llista enllaçada doblement circular?
Resposta: Podeu crear una classe per a una llista enllaçada doblement circular. Dins d’aquesta classe, hi haurà una classe estàtica per representar el node. Cada node contindrà dos indicadors: anterior i següent i un element de dades. A continuació, podeu fer operacions per afegir nodes a la llista i recórrer la llista.
P # 3) La llista doblement enllaçada és lineal o circular?
Resposta: La llista doblement enllaçada és una estructura lineal, però una llista circular doblement enllaçada que té la cua apuntada cap al cap i el cap apuntat cap a la cua. Per tant, és una llista circular.
Q # 4) Quina diferència hi ha entre la llista doblement enllaçada i la llista enllaçada circular?
Resposta: Una llista doblement enllaçada té nodes que conserven informació sobre els nodes anterior i següent, mitjançant els punters anterior i següent, respectivament. A més, el punter anterior del primer node i el següent del darrer node es defineix com a nul a la llista doblement enllaçada.
A la llista enllaçada circular, no hi ha nodes inicials ni finals i els nodes formen un cicle. A més, cap dels indicadors no es defineix com a nul a la llista enllaçada circular.
P # 5) Quins avantatges té una llista doblement enllaçada?
Resposta: Els avantatges de la llista doblement enllaçada són:
- Es pot recórrer cap endavant i cap enrere.
- L'operació d'inserció és més senzilla, ja que no cal recórrer tota la llista per trobar l'element anterior.
- La supressió és eficaç, ja que sabem que els nodes anterior i següent i la manipulació són més fàcils.
Conclusió
En aquest tutorial, hem discutit detalladament la llista Doble enllaçada a Java. Una llista doblement enllaçada és una estructura complexa en la qual cada node conté indicadors als nodes anteriors i següents. La gestió d’aquests enllaços de vegades és difícil i pot provocar el desglossament del codi si no es gestiona correctament.
En general, les operacions d'una llista doblement enllaçada són més eficients, ja que podem estalviar temps per recórrer la llista, ja que obtenim tant els indicadors anterior com el següent.
La llista circular doblement enllaçada és més complexa i forma un patró circular amb el punter anterior del primer node que apunta al darrer node i el següent punter del darrer node que apunta al primer node. En aquest cas, també, les operacions són eficients.
Amb això, hem acabat amb la llista enllaçada a Java. Estigueu atents a molts més tutorials sobre tècniques de cerca i classificació a Java.
=> Visiteu aquí la sèrie exclusiva de cursos de formació de Java.
Lectura recomanada
- Estructura de dades de llistes doblement enllaçades en C ++ amb il·lustració
- Algorisme de cerca binària a Java: implementació i exemples
- Llista Java: Com crear, inicialitzar i utilitzar una llista a Java
- Interfície Java i tutoria de classes abstractes amb exemples
- Mètodes de llista de Java: ordena llista, conté, afegeix llista, elimina llista
- Classificació per inserció a Java: algorisme i exemples d'ordenació per inserció
- Tutorial JAVA per a principiants: més de 100 tutorials pràctics de vídeo Java
- Bubble Sort In Java - Algoritmes d'ordenació de Java i exemples de codi