Java LinkedList – LinkedList Em Java

LinkedList do Java é uma implementação das interfaces List e Deque. É uma das classes de implementação de List frequentemente utilizadas. Ela estende AbstractSequentialList e implementa as interfaces List e Deque. É uma coleção ordenada e suporta elementos duplicados. Armazena os elementos na ordem de inserção. Suporta a adição de elementos nulos. Suporta operações baseadas em índice. Se você deseja aprender mais sobre os conceitos básicos de List, por favor, leia este artigo: Lista Java.

Sumário do Artigo

Neste artigo, vamos discutir os seguintes conceitos.

• LinkedList do Java
• Diagrama de Classe da LinkedList do Java
• Métodos da Lista LinkedList do Java
• Métodos da Deque LinkedList do Java
• Exemplo Básico da LinkedList do Java
• Genéricos da LinkedList do Java
• Array Java para LinkedList
• LinkedList do Java para Array
• Casos de Uso em Tempo Real da LinkedList do Java
• Representação Interna da LinkedList do Java
• Como a Inserção Funciona na LinkedList do Java?
• Como a Exclusão Funciona na LinkedList do Java?
• Operações da Deque da LinkedList do Java
• Java SE 8: Da LinkedList do Java para o Stream
• Java SE 9 LinkedList

Java LinkedList

Nesta seção, discutiremos alguns dos pontos importantes sobre Java LinkedList:

• A classe Java LinkedList é um membro do Framework de Coleções do Java.
• É uma implementação das interfaces List e Deque.
• Internamente, é implementada usando a Estrutura de Dados de Lista Duplamente Encadeada.
• Suporta elementos duplicados.
• Armazena ou mantém seus elementos em ordem de inserção.
• Podemos adicionar qualquer número de elementos nulos.
• Não é sincronizada, o que significa que não é Thread safe.
• Podemos criar uma LinkedList sincronizada usando o método Collections.synchronizedList().
• Nas aplicações Java, podemos usá-la como uma Lista, pilha ou fila.
• Não implementa a interface RandomAccess. Portanto, podemos acessar elementos apenas em ordem sequencial. Não suporta o acesso aleatório aos elementos.
• Quando tentamos acessar um elemento de uma LinkedList, a busca por esse elemento começa do início ou do final da LinkedList, dependendo de onde esse elemento está disponível.
• Podemos usar ListIterator para iterar os elementos da LinkedList.
• A partir do Java SE 8 em diante, podemos converter uma LinkedList em um Fluxo e vice-versa.
• O Java SE 9 vai adicionar alguns métodos de fábrica para criar uma LinkedList imutável.

Diagrama de Classe LinkedList em Java

Como sabemos, o Java LinkedList é uma das classes de implementação de List. Também implementa Deque. Como mostrado no diagrama de classe abaixo, não estende diretamente da classe AbstractList. Estende a classe AbstractSequentialList.

Métodos de Lista Java LinkedList

Nesta seção, discutiremos alguns dos métodos úteis e frequentemente usados da Java LinkedList. Os seguintes métodos são herdados da interface List ou Collection:

1. int size(): para obter o número de elementos na lista.
2. boolean isEmpty(): para verificar se a lista está vazia ou não.
3. boolean contains(Object o): Retorna verdadeiro se esta lista contém o elemento especificado.
4. Iterator iterator(): Retorna um iterador sobre os elementos nesta lista na sequência apropriada.
5. Object[] toArray(): Retorna uma matriz contendo todos os elementos nesta lista na sequência apropriada.
6. boolean add(E e): Anexa o elemento especificado ao final desta lista.
7. boolean remove(Object o): Remove a primeira ocorrência do elemento especificado desta lista.
8. boolean retainAll(Collection c): Mantém apenas os elementos nesta lista que estão contidos na coleção especificada.
9. void clear(): Remove todos os elementos da lista.
10. E get(int index): Returns the element at the specified position in the list.
11. E set(int index, E element): Replaces the element at the specified position in the list with the specified element.
12. ListIterator listIterator(): Retorna um iterador de lista sobre os elementos na lista.
13. List subList(int fromIndex, int toIndex): Retorna uma visualização da parte desta lista entre o fromIndex especificado, inclusive, e toIndex, exclusivo. A lista retornada é suportada por esta lista, então as mudanças não estruturais na lista retornada são refletidas nesta lista, e vice-versa.

Métodos Deque da LinkedList em Java

Os seguintes métodos são específicos da classe LinkedList que são herdados da interface Deque:

1. void addFirst(E e): Insere o elemento especificado no início desta lista.
2. void addLast(E e): Insere o elemento especificado no final desta lista.
3. E getFirst(): Retrieves, but does not remove, the first element of this list. This method differs from peekFirst only in that it throws an exception if this list is empty.
4. E getLast(): Retrieves, but does not remove, the last element of this list. This method differs from peekLast only in that it throws an exception if this list is empty.
5. E remvoeFirst(): Removes and returns the first element from this list.
6. E removeLast(): Removes and returns the last element from this list.
7. boolean offerFirst(E e): Insere o elemento especificado na frente desta lista.
8. boolean offerLast(E e): Insere o elemento especificado no final desta lista.
9. E pollFirst(): Retrieves and removes the first element of this list, or returns null if this list is empty.
10. E pollLast(): Retrieves and removes the last element of this list, or returns null if this list is empty.
11. E peekFirst(): Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
12. E peekLast(): Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.

Exemplo Básico de LinkedList em Java

Nesta seção, discutiremos sobre um exemplo básico de LinkedList em Java. Vamos explorar algumas operações mais úteis nas próximas seções. Exemplo:-

import java.util.LinkedList;
import java.util.List;

public class LinkedListDemo 
{
  public static void main(String[] args) 
  {
	List names = new LinkedList();
	names.add("Rams");
	names.add("Posa");
	names.add("Chinni");
        names.add(2011);
			
	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
  }
}

Saída:-

LinkedList content: [Rams, Posa, Chinni, 2011]
LinkedList size: 4

Aqui criamos um objeto LinkedList e adicionamos 4 itens. Como discutimos, o método LinkedList.size() é usado para obter o número de elementos na lista. NOTA:- Sem o uso de Genéricos, LinkedList em Java suporta elementos Heterogêneos. No entanto, não é recomendado usar Coleções sem Genéricos. Vamos explorar as Vantagens e o uso de Genéricos em Java na próxima seção com um exemplo simples.

Genéricos em LinkedList Java

Nesta seção, discutiremos como usar Genéricos com LinkedList em Java. Como sabemos, Genéricos em Java são úteis para escrever programação com Segurança de Tipos e realizar verificações de tipo mais fortes em tempo de compilação. Eles também são úteis para eliminar o overhead de casting. Exemplo:-

import java.util.LinkedList;
import java.util.List;

public class LinkedListGenericsDemo
{
  public static void main(String[] args) 
  {
	List names = new LinkedList<>();
	names.add("Rams");
	names.add("Posa");
	names.add("Chinni");
        // Não podemos adicionar nada além de Strings
        // names.add(2011);
			
	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
  }
}

Saída:-

LinkedList content: [Rams, Posa, Chinni]
LinkedList size: 3

Aqui criamos um objeto LinkedList com Genéricos e adicionamos 3 itens. Quando tentamos adicionar um Número à LinkedList, ele gera um erro de compilação.

Array Java para LinkedList

Nesta seção, vamos explorar como converter um Array Java em um objeto LinkedList. Podemos fazer isso de várias maneiras, no entanto, aqui forneci apenas uma abordagem. Exemplo:-

import java.util.LinkedList;
import java.util.List;

public class JavaArrayToLinkedListDemo 
{
	public static void main(String[] args) 
	{
		Integer[] numbers = {1,2,3,4,5};
		List<Integer> numbersList = new LinkedList<>();
		for(Integer s : numbers){
			numbersList.add(s);
		}
		System.out.println(numbersList);
	}
}

Saída:-

[1, 2, 3, 4, 5]

Java LinkedList para Array

Nesta seção, vamos explorar como converter um LinkedList Java em um Array. Podemos fazer isso de várias maneiras, no entanto, aqui forneci apenas uma abordagem. Exemplo:-

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class LinkedListToJavaArrayDemo 
{
	public static void main(String[] args) 
	{		
		List<Integer> numbersList = new LinkedList<>();
		numbersList.add(1);
		numbersList.add(2);
		numbersList.add(3);
		numbersList.add(4);
		numbersList.add(5);
		Integer[] numbers = new Integer[numbersList.size()];
		
		numbers = numbersList.toArray(numbers);
		System.out.println(Arrays.toString(numbers));

	}
}

Saída:-

[1, 2, 3, 4, 5]

Cenários de Uso em Tempo Real de Java LinkedList

Nesta seção, vamos discutir sobre qual é o melhor e qual é o pior cenário de uso de LinkedList em aplicações Java. Cenário de Uso Melhor:-

• Quando nossa operação frequentemente usada é adicionar ou remover elementos no meio da Lista, LinkedList é a melhor classe para usar.

Por quê? Porque não precisamos fazer mais deslocamentos para adicionar ou remover elementos no meio da lista. Consulte a seção “Como a Inserção Funciona em Java LinkedList?” para entendê-la detalhadamente. Cenário de Uso Pior:-

• Quando a operação frequentemente utilizada é a recuperação de elementos de uma lista, então a LinkedList é a pior escolha.

Por quê? Porque a LinkedList suporta apenas acesso sequencial, NÃO suporta acesso aleatório. Consulte a seção “Como funciona a exclusão em Java LinkedList?” para entender isso detalhadamente. NOTA:- A LinkedList implementa List, Deque, Cloneable e Serializable. Mas não implementa a interface RandomAccess.

Representação Interna da Java LinkedList

Como sabemos, internamente, a Java LinkedList é implementada usando Doubly Linked List. Assim, a Java LinkedList representa seus elementos como nós. Cada nó é dividido em 3 partes, como mostrado abaixo. Aqui, cada nó é usado para um propósito específico.

1. A parte do nó do lado esquerdo é usada para apontar para o nó (ou elemento) anterior na LinkedList.
2. A parte do nó do lado direito é usada para apontar para o próximo nó (ou elemento) na LinkedList.
3. A parte central do nó é usada para armazenar os dados reais.

NOTA:- Na JVM, LinkedList NÃO armazena seus elementos em ordem consecutiva. Ele armazena seus elementos em qualquer espaço disponível e eles são conectados entre si usando as porções de Nós do lado Esquerdo e Direito como mostrado no diagrama abaixo.

Como funciona a inserção no Java LinkedList?

Já vimos como o LinkedList armazena seus elementos como Nós na seção anterior. Nesta seção, discutiremos como funciona a operação de inserção do Java LinkedList internamente.

1. Vamos supor que nosso LinkedList inicial tenha os seguintes dados.
   3. Execute a seguinte operação de inserção neste LinkedList

linkedList.add(2,54);

Aqui estamos tentando realizar a operação de inserção para adicionar um novo elemento com valor “54” no índice 2.5. O LinkedList atualizado parece o seguinte.

Como funciona a exclusão no Java LinkedList?

Já vimos como a LinkedList realiza a operação de inserção internamente na seção anterior. Nesta seção, discutiremos como a operação de exclusão da LinkedList em Java funciona internamente.

1. Vamos supor que nossa LinkedList inicial tenha os seguintes dados.
   3. Realize a seguinte operação de inserção nesta LinkedList

linkedList.remove(3);

Aqui estamos tentando realizar a operação de exclusão para excluir um elemento que está disponível no índice 3.5. A LinkedList atualizada fica assim.

Operações de Deque da LinkedList em Java

Aqui exploraremos como um objeto LinkedList funciona como um Deque. Usamos essas operações para implementar Filas ou Pilhas. Discutiremos como uma Pilha ou Fila funciona em profundidade em minhas próximas postagens. Exemplo:-

import java.util.LinkedList;
import java.util.LinkedList;
import java.util.Deque;

public class LinkedListDequeOperationsDemo 
{
  public static void main(String[] args) 
  {
	Deque names = new LinkedList();
	names.add(2);
	names.addFirst(1);
	names.addLast(3);
	names.addFirst(0);
	names.addLast(4);
			
	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
	names.removeFirst();
	names.removeLast();
	
	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());	
  }
}

Saída:-

LinkedList content: [0, 1, 2, 3, 4]
LinkedList size: 5
LinkedList content: [1, 2, 3]
LinkedList size: 3

Java SE 8: LinkedList Java para Stream

Aqui exploraremos como converter um objeto LinkedList para o conceito de Stream do Java SE 8. Exemplo:-

import java.util.LinkedList;
import java.util.List;

public class LinkedListToStreamDemo 
{
  public static void main(String[] args) 
  {		
	List numbersList = new LinkedList<>();
	numbersList.add(1);
	numbersList.add(2);
	numbersList.add(3);
	numbersList.add(4);
	numbersList.add(5);
		
	//converter Lista para stream
	numbersList.stream().forEach(System.out::println);
  }
}

Saída:-

1
2
3
4
5

Java SE 9 LinkedList

No Java SE 9, a Oracle Corp vai adicionar alguns métodos de utilidade úteis para criar uma Lista Imutável. Se você deseja aprendê-los em profundidade com alguns exemplos úteis, por favor, leia minha postagem em: Java SE 9: Métodos de Fábrica para Lista Imutável Isso resume rapidamente o LinkedList em Java. Espero que esses exemplos de LinkedList em Java ajudem você a começar a programar com LinkedList. Obrigado por ler meus tutoriais. Por favor, deixe um comentário se você gostou dos meus tutoriais ou se tiver algum problema, sugestão ou erro tipográfico.