Estrutura de dados de lista encadeada em Java

Diferentes estruturas de dados são criadas para diferentes propósitos. Você pode conhecer ArrayList (se ainda não, recomendamos que você leia sobre isso primeiro). Neste artigo, vamos aprender sobre LinkedList e perceber para que serve esta coleção. Se você examinar a fonte de código de classe LinkedList Java 8 (ou versão posterior da linguagem) (no site da Oracle ou em seu IDE, no caso de IDEA: crtl+B no nome da classe), verá a seguinte declaração:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

No momento, a informação mais importante do código é o fato de LinkedList implementar as interfaces List e Deque . A interface List mantém a sequência de adição de itens e permite o acesso ao item por índice. A Fila “comum” suporta adicionar elementos ao final e extraí-los do início. Deque é uma fila bidirecional e suporta a adição e remoção de elementos de ambos os lados. Você pode pensar nisso como uma combinação de pilha e fila. Portanto, LinkedList é uma implementação desses dois e nos permite criar uma fila bidirecional composta por quaisquer objetos, incluindo null. LinkedListé uma coleção de elementos. Podemos ver no código fonte da classe, desta vez preste atenção nos campos:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

Cada elemento, geralmente chamado de Node , contém um objeto e referências a dois objetos vizinhos — o anterior e o seguinte. Portanto, não é muito eficaz em termos de uso de memória. Como LinkedList na verdade é uma estrutura bidirecional, podemos facilmente adicionar ou remover elementos de ambos os lados.

Construtores LinkedList

De volta ao código-fonte, podemos descobrir que LinkedList tem dois construtores

• LinkedList() sem parâmetros é usado para construir uma lista vazia.
• >LinkedList(Collection<? extends E> c) serve para criar uma lista contendo os elementos da coleção especificada, em ordem, eles são retornados pelo iterador da coleção.

Declaração LinkedList

Na verdade, uma lista encadeada (Java ou em qualquer outra linguagem) consiste em uma sequência de nós. Cada nó é projetado para armazenar um objeto de um tipo definido durante a criação. Então, para criar LinkedList , o código Java é o seguinte:

LinkedList<Integer> myList = new LinkedList<>();

Temos um objeto para manter uma sequência de inteiros e links para os vizinhos. No entanto, está vazio no momento.

Principais operações da LinkedList

Como de costume, no caso de Collections você pode colocar elementos em LinkedList (no final ou no meio), remover de lá e obter um elemento por índice. Então aqui estão eles:

• add(E element) Acrescenta o elemento especificado ao final desta lista;
• add(int index, E element) Insere o elemento na posição especificada index ;
• get(int index) Retorna o elemento na posição especificada nesta lista;
• remove(int index) Remove o elemento que está na posição index;
• remove(Object o) Remove a primeira ocorrência de ? o elemento desta lista se estiver lá.
• remove() Recupera e remove o primeiro elemento da lista.

Implementação de lista encadeada em Java, adicionando e removendo elementos. Exemplo

Vamos experimentar essas operações na prática. Primeiro, a implementação do Java LinkedList: criando um LinkedList de Strings, adicionando 3 elementos. Em seguida, remova um e adicione um no meio.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

O resultado da execução deste programa:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

Uma LinkedList faz parte do framework Collection , você pode usar o Iterator para remover elementos, bem como um iterador especial para listas — ListIterator . Ainda mais, as operações com iterador fornecem os principais benefícios da classe LinkedList : bom desempenho das operações de inserção/exclusão. Usando o Iterator, você pode obter um tempo constante para eles. Mais adiante neste artigo, escreveremos um exemplo de código para comparar ArrayList e LinkedList+Iterator

• Iterator.remove() remove o último elemento retornado por este iterador.
• ListIterator.add(E element) insere um elemento na lista

Java LinkedList Exemplo: como o Iterator funciona

Aqui temos um pequeno código Java LinkedList Example, onde tentamos adicionar e deletar via Iterator.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

O resultado da execução deste programa:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

Mais operações Java LinkedList :

• addFirst() , addLast() adiciona um elemento ao início/fim de uma lista
• clear() remove todos os elementos da lista
• contains(Object o) retorna verdadeiro se a lista contiver o elemento o.
• indexOf(Object o) retorna o índice da primeira ocorrência do elemento o, ou -1 se não estiver na lista.
• set(int index, elemento E) substitui o elemento na posição do índice pelo elemento
• size() Retorna a quantidade de elementos na lista.
• toArray() retorna um array contendo todos os elementos da lista do primeiro ao último elemento.

BTW sendo uma fila de dois tamanhos, LinkedList em Java tem operações específicas de pilha:

• pop() que retira um elemento da pilha (representado pela lista)
• push(E e) que coloca um elemento na pilha (representado por esta lista)

Como reverter LinkedList: exemplo

Aqui está um pequeno exemplo, uma tarefa popular, mas fácil para iniciantes. Temos uma LinkedList e devemos revertê-la. O algoritmo mais fácil é percorrer o LinkedList na ordem inversa e colocar cada elemento no novo. No entanto, talvez você encontre uma maneira melhor? Aqui está o código do programa java de lista encadeada reversa:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

O resultado:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList vs ArrayList: quando usar o primeiro

Ambos LinkedList e ArrayList são implementações da interface List . LinkedList o implementa com uma lista duplamente vinculada. ArrayList o implementa usando um array de redimensionamento dinâmico. Como você já sabe, cada nó de LinkedList contém Objetos e duas referências aos vizinhos. Isso significa custos adicionais de memória para armazenar referências entre elementos no caso de Java LinkedList . ArrayList o implementa com um array de redimensionamento dinâmico. Algumas das operações LinkedList e ArrayList parecem iguais, mas funcionam de maneira diferente. Na lista de matrizescaso, você manipula com matrizes internas, em LinkedList — com referências. ArrayList é a implementação de List mais popular . Você definitivamente deve usar ArrayList quando o acesso ao índice for uma prioridade, pois essas operações são executadas em tempo constante. Adicionar ao final da lista em média também é feito em tempo constante. Ainda mais, ArrayList não tem custos adicionais para armazenar um monte de elementos. Você pode contar como contras a velocidade de inserção e remoção de operações quando não é feito no final da lista. LinkedListé mais útil no caso do desempenho das operações de inserção e exclusão de algumas maneiras: se você usar iteradores, isso ocorre em tempo constante. As operações de acesso por índice são realizadas buscando do início ao fim (o que for mais próximo) até o elemento desejado. No entanto, não se esqueça dos custos adicionais para armazenar referências entre elementos. Portanto, aqui estão as operações LinkedList e ArrayList padrão com tempos de execução algorítmicos. N refere-se ao número de itens que já estão na lista. O(N) significa que no pior caso devemos “percorrer” toda a lista até encontrar a posição necessária, por exemplo, para inserção do novo elemento na lista. O(1)significa que a operação ocorre em tempo constante, independentemente do número de itens.

Complexidade de Tempo LinkedList

Complexidade de Tempo ArrayList

Quando usar LinkedList: Exemplo

Definitivamente, ArrayList é a implementação de List mais popular . No entanto, você pode encontrar situações em que as operações de adicionar/remover são necessárias com muita frequência. Nesse caso, LinkedList junto com Iterator pode ser benéfico. Aqui está um exemplo. Temos uma longa lista e devemos excluir todos os elementos desta lista. Vamos fazer esta tarefa com ArrayList e LinkedList + Iterator . Comparamos o tempo de cada operação e o imprimimos no console. Aqui o código:

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

Resultado para ArrayList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

Resultado para LinkedList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

Como você pode ver neste caso, LinkedList é muito mais eficaz. Sejamos honestos. No desenvolvimento de software real, o uso do LinkedList é um tipo de evento raro. No entanto, um profissional deve saber sobre a existência dessa estrutura de dados e suas vantagens. Se no código real o LinkedList é um convidado raro, nas entrevistas do Java Junior ele é muito popular. E, no entanto, aqui está o que Joshua Bloch escreveu sobre LinkedList :

Complemento: Java de lista encadeada individualmente

Não existe uma lista vinculada individualmente entre as coleções clássicas em Java. A lista vinculada individualmente é uma estrutura em que cada nó contém um objeto e uma referência ao próximo nó, mas não ao anterior. Java LinkedList tem dois links, mas ninguém interfere com você para criar sua própria estrutura de dados, como um código único>Lista vinculada. Aqui estão algumas etapas para resolver essas tarefas:

1. Crie uma classe Node com dois atributos, data e next. Next é uma referência ao próximo nó.
2. Crie a classe FirstLast com dois atributos, head e tail.
3. Crie um método add() para adicionar um novo nó à lista. Verifique primeiro se a lista está vazia ( head == null ). Nesse caso, cabeça e cauda referem-se ao novo nó. Se a lista não estiver vazia, o novo nó será adicionado ao final, então o próximo atributo da cauda se refere ao nó adicionado e o novo nó se torna a cauda da lista.

A propósito, você também pode tentar criar sua própria LinkedList como um exercício. Boa sorte no seu aprendizado.