Neste tutorial, aprenderemos sobre o Java LinkedList em detalhes com a ajuda de exemplos.
A LinkedListclasse da estrutura de coleções Java fornece a funcionalidade da estrutura de dados de lista vinculada (lista duplamente vinculada).
Java Doubly LinkedList
Cada elemento em uma lista vinculada é conhecido como um nó . Consiste em 3 campos:
- Anterior - armazena um endereço do elemento anterior na lista. É
nullpara o primeiro elemento - Próximo - armazena um endereço do próximo elemento na lista. É
nullpara o último elemento - Dados - armazena os dados reais
Criação de um Java LinkedList
Aqui está como podemos criar listas vinculadas em Java:
LinkedList linkedList = new LinkedList();
Aqui, Tipo indica o tipo de uma lista vinculada. Por exemplo,
// create Integer type linked list LinkedList linkedList = new LinkedList(); // create String type linked list LinkedList linkedList = new LinkedList();
Exemplo: Crie LinkedList em Java
import java.util.LinkedList; class Main ( public static void main(String() args)( // create linkedlist LinkedList animals = new LinkedList(); // Add elements to LinkedList animals.add("Dog"); animals.add("Cat"); animals.add("Cow"); System.out.println("LinkedList: " + animals); ) )
Resultado
LinkedList: (cachorro, gato, vaca)
No exemplo acima, criamos LinkedListanimais nomeados.
Aqui, usamos o add()método para adicionar elementos à LinkedList. Aprenderemos mais sobre o add()método posteriormente neste tutorial.
Trabalho de um Java LinkedList
Os elementos nas listas vinculadas não são armazenados em sequência. Em vez disso, eles estão espalhados e conectados por meio de links ( Anterior e Próximo ).
Implementação Java LinkedList
Aqui, temos 3 elementos em uma lista vinculada.
- Dog - é o primeiro elemento que contém null como endereço anterior e o endereço de Cat como próximo endereço
- Cat - é o segundo elemento que contém um endereço de Dog como o endereço anterior e o endereço de Cow como o próximo endereço
- Cow - é o último elemento que contém o endereço de Cat como o endereço anterior e nulo como o próximo elemento
Para saber mais, visite a Estrutura de dados LinkedList.
Métodos de Java LinkedList
LinkedListfornece vários métodos que nos permitem realizar diferentes operações em listas vinculadas. Veremos quatro operadores LinkedList comumente usados neste tutorial:
- Adicionar elementos
- Elementos de acesso
- Elementos de mudança
- Remover elementos
1. Adicionar elementos a uma LinkedList
Podemos usar o add()método para adicionar um elemento (nó) no final da LinkedList. Por exemplo,
import java.util.LinkedList; class Main ( public static void main(String() args)( // create linkedlist LinkedList animals = new LinkedList(); // add() method without the index parameter animals.add("Dog"); animals.add("Cat"); animals.add("Cow"); System.out.println("LinkedList: " + animals); // add() method with the index parameter animals.add(1, "Horse"); System.out.println("Updated LinkedList: " + animals); ) )
Resultado
LinkedList: (cão, gato, vaca) LinkedList atualizado: (cão, cavalo, gato, vaca)
No exemplo acima, criamos uma LinkedList chamada animals. Aqui, usamos o add()método para adicionar elementos aos animais.
Observe a declaração,
animals.add(1, "Horse");
Aqui, usamos o parâmetro de número de índice . É um parâmetro opcional que especifica a posição onde o novo elemento é adicionado.
Para saber mais sobre como adicionar elementos a LinkedList, visite o programa Java para adicionar elementos a LinkedList.
2. Acesse os elementos LinkedList
O get()método da classe LinkedList é usado para acessar um elemento de LinkedList. Por exemplo,
import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList languages = new LinkedList(); // add elements in the linked list languages.add("Python"); languages.add("Java"); languages.add("JavaScript"); System.out.println("LinkedList: " + languages); // get the element from the linked list String str = languages.get(1); System.out.print("Element at index 1: " + str); ) )
Resultado
LinkedList: (Python, Java, JavaScript) Elemento no índice 1: Java
No exemplo acima, usamos o get()método com o parâmetro 1 . Aqui, o método retorna o elemento no índice 1 .
Também podemos acessar elementos de LinkedList usando iterator()o listIterator()método e. Para saber mais, visite o programa Java para acessar elementos de LinkedList.
3. Alterar os elementos de uma LinkedList
O set()método da LinkedListclasse é usado para alterar os elementos da LinkedList. Por exemplo,
import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList languages = new LinkedList(); // add elements in the linked list languages.add("Java"); languages.add("Python"); languages.add("JavaScript"); languages.add("Java"); System.out.println("LinkedList: " + languages); // change elements at index 3 languages.set(3, "Kotlin"); System.out.println("Updated LinkedList: " + languages); ) )
Resultado
LinkedList: (Java, Python, JavaScript, Java) LinkedList atualizada: (Java, Python, JavaScript, Kotlin)
No exemplo acima, criamos linguagens nomeadas LinkedList. Observe a linha,
languages.set(3, "Kotlin");
Aqui, o set()método altera o elemento no índice 3 para Kotlin.
4. Remova o elemento de uma LinkedList
The remove() method of the LinkedList class is used to remove an element from the LinkedList. For example,
import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList languages = new LinkedList(); // add elements in LinkedList languages.add("Java"); languages.add("Python"); languages.add("JavaScript"); languages.add("Kotlin"); System.out.println("LinkedList: " + languages); // remove elements from index 1 String str = languages.remove(1); System.out.println("Removed Element: " + str); System.out.println("Updated LinkedList: " + languages); ) )
Output
LinkedList: (Java, Python, JavaScript, Kotlin) Removed Element: Python New LinkedList: (Java, JavaScript, Kotlin)
Here, the remove() method takes the index number as the parameter. And, removes the element specified by the index number.
To learn more about removing elements from the linkedlist, visit the Java program to remove elements from LinkedList…
Other Methods
| Methods | Description |
|---|---|
contains() | checks if the LinkedList contains the element |
indexOf() | returns the index of the first occurrence of the element |
lastIndexOf() | returns the index of the last occurrence of the element |
clear() | removes all the elements of the LinkedList |
iterator() | returns an iterator to iterate over LinkedList |
LinkedList as Deque and Queue
Since the LinkedList class also implements the Queue and the Deque interface, it can implement methods of these interfaces as well. Here are some of the commonly used methods:
| Methods | Descriptions |
|---|---|
addFirst() | adds the specified element at the beginning of the linked list |
addLast() | adds the specified element at the end of the linked list |
getFirst() | returns the first element |
getLast() | returns the last element |
removeFirst() | removes the first element |
removeLast() | removes the last element |
peek() | returns the first element (head) of the linked list |
poll() | returns and removes the first element from the linked list |
offer() | adds the specified element at the end of the linked list |
Example: Java LinkedList as Queue
import java.util.LinkedList; import java.util.Queue; class Main ( public static void main(String() args) ( Queue languages = new LinkedList(); // add elements languages.add("Python"); languages.add("Java"); languages.add("C"); System.out.println("LinkedList: " + languages); // access the first element String str1 = languages.peek(); System.out.println("Accessed Element: " + str1); // access and remove the first element String str2 = languages.poll(); System.out.println("Removed Element: " + str2); System.out.println("LinkedList after poll(): " + languages); // add element at the end languages.offer("Swift"); System.out.println("LinkedList after offer(): " + languages); ) )
Output
LinkedList: (Python, Java, C) Accessed Element: Python Removed Element: Python LinkedList after poll(): (Java, C) LinkedList after offer(): (Java, C, Swift)
Example: LinkedList as Deque
import java.util.LinkedList; import java.util.Deque; class Main ( public static void main(String() args)( Deque animals = new LinkedList(); // add element at the beginning animals.add("Cow"); System.out.println("LinkedList: " + animals); animals.addFirst("Dog"); System.out.println("LinkedList after addFirst(): " + animals); // add elements at the end animals.addLast("Zebra"); System.out.println("LinkedList after addLast(): " + animals); // remove the first element animals.removeFirst(); System.out.println("LinkedList after removeFirst(): " + animals); // remove the last element animals.removeLast(); System.out.println("LinkedList after removeLast(): " + animals); ) )
Output
LinkedList: (Cow) LinkedList after addFirst(): (Dog, Cow) LinkedList after addLast(): (Dog, Cow, Zebra) LinkedList after removeFirst(): (Cow, Zebra) LinkedList after removeLast(): (Cow)
Iterating through LinkedList
We can use the Java for-each loop to iterate through LinkedList. For example,
import java.util.LinkedList; class Main ( public static void main(String() args) ( // Creating a linked list LinkedList animals = new LinkedList(); animals.add("Cow"); animals.add("Cat"); animals.add("Dog"); System.out.println("LinkedList: " + animals); // Using forEach loop System.out.println("Accessing linked list elements:"); for(String animal: animals) ( System.out.print(animal); System.out.print(", "); ) ) )
Output
LinkedList: (Cow, Cat, Dog) Accessing linked list elements: Cow, Cat, Dog,
LinkedList Vs. ArrayList
Both the Java ArrayList and LinkedList implements the List interface of the Collections framework. However, there exists some difference between them.
| LinkedList | ArrayList |
|---|---|
Implements List, Queue, and Deque interfaces. | Implements List interface. |
| Stores 3 values (previous address, data, and next address) in a single position. | Armazena um único valor em uma única posição. |
| Fornece a implementação de lista duplamente vinculada. | Fornece uma implementação de array redimensionável. |
Sempre que um elemento é adicionado preve o nextendereço é alterado. | Sempre que um elemento é adicionado, todos os elementos após essa posição são deslocados. |
| Para acessar um elemento, precisamos iterar desde o início até o elemento. | Pode acessar elementos aleatoriamente usando índices. |
Nota : Também podemos criar uma LinkedList usando interfaces em Java. Por exemplo,
// create linkedlist using List List animals1 = new LinkedList(); // creating linkedlist using Queue Queue animals2 = new LinkedList(); // creating linkedlist using Deque Deque animals3 = new LinkedList();
Aqui, se LinkedList é criada usando uma interface, então não podemos usar métodos fornecidos por outras interfaces. Ou seja, animals1 não pode usar métodos específicos para interfaces Queuee Deque.
