Lista duplamente vinculada em Java

doubly linked list java implementation code examples

Este tutorial explica a lista duplamente vinculada em Java junto com a implementação de lista dupla vinculada, código Java circular duplamente vinculado e exemplos:

A lista vinculada é uma representação sequencial dos elementos. Cada elemento da lista vinculada é chamado de ‘Nó’. Um tipo de lista vinculada é denominado “Lista vinculada individualmente”.

Neste, cada nó contém uma parte de dados que armazena os dados reais e uma segunda parte que armazena o ponteiro para o próximo nó na lista. Já aprendemos os detalhes da lista vinculada individualmente em nosso tutorial anterior.

=> Verifique TODOS os tutoriais Java aqui.

Lista duplamente vinculada em Java

O que você aprenderá:

Lista duplamente vinculada em Java
Lista circular duplamente vinculada em Java
- perguntas frequentes
Conclusão
- Leitura recomendada

Uma lista vinculada possui outra variação chamada “lista duplamente vinculada”. Uma lista duplamente vinculada possui um ponteiro adicional conhecido como o ponteiro anterior em seu nó, além da parte de dados, e o próximo ponteiro como na lista vinculada individualmente.

Um nó na lista duplamente vinculada tem a seguinte aparência:

nó na lista duplamente ligada

onde posso assistir animes grátis online

Aqui, “Prev” e “Next” são ponteiros para os elementos anteriores e seguintes do nó, respectivamente. Os 'Dados' são o elemento real que é armazenado no nó.

A figura a seguir mostra uma lista duplamente vinculada.

lista duplamente ligada

O diagrama acima mostra a lista duplamente vinculada. Existem quatro nós nesta lista. Como você pode ver, o ponteiro anterior do primeiro nó e o próximo ponteiro do último nó são definidos como nulos. O ponteiro anterior definido como nulo indica que este é o primeiro nó na lista duplamente vinculada, enquanto o próximo ponteiro definido como nulo indica que o nó é o último nó.

Vantagens

Como cada nó tem ponteiros apontando para o nó anterior e o próximo, a lista duplamente vinculada pode ser percorrida facilmente na direção para frente e para trás
Você pode adicionar rapidamente o novo nó apenas alterando os ponteiros.
Da mesma forma, para a operação de exclusão, uma vez que temos os ponteiros anteriores e também os próximos, a exclusão é mais fácil e não precisamos percorrer toda a lista para encontrar o nó anterior como no caso da lista unida individualmente.

Desvantagens

Uma vez que há um ponteiro extra na lista duplamente vinculada, ou seja, o ponteiro anterior, é necessário espaço de memória adicional para armazenar este ponteiro junto com o próximo ponteiro e item de dados.
Todas as operações como adição, exclusão, etc. requerem que os ponteiros anterior e seguinte sejam manipulados, impondo sobrecarga operacional.

Implementação em Java

A implementação de lista duplamente vinculada em Java compreende a criação de uma classe de lista duplamente vinculada, a classe de nó e adição de nós à lista duplamente vinculada

A adição de novos nós geralmente é feita no final da lista. O diagrama abaixo mostra a adição do novo nó no final da lista duplamente vinculada.

Implementação de lista duplamente vinculada em Java

Conforme mostrado no diagrama acima, para adicionar um novo nó no final da lista, o próximo ponteiro do último nó agora aponta para o novo nó em vez de nulo. O ponteiro anterior do novo nó aponta para o último nó. Além disso, o próximo ponteiro do novo nó aponta para nulo, tornando-o um novo último nó.

O programa a seguir mostra a implementação Java de uma lista duplamente vinculada com a adição de novos nós no final da lista.

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

Resultado:

Nós da lista duplamente vinculada:
10 20 30 40 50

Saída - adição de novos nós

Além de adicionar um novo nó no final da lista, você também pode adicionar um novo nó no início da lista ou no meio da lista. Deixamos essa implementação para o leitor para que ele possa entender melhor as operações.

Lista circular duplamente vinculada em Java

Uma lista circular duplamente ligada é uma das estruturas complexas. Nesta lista, o último nó da lista duplamente ligada contém o endereço do primeiro nó e o primeiro nó contém o endereço do último nó. Portanto, em uma lista circular duplamente vinculada, há um ciclo e nenhum dos ponteiros de nó é definido como nulo.

O diagrama a seguir mostra a lista circular duplamente vinculada.

lista circular duplamente ligada

Conforme mostrado no diagrama acima, o próximo ponteiro do último nó aponta para o primeiro nó. O ponteiro anterior do primeiro nó aponta para o último nó.

As listas circulares duplamente vinculadas têm amplas aplicações na indústria de software. Um desses aplicativos é o aplicativo musical que possui uma lista de reprodução. Na lista de reprodução, quando você termina de tocar todas as músicas, no final da última música, você volta para a primeira música automaticamente. Isso é feito usando listas circulares.

Vantagens de uma lista dupla circular:

A lista circular duplamente ligada pode ser percorrida de ponta a ponta ou de ponta a ponta.
Ir da cabeça à cauda ou cauda a cabeça é eficiente e leva apenas um tempo constante O (1).
Ele pode ser usado para implementar estruturas de dados avançadas, incluindo heap de Fibonacci.

Desvantagens:

Como cada nó precisa liberar espaço para o ponteiro anterior, é necessária memória extra.
Precisamos lidar com muitos ponteiros ao executar operações em uma lista circular duplamente vinculada. Se os ponteiros não forem tratados corretamente, a implementação pode falhar.

O programa Java abaixo mostra a implementação da lista duplamente vinculada 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(); } }

Resultado:

Lista circular duplamente vinculada: 40 50 60 70 80
Lista circular duplamente vinculada retrocedida:
80 70 60 50 40

saída - lista circular duplamente vinculada

No programa acima, adicionamos o nó no final da lista. Como a lista é circular, quando o novo nó for adicionado, o próximo ponteiro do novo nó apontará para o primeiro nó e o ponteiro anterior do primeiro nó apontará para o novo nó.

Da mesma forma, o ponteiro anterior do novo nó apontará para o último nó atual, que agora se tornará o segundo último nó. Deixamos a implementação de adicionar um novo nó no início da lista e entre os nós para os leitores.

perguntas frequentes

P # 1) A lista duplamente vinculada pode ser circular?

Responda: sim. É uma estrutura de dados mais complexa. Em uma lista circular duplamente ligada, o ponteiro anterior do primeiro nó contém o endereço do último nó e o próximo ponteiro do último nó contém o endereço do primeiro nó.

P # 2) Como você cria uma lista duplamente ligada circular?

como extrair arquivos 7z no mac

Responda: Você pode criar uma classe para uma lista vinculada duplamente circular. Dentro desta classe, haverá uma classe estática para representar o nó. Cada nó conterá dois ponteiros - anterior e próximo e um item de dados. Então você pode ter operações para adicionar nós à lista e percorrer a lista.

P # 3) A lista duplamente vinculada é linear ou circular?

Responda: A lista duplamente vinculada é uma estrutura linear, mas uma lista circular duplamente vinculada que tem sua cauda apontada para a cabeça e a cabeça apontada para a cauda. Portanto, é uma lista circular.

P # 4) Qual é a diferença entre a lista duplamente vinculada e a lista circular vinculada?

Responda: Uma lista duplamente vinculada possui nós que mantêm informações sobre seus nós anteriores e também os próximos, usando os ponteiros anterior e seguinte, respectivamente. Além disso, o ponteiro anterior do primeiro nó e o próximo ponteiro do último nó são definidos como nulos na lista duplamente vinculada.

Na lista ligada circular, não há nós iniciais ou finais e os nós formam um ciclo. Além disso, nenhum dos ponteiros é definido como nulo na lista ligada circular.

P # 5) Quais são as vantagens de uma lista duplamente vinculada?

Responda: As vantagens da lista duplamente vinculada são:

Ele pode ser percorrido tanto para frente quanto para trás.
A operação de inserção é mais fácil, pois não precisamos percorrer toda a lista para encontrar o elemento anterior.
A exclusão é eficiente, pois sabemos que os nós anteriores e seguintes e a manipulação é mais fácil.

Conclusão

Neste tutorial, discutimos a lista duplamente vinculada em Java em detalhes. Uma lista duplamente vinculada é uma estrutura complexa em que cada nó contém ponteiros para seus nós anteriores e também para os próximos. O gerenciamento desses links às vezes é difícil e pode levar à quebra do código se não for tratado adequadamente.

No geral, as operações de uma lista duplamente vinculada são mais eficientes, pois podemos economizar tempo para percorrer a lista, pois temos os ponteiros anterior e seguinte.

A lista circular duplamente ligada é mais complexa e eles formam um padrão circular com o ponteiro anterior do primeiro nó apontando para o último nó e o próximo ponteiro do último nó apontando para o primeiro nó. Nesse caso, também, as operações são eficientes.

Com isso, terminamos com a lista vinculada em Java. Fique ligado em muitos outros tutoriais sobre técnicas de pesquisa e classificação em Java.

=> Visite aqui a série exclusiva de tutoriais de treinamento em Java.

Lista duplamente vinculada em Java - exemplos de implementação e código