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.
O que você aprenderá:
Lista duplamente vinculada em Java
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:
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.
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.
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
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.
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
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.
Leitura recomendada
- Estrutura de dados de lista duplamente vinculada em C ++ com ilustração
- Algoritmo de pesquisa binária em Java - implementação e exemplos
- Lista Java - Como criar, inicializar e usar a lista em Java
- Interface Java e tutorial de classe abstrata com exemplos
- Métodos de lista Java - Classificar lista, contém, adicionar lista, remover lista
- Insertion Sort In Java - Insertion Sort Algorithm & Exemplos
- Tutorial JAVA para iniciantes: mais de 100 tutoriais práticos em vídeo Java
- Bubble Sort In Java - Algoritmos de classificação Java e exemplos de código