linked list java linked list implementation java examples
Este tutorial explica o que é uma estrutura de dados de lista vinculada em Java e como criar, inicializar, implementar, percorrer, reverter e classificar uma lista vinculada em Java:
Em Java, um LinkedList é uma estrutura de dados que armazena elementos em um local não contíguo. É uma estrutura de dados linear.
Cada item de dados é chamado de 'Nó' e cada nó tem uma parte de dados e uma parte de endereço. A parte do endereço armazena o link para o próximo nó na LinkedList.
=> Visite aqui para ver a série de treinamento Java para todos.
O que você aprenderá:
- LinkedList em Java
- Classe Java LinkedList
- Como criar uma lista vinculada em Java
- Implementação de lista vinculada em Java
- Percorrer / Imprimir lista vinculada em Java
- Métodos LinkedList
- Lista vinculada reversa em Java
- Classificar uma lista vinculada em Java
- Remover Duplicados
- Lista vinculada circular em Java
- Java 8 LinkedList
- perguntas frequentes
- Conclusão
LinkedList em Java
A seguir está o Layout geral de LinkedList:
Conforme mostrado na representação acima de LinkedList, cada item em LinkedList é o “Node”. Cada nó tem duas partes, a primeira parte armazena os dados e a segunda parte tem uma referência ou ponteiro ou endereço do próximo nó na LinkedList.
alternativa gratuita para livros rápidos para pequenas empresas
Esse arranjo é necessário porque os dados em LinkedList são armazenados em locais não contíguos, ao contrário de Arrays.
O “Head” de LinkedList é um ponteiro que contém o endereço do primeiro elemento em LinkedList. O último nó em LinkedList é a cauda. Conforme mostrado na figura acima, a parte do endereço do último nó na LinkedList é definida como ‘Nulo’ indicando o final da LinkedList.
O diagrama acima representa um “ Lista vinculada individualmente ”Que armazena o endereço apenas do próximo nó na LinkedList.
Existe outra versão conhecida como “ Lista duplamente vinculada ”Cujo cada nó tem três partes:
- Endereço ou referência ou ponteiro para o elemento anterior na LinkedList.
- Parte de dados
- Endereço ou referência ou ponteiro para o próximo elemento em LinkedList.
O endereço anterior do primeiro elemento em LinkedList será definido como Null, enquanto o próximo ponteiro do último elemento em LinkedList será definido como Null.
Representação de lista duplamente vinculada:
Conforme mostrado na representação acima, cada nó na lista duplamente vinculada tem ponteiros para o nó anterior e o próximo (assim representado sem setas). O ponteiro anterior do primeiro nó aponta para nulo enquanto o próximo ponteiro do último nó aponta para nulo.
Neste tutorial LinkedList, lidaremos principalmente com a lista vinculada individualmente. Discutiremos a lista duplamente vinculada em nosso próximo tutorial.
Classe Java LinkedList
Em Java, a lista vinculada é implementada pelo “ LinkedList ' aula. Esta classe pertence ao “ java.util ' pacote. A classe LinkedList implementa as interfaces List e Deque e herda a classe AbstractList.
A seguir está a hierarquia de classes da classe LinkedList.
O diagrama acima mostra a hierarquia da classe LinkedList. Conforme mostrado, a classe LinkedList implementa as interfaces List e Deque.
Como já mencionado, a classe LinkedList é uma parte do “ java.util ' pacote. Portanto, você deve ser capaz de usar a classe LinkedList em seu programa, incluindo uma das seguintes instruções em seu programa.
import java.util.*;
Ou
import java.util.LinkedList;
Portanto, com base na hierarquia acima, uma definição típica da classe LinkedList é a seguinte:
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable
Listados abaixo estão algumas das características da classe LinkedList que você deve se lembrar:
- Esta classe não está sincronizada.
- Ele permite valores duplicados.
- Retém o pedido de inserção.
- Como os elementos não precisam ser deslocados durante o movimento, a manipulação dos elementos nele é mais rápida.
- Esta classe pode ser usada para implementar uma pilha, fila e lista.
Como criar uma lista vinculada em Java
Antes de prosseguirmos para a criação de uma lista vinculada em Java, vamos primeiro discutir um nó de lista vinculada em Java.
Como já discutido, uma lista vinculada consiste em nós. Portanto, em Java, podemos representar uma LinkedList como uma classe com seu Node como uma classe separada. Portanto, essa classe terá uma referência ao tipo Node.
Isso é mostrado abaixo:
class LinkedList { Node head; // list head //node - linkedlist class Node { int data; Node next; Node(int d) { data = d; } //constructor to create a new node } }
Para criar um objeto do tipo LinkedList, existem dois construtores principais, como segue:
# 1) LinkedList ()
A sintaxe geral para este construtor é:
LinkedList linkedList = new LinkedList();
A instrução acima cria uma LinkedList vazia.
Por exemplo,
LinkedList l_list = new LinkedList();
Isso criará uma lista vinculada vazia chamada l_list.
# 2) LinkedList (coleção c)
A sintaxe geral é:
LinkedList linkedList = new LinkedList (Collection c);
A instrução acima cria uma LinkedList com elementos da coleção c como seus elementos iniciais.
Como outras estruturas de dados de lista que já vimos, a lista vinculada também pode ser inicializada usando o método add, o método Arrays.asList () ou usando o construtor com a coleção como um argumento.
Implementação de lista vinculada em Java
Abaixo está um exemplo simples de uma estrutura de dados LinkedList em Java. Neste exemplo de implementação, usaremos o método add e o método asList para inicializar os objetos LinkedList.
import java.util.*; public class Main{ public static void main(String[] args) { //create a LinkedList object and initialize it with Array elements converted to list LinkedList intList = new LinkedList<>(Arrays.asList(10,20,30,40,50)); //print the LinkedList just created System.out.println('Contents of first LinkedList: ' + intList); //create an empty list LinkedList colorsList = new LinkedList<>(); //add elements to the linkedList using add method. colorsList.add('Red'); colorsList.add('Green'); colorsList.add('Blue'); colorsList.add('Cyan'); colorsList.add('Magenta'); // print the LinkedList System.out.println('
Contents of second LinkedList: ' + colorsList); } }
Resultado:
Conteúdo da primeira LinkedList: [10, 20, 30, 40, 50]
Conteúdo da segunda LinkedList: [Vermelho, Verde, Azul, Ciano, Magenta]
O programa acima mostra a criação e inicialização do LinkedList. Primeiro, criamos um LinkedList do tipo Integer e fornecemos um array de Integers convertidos em lista usando o método asList como valores iniciais para LinkedList.
Em seguida, criamos uma LinkedList vazia do tipo String e, em seguida, usando o método add, adicionamos valores à LinkedList.
Finalmente, exibimos ambos os objetos LinkedList como uma string.
Percorrer / Imprimir lista vinculada em Java
Para imprimir o conteúdo ou realizar qualquer operação nos elementos de LinkedList, você precisa percorrer seus elementos. Já vimos esses métodos em nossos tutoriais anteriores. Nesta seção, discutiremos os exemplos de cada um com relação a LinkedList.
Usando o loop for
import java.util.LinkedList; class Main { public static void main(String[] args) { // Create a LinkedList and initialize it LinkedList colorList = new LinkedList<>(); colorList.add('Red'); colorList.add('Green'); colorList.add('Blue'); // Using for loop,print the contents of the LinkedList System.out.println('LinkedList elements using for loop:'); for(int i=0; i Resultado:
Elementos LinkedList usando loop for:
Vermelho Verde Azul
Usando forEach Loop
import java.util.LinkedList; class Main { public static void main(String[] args) { // Create a LinkedList and initialize it LinkedList colorList = new LinkedList<>(); colorList.add('Red'); colorList.add('Green'); colorList.add('Blue'); // Using forEach loop,print the contents of the LinkedList System.out.println('LinkedList elements using forEach loop:'); for(String color:colorList) { System.out.print(color + ' '); } } }
Resultado:
Elementos LinkedList usando loop forEach:
Vermelho Verde Azul
Usando o Iterator
import java.util.*; public class Main{ public static void main(String args[]){ //declare a LinkedList object LinkedList l_list=new LinkedList(); //Add elements to LinkedList l_list.add('Red'); l_list.add('Green'); l_list.add('Blue'); l_list.add('Yellow'); //declare an iterator for the LinkedList Iterator itr=l_list.iterator(); System.out.println('The contents of Linked List:'); //Iterate through the LinkedList using Iterator and print its elements while(itr.hasNext()){ System.out.print(itr.next() + ' '); } } }
Resultado:
O conteúdo da lista vinculada:
Vermelho Verde Azul Amarelo
teste de automação perguntas e respostas da entrevista pdf
Métodos LinkedList
A classe LinkedList fornece API que suporta vários métodos para manipular a lista Linked. Tabularizamos os métodos na API LinkedList abaixo.
Discutiremos as principais operações / métodos na seção seguinte.
Método Protótipo Descrição Claro void clear () Exclui todos os elementos da lista. Adicionar adição booleana (E e) Adicione um elemento especificado ao LinkedList void add (int índice, elemento E) Adicionar elemento no índice fornecido em LinkedList AddAll boolean addAll (coleção c) Adiciona os elementos de determinada coleção c no final de LinkedList. boolean addAll (int index, Collection c) Adiciona os elementos de determinada coleção c no índice especificado na LinkedList addFirst void addFirst (E e) Adicione o elemento fornecido como o primeiro elemento a LinkedList. addLast void addLast (E e) Anexe o elemento fornecido no final da lista. Clone Clone de objeto () Faz uma cópia superficial de LinkedList Contém Boolean contém (objeto o) Verifica se a lista contém elementos especificados; se sim retorna verdadeiro. descendingIterator Iterator descendingIterator () Retorna um iterador de ordem reversa para LinkedList. Elemento Elemento E () Retorna o elemento no topo da lista. Obter E get (índice interno) Obtém o elemento no índice especificado. getFirst E getFirst () Recupera o primeiro elemento em LinkedList. Obtenha o último E getLast () Recupera o último elemento de LinkedList. índice de Int indexOf (Object o) Encontre o índice da primeira ocorrência dos elementos fornecidos na lista e retorne o índice. -1 se o elemento não for encontrado. lastIndexOf Int lastIndexOf (Object o) Retorna a posição da última ocorrência do elemento fornecido na LinkedList; -1 se o elemento fornecido não estiver presente listIterator ListIterator listIterator (índice interno) Retorna o listIterator do índice especificado na lista vinculada. Oferta oferta booleana (E e) Adiciona o elemento fornecido como o último elemento (cauda) na LinkedList. offerFirst Oferta booleanaFirst (E e) Adiciona o elemento fornecido como o primeiro elemento em LinkedList. offerLast Oferta booleanaLast (E e) Adicione o elemento e fornecido no final da LinkedList. Olhadinha E peek () Retorna o topo da lista sem removê-lo. peekFirst E peekFirst () Retorna o primeiro elemento da lista. retorna nulo se a lista estiver vazia. peekLast E peekLast () Retorna o último elemento ou nulo se a lista estiver vazia. Não exclui o elemento. Enquete E poll () Retorna o cabeçalho de LinkedList e também o remove. pollFirst E pollFirst () Retorna e exclui o primeiro elemento da lista; retorna nulo se a lista estiver vazia. pollLast E pollLast () Retorna e exclui o último elemento da lista; retorna nulo se a lista estiver vazia. Pop E pop () Retira o elemento da representação da pilha de LinkedList. Empurre Anular push (E e) Empurra ou insere um elemento na representação da pilha de LinkedList. Retirar E remove () Remove e retorna o cabeçalho de LinkedList. E remove (índice interno) Exclui o elemento no índice fornecido de LinkedList. boolean remove (objeto o) Exclui a primeira ocorrência do elemento fornecido de LinkedList. removeFirst E removeFirst () Retorna e exclui o primeiro elemento da lista. removeFirstOccurence boolean removeFirstOccurrence (Object o) Exclui a primeira ocorrência do elemento fornecido da lista quando a lista está sendo percorrida de ponta a ponta. removeLast E removeLast () Retorna o último elemento de LinkedList e também o exclui. removeLastOccurence boolean removeLastOccurrence (Object o) Remove a última ocorrência de um determinado elemento da LinkedList quando percorrido do início ao fim Definir E conjunto (índice interno, elemento E) Define o elemento fornecido no índice fornecido. Substitui o elemento atual por novo. Tamanho Tamanho interno () Retorna o tamanho ou número de elementos na LinkedList toArray Object [] toArray () Converte o LinkedList em um array contendo todos os elementos da lista na seqüência apropriada T [] toArray (T [] a) Converte LinkedList em uma matriz com tipo de tempo de execução igual ao argumento a.
O programa Java abaixo demonstra os vários métodos listados acima.
import java.util.*; public class Main { public static void main(String args[]) { //create a linked list LinkedList l_list = new LinkedList(); // Add elements to linkedList using various add methods l_list.add('B'); l_list.add('C'); l_list.addLast('G'); l_list.addFirst('A'); l_list.add(3, 'D'); l_list.add('E'); l_list.add('F'); //print the linkedList System.out.println('Linked list : ' + l_list); //Create and initialize an ArrayList ArrayList aList = new ArrayList<>(); aList.add('H'); aList.add('I'); //add the ArrayList to linkedList using addAll method l_list.addAll(aList); //print the linkedList System.out.println('Linked list after adding ArrayList contents: ' + l_list); // use various remove methods to remove elements from linkedList l_list.remove('B'); l_list.remove(3); l_list.removeFirst(); l_list.removeLast(); //print the altered list System.out.println('Linked list after deletion: ' + l_list); // use contains method to check for an element in the linkedList boolean ret_value = l_list.contains('G'); //print the results of contains method if(ret_value) System.out.println('List contains the element 'G' '); else System.out.println('List doesn't contain the element 'G''); // use size methods to return Number of elements in the linked list int size = l_list.size(); System.out.println('Size of linked list = ' + size); // Get and set elements from linked list Object element = l_list.get(3); System.out.println('Element returned by get() : ' + element); l_list.set(3, 'J'); System.out.println('Linked list after change : ' + l_list); //convert linkedList to Array using toArray methods String [] list_array = l_list.toArray(new String[l_list.size()]); System.out.println('Array obtained from linked List:' + Arrays.toString(list_array)); } }
Resultado:
Lista vinculada: [A, B, C, D, G, E, F]
Lista vinculada após adicionar conteúdo de ArrayList: [A, B, C, D, G, E, F, H, I]
Lista vinculada após exclusão: [C, D, E, F, H]
A lista não contém o elemento ‘G’
Tamanho da lista ligada = 5
Elemento retornado por get (): F
Lista vinculada após alteração: [C, D, E, J, H]
Matriz obtida da Lista vinculada: [C, D, E, J, H]
O programa acima demonstra vários métodos da classe LinkedList. Primeiro, declaramos uma LinkedList do tipo String. Em seguida, usamos várias versões do método add, como add, andFirst, addLast, addAll, etc. para preencher a LinkedList com valores.
Aqui, podemos adicionar o elemento diretamente no final da lista ou adicionar o elemento em uma posição especificada na lista.
Também usamos o método addFirst para adicionar um elemento no início da lista e addLast para adicionar um elemento no final da lista. Em seguida, realizamos operações de remoção na LinkedList, como remove, removeFirst, removeLast, etc.
Para o método remove, podemos especificar o elemento a ser removido ou podemos especificar o índice ou a posição na LinkedList na qual o elemento deve ser removido. Os métodos removeFirst e removeLast removem o primeiro e o último elemento da lista, respectivamente.
Em seguida, procuramos na lista um elemento específico usando o método contains. Em seguida, usamos o método size () para recuperar o tamanho ou comprimento de LinkedList. Em seguida, usamos os métodos get / set para recuperar o valor em um índice específico na lista e, a seguir, substituir um valor em uma posição especificada na lista.
Por fim, convertemos LinkedList em Array usando o método toArray.
Lista vinculada reversa em Java
Para reverter uma lista vinculada em Java, usamos o método “descendingIterator ()” que retorna um iterador reverso para a lista. Podemos então usar esse iterador para percorrer a lista e exibir os elementos.
O programa a seguir inverte a lista vinculada usando o método descendingIterator ().
import java.util.*; public class Main{ public static void main(String args[]){ //create a LinkedList object LinkedList l_list=new LinkedList(); l_list.add('Pune'); l_list.add('Mumbai'); l_list.add('Nagpur'); System.out.println('Linked List : ' + l_list); System.out.println('Linked List in reverse order:'); //use descendingIterator method to get a reverse iterator Iterator iter=l_list.descendingIterator(); //traverse the list using iterator and print the elements. while(iter.hasNext()) { System.out.print(iter.next() + ' '); } } }
Resultado:
Lista vinculada: [Pune, Mumbai, Nagpur]
Lista vinculada na ordem inversa:
Nagpur Mumbai Pune
No programa acima, declaramos uma lista vinculada e a imprimimos. Em seguida, obtemos um iterador reverso e percorremos a lista usando-o e exibimos cada elemento. A saída mostra o conteúdo da Lista vinculada, primeiro na ordem em que os elementos são adicionados e, em seguida, a saída mostra o conteúdo na ordem inversa.
Classificar uma lista vinculada em Java
Os objetos da classe LinkedList podem ser classificados usando o método Collections.sort (). Este método fornece duas versões com ou sem o uso de um comparador. Quando o método Collections.sort () é chamado sem um comparador, a coleção é classificada na ordem natural.
Quando o comparador é usado com este método, podemos definir nossos próprios critérios de classificação substituindo o método compareTo.
O programa Java a seguir classifica uma LinkedList usando Collections.sort (). Aqui, classificamos as matrizes usando a ordenação natural e também usando um comparador.
import java.util.*; public class Main{ public static void main(String args[]) { // create and initialize the LinkedList object LinkedList l_list = new LinkedList<>(); l_list.add('Jan'); l_list.add('Feb'); l_list.add('Mar'); l_list.add('Apr'); l_list.add('May'); l_list.add('Jun'); //print original unsorted linkedlist System.out.println('Original LinkedList (unsorted): ' + l_list); // sort LinkedList with Collecitons.sort() method in natural order Collections.sort(l_list); System.out.println('
LinkedList (sorted in natural order): ' + l_list); // sort LinkedList using Collection.sort() and Comparator in Java Collections.sort(l_list, new Comparator() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } } ); System.out.println('LinkedList (sorted using Comparator): ' + l_list); } }
Resultado:
LinkedList original (não classificado): [janeiro, fevereiro, março, abril, maio, junho]
LinkedList (classificado em ordem natural): [abril, fevereiro, janeiro, junho, março, maio]
LinkedList (classificado usando Comparator): [abril, fevereiro, janeiro, junho, março, maio]
Remover Duplicados
Para remover duplicatas, você precisa percorrer cada nó e compará-lo com o próximo nó. Se ambos os nós forem iguais, pulamos um nó e passamos para o próximo.
Dessa forma, após percorrer cada um dos nós e nos livrar dos nós duplicados, obteremos a lista resultante que está sem nenhum elemento duplicado.
Dada a seguir é um programa Java para remover duplicatas.
class LinkedList_Duplicate { //A class to represent node in linkedlist class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } //Initially the head and tail of the linked list set to null public Node head = null; public Node tail = null; //add a new node to the linkedlist public void addNode(int data) { //Create new node Node newNode = new Node(data); //If list is empty set head and tail to new node if(head == null) { head = newNode; tail = newNode; } else { // add newNode after the tail tail.next = newNode; //newNode is now the tail or last element tail = newNode; } } //scans the linkedlist and removes duplicate nodes public void removeDuplicateNodes() { //Head is the current node Node current = head, index = null, temp = null; //head = null means list is empty if(head == null) { return; } //traverse through the list else { while(current != null){ //temp node points to previous node to index. temp = current; //Index will point to node next to current index = current.next; while(index != null) { //Check if current node's data is equal to index node's data if(current.data == index.data) { //since node is duplicate skip index and point to next node temp.next = index.next; } else { //Temp will point to previous node of index. temp = index; } index = index.next; } current = current.next; } } } //print the linked list public void print() { //Node current will point to head Node current = head; if(head == null) { System.out.println('List is empty'); return; } while(current != null) { //Print each node by incrementing pointer System.out.print(current.data + ' '); current = current.next; } System.out.println(); } }class Main{ public static void main(String[] args) { LinkedList_Duplicate l_List = new LinkedList_Duplicate(); //Add data to the list l_List.addNode(1); l_List.addNode(1); l_List.addNode(2); l_List.addNode(3); l_List.addNode(5); l_List.addNode(2); l_List.addNode(1); l_List.addNode(1); //print the original list System.out.println('Original Linkedlist: '); l_List.print(); //Removes duplicate nodes l_List.removeDuplicateNodes(); //print the altered list without duplicates System.out.println('LinkedList after removing duplicates: '); l_List.print(); } }
Resultado:
Os métodos python usados para adicionar itens a uma lista ou excluí-los de uma lista são chamados
Lista vinculada original:
1 1 2 3 5 2 1 1
LinkedList após remover duplicatas:
1 2 3 5
No programa acima, temos uma classe de lista vinculada criada para remover duplicatas. Também temos uma classe para definir cada nó. Em outras palavras, os nós da lista são os objetos desse nó de classe. Temos um método para adicionar o nó a uma lista vinculada.
Em seguida, no método removeDuplicate, percorremos cada nó na lista encadeada começando pelo cabeçalho e comparamos cada nó subsequente para a duplicata. Se uma duplicata for encontrada, pulamos esse nó e prosseguimos para o próximo nó.
Desta forma, o ist é construído pulando os nós duplicados e a lista alterada é impressa usando o método print ().
Lista vinculada circular em Java
Uma lista ligada circular é uma lista que tem sua cauda ou último nó conectado de volta à cabeça ou ao primeiro nó.
O diagrama abaixo mostra a lista vinculada circular em Java.
Conforme mostrado no diagrama acima, a parte do endereço do último nó ou cauda da lista vinculada não é definida como nula. Em vez disso, ele aponta de volta para o primeiro nó ou cabeçalho da lista, formando assim uma lista ligada circular.
O programa a seguir implementa uma lista ligada circular em que temos que manipular nós individuais da lista ligada.
class CircularLinkedList { //Node definition for circular linked list public class Node{ int data; Node next; public Node(int data) { this.data = data; } } //Initially head and tail pointers point to null public Node head = null; public Node tail = null; //add new node to the circular linked list public void add(int data){ //Create new node Node newNode = new Node(data); //check if list is empty if(head == null) { //head and tail point to same node if list is empty head = newNode; tail = newNode; newNode.next = head; } else { //tail points to new node if list is not empty tail.next = newNode; //New node becomes new tail. tail = newNode; //tail points back to head tail.next = head; } } //Display the nodes in circular linked list public void displayList() { Node current = head; if(head == null) { System.out.println('The List is empty'); } else { System.out.println('Circular linked list nodes: '); do{ //Print each node of the linked list System.out.print(current.data + ' '); current = current.next; }while(current != head); System.out.println(); } } } class Main{ public static void main(String[] args) { //create a CircularLinkedList object CircularLinkedList c_list = new CircularLinkedList(); //Add data to the list c_list.add(10); c_list.add(20); c_list.add(30); c_list.add(40); //Display the nodes in circular linked list c_list.displayList(); } }
Resultado:
Nós circulares da lista ligada:
10 20 30 40
Java 8 LinkedList
Embora não haja mais recursos adicionados especificamente à classe LinkedList no Java 8, ele ainda introduziu fluxos para manipular dados.
O programa abaixo mostra o uso do fluxo Java 8 para exibir LinkedList.
import java.util.LinkedList; import java.util.List; public class Main { public static void main(String[] args) { //create a LinkedList and initialize it to values List colorsList = new LinkedList<>(); colorsList.add('Red'); colorsList.add('Green'); colorsList.add('Blue'); colorsList.add('Cyan'); colorsList.add('Magenta'); //convert List to stream & print it System.out.println('The contents of LinkedList:'); colorsList.stream().forEach(System.out::println); } }
Resultado:
O conteúdo de LinkedList:
Internet
Verde
Azul
Ciano
Magenta
perguntas frequentes
P # 1) Quando a lista vinculada é usada em Java?
Responda: Como é mais rápido do que coleções como ArrayList em operações de modificação, deve ser usado em aplicativos que requerem operações de adição / exclusão frequentes. Para aplicativos que possuem principalmente dados somente leitura, ArrayList ou coleções semelhantes podem ser usadas.
Q # 2) O que é ListNode?
Responda: Um ListNode é uma classe básica associada a uma lista vinculada em Java e representa informações associadas a um único elemento ou nó. Cada ListNode consiste em dados e um ponteiro ou referência para o próximo elemento.
Q # 3) A lista vinculada permite valores nulos?
Responda: Sim, a lista vinculada permite qualquer número de valores nulos.
Q # 4) Quais são as vantagens de uma lista vinculada?
Resposta: Algumas das vantagens são:
- Operações de manipulação, como adição e exclusão, são mais rápidas.
- Não há necessidade de pré-alocar memória para uma lista vinculada e, portanto, resulta em uma utilização eficiente da memória.
- Ele fornece tempo de acesso mais rápido e sem sobrecarga adicional para a memória e pode ser expandido em tempo constante.
- É uma estrutura de dados dinâmica
- Aumenta e diminui em tempo de execução, dependendo dos valores adicionados ou excluídos.
Q # 5) Qual é a aplicação da lista vinculada?
Resposta: É usado principalmente nas seguintes aplicações:
- Para implementar a funcionalidade de 'desfazer' em software como MS-Word, Photoshop, etc.
- Para implementar estruturas de dados como pilha e fila.
- Também podemos implementar gráficos usando uma lista vinculada.
- Para hashing de balde, cada balde pode ser implementado como uma lista vinculada.
Q # 6) Quais são as limitações de uma lista vinculada?
Resposta: Algumas das limitações são:
- Com um ponteiro adicional para manter a referência do próximo elemento em cada nó, a memória utilizada é muito mais do que arrays.
- Esta é uma estrutura de dados acessada estritamente sequencialmente, portanto, os nós da lista vinculada devem ser sempre lidos desde o início.
- É difícil retroceder, especialmente nas listas com links simples.
- Como os nós são armazenados em locais não contíguos, o tempo necessário para o acesso pode ser alto.
Conclusão
Neste tutorial, aprendemos a estrutura de dados de lista vinculada básica. Em seguida, mudamos para a classe java.util.LinkedList fornecida em Java. Discutimos essa classe em detalhes, incluindo seus construtores, métodos, etc.
Também discutimos algumas operações especiais relacionadas a listas vinculadas, como classificação, reversão de uma lista, remoção de duplicatas, lista vinculada circular, etc.
Em nosso próximo tutorial, discutiremos recursos específicos da lista duplamente vinculada.
=> Confira o Guia de treinamento Java completo aqui.
Leitura recomendada
- Lista duplamente vinculada em Java - exemplos de implementação e código
- Lista Java - Como criar, inicializar e usar a lista em Java
- Métodos de lista Java - Classificar lista, contém, adicionar lista, remover lista
- Algoritmo de pesquisa binária em Java - implementação e exemplos
- Insertion Sort In Java - Insertion Sort Algorithm & Exemplos
- Interface Java e tutorial de classe abstrata com exemplos
- Estrutura de dados de lista vinculada em C ++ com ilustração
- Lista secreta para matriz e outras coleções em Java