Linked List em Java
E se os objetos estivessem ligados entre si?
Vamos avançar para a próxima estrutura de dados, bastante interessante - LinkedList.
Vamos analisar a sintaxe e o esquema de funcionamento de LinkedList:
Como pode ser observado, a sintaxe é absolutamente idêntica à declaração de um ArrayList. De modo geral, qualquer lista pode ser declarada dessa forma.
Mas a parte interessante começa quando tentamos entender como o LinkedList funciona.
Como é Estruturado o LinkedList?
Internamente, o LinkedList funciona com Nodes. Um Node é um objeto que é armazenado dentro do LinkedList. Ele é implementado dentro do LinkedList da seguinte forma:
Main.java
1234567891011class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
Vamos analisar do que essa classe é composta.
Primeiro, é necessário responder à principal dúvida que surge: O que significa <E>? Isto é um genérico.
De forma simples, aqui, você deixa um espaço reservado para o tipo de dado que será especificado durante a inicialização. Esse espaço reservado é utilizado no código, sendo posteriormente substituído pelo tipo de dado definido pelo usuário.
Isso pode ser comparado à sobrecarga.
Veja como funciona:
Assim, em vez de sobrecarregar este método para cada tipo de dado, utiliza-se um genérico no qual se insere o tipo de dado com o qual o método irá trabalhar.
A letra E será simplesmente substituída pelo tipo de dado necessário. No nosso caso, é Integer.
Em seguida, observe o campo item E. Este é o valor do objeto que será armazenado neste Node.
Portanto, se criarmos uma lista como {0, 1, 2, 3}, o primeiro nó armazenará o item 0, o segundo nó armazenará o item 1 e assim por diante.
A seguir, você vê referências para outros objetos Node: Node<E> next e Node<E> prev.
Esta é a principal característica de uma lista ligada. Em um Node, há uma referência para o próximo Node e para o anterior.
É assim que se percorre a lista. Vamos analisar mais detalhadamente a iteração em uma LinkedList.
Ao observar tal esquema, pode-se concluir que a iteração por esta lista funciona de forma diferente.
Em ArrayList<>(), internamente, o programa utiliza um array que dobra de tamanho quando o número de elementos atinge 3/4 de sua capacidade.
Em uma LinkedList<>(), não é necessário recriar um array porque não existe array em uma LinkedList.
Em vez disso, ao adicionar um novo elemento, um novo objeto Node é criado e vinculado por referências ao último elemento anterior.
Pode parecer e soar um pouco complicado, mas como programador, não será necessário configurar tudo isso.
Os métodos de LinkedList são os mesmos que os de ArrayList, pois ambos herdam da interface List, que define os métodos que todos os seus descendentes devem implementar.
Complexidade Algorítmica
No framework Collection, existem diversas estruturas de dados, e cada uma possui sua própria complexidade algorítmica.
A complexidade algorítmica é representada utilizando a notação big O (por exemplo, O(n), O(n^2)), onde "O" significa "big O" e indica um limite superior para o crescimento do tempo de execução em função do tamanho da entrada.
A seguir estão os principais tipos de complexidade algorítmica:
-
O(1)(tempo constante): a complexidade de tempo não depende do tamanho dos dados de entrada. Por exemplo, acessar um elemento em um array pelo índice; -
O(log n)(tempo logarítmico): a complexidade de tempo cresce de forma logarítmica com o tamanho dos dados de entrada. Exemplo: busca binária em um array ordenado; -
O(n)(tempo linear): a complexidade de tempo cresce linearmente com o tamanho dos dados de entrada. Exemplo: percorrer todos os elementos em umArrayList; -
O(n^2)(tempo quadrático): a complexidade de tempo é proporcional ao quadrado do tamanho dos dados de entrada. Exemplo: ordenação por bolha.
Estas são categorias básicas, e existem muitos outros tipos de complexidade algorítmica, como O(n log n), O(2^n), O(n!), entre outros, caracterizando algoritmos mais complexos. A escolha de um algoritmo eficiente, considerando sua complexidade, é um aspecto crucial do desenvolvimento de software.
Agora, vamos retornar às estruturas de dados em Java. Cada estrutura de dados possui sua complexidade algorítmica de tempo dependendo da operação que precisa ser realizada. Veja a tabela:
É possível observar que a busca de um elemento pelo índice em ArrayList possui complexidade constante, pois simplesmente acessamos o índice no array.
Enquanto isso, em LinkedList, a busca pelo índice leva muito mais tempo porque é necessário percorrer todos os nós e encontrar o objeto desejado pelo índice.
Por outro lado, ao analisar a inserção de um elemento, LinkedList apresenta complexidade constante, enquanto ArrayList possui complexidade linear. Isso ocorre porque, para inserir um elemento em uma LinkedList, basta alterar as referências nos nós para os novos, inserindo o elemento entre eles. Para ArrayList, é necessário recriar o array com o novo elemento, o que envolve copiar o array antigo e inserir o elemento, demandando muito mais tempo.
Veja um exemplo:
Main.java
1234567891011121314151617181920212223242526272829package com.example; import java.util.*; public class Main { public static void main(String[] args) { List<Integer> linkedList = new LinkedList<>(); List<Integer> arrayList = new ArrayList<>(); Random random = new Random(); for (int i = 0; i < 1000000; i++) { int randomValue = random.nextInt(100); arrayList.add(randomValue); linkedList.add(randomValue); } long startTimeArrayList = System.nanoTime(); arrayList.add(1000, 50); long endTimeArrayList = System.nanoTime(); long elapsedTimeArrayList = endTimeArrayList - startTimeArrayList; System.out.println("Time taken to put data in ArrayList: " + elapsedTimeArrayList + " nanoseconds"); long startTimeLinkedList = System.nanoTime(); linkedList.add(1000, 50); long endTimeLinkedList = System.nanoTime(); long elapsedTimeLinkedList = endTimeLinkedList - startTimeLinkedList; System.out.println("Time taken to put data in LinkedList: " + elapsedTimeLinkedList + " nanoseconds"); } }
Criamos duas listas: uma é um ArrayList e a outra é um LinkedList. Em seguida, preenchemos ambas com 1.000.000 de inteiros aleatórios. As listas possuem o mesmo conteúdo, cada uma contendo um milhão de números de 1 a 100.
Depois, medimos o tempo necessário para adicionar um elemento no milésimo índice com o valor 50. Utilizamos o método System.nanoTime() para medir o tempo, que exibe o tempo atual em nanossegundos. Em seguida, para cada lista, subtraímos o tempo inicial do tempo final, assim determinando quanto tempo foi gasto para adicionar um elemento no meio da lista.
É possível observar que o LinkedList teve um desempenho significativamente mais rápido, como mostrado na tabela. O LinkedList possui complexidade algorítmica constante, enquanto o ArrayList apresenta complexidade linear.
Por isso, precisamos de diferentes tipos de listas. Se o seu projeto lida com uma grande quantidade de dados onde a otimização é crucial, vale a pena reconsiderar qual tipo de lista o programa executará mais rapidamente em determinados casos. Mas vou contar um segredo: quase sempre utilizo o ArrayList.
SinglyLinkedList
Existe outra estrutura de dados não divulgada chamada SinglyLinkedList. Como o nome sugere, essa estrutura de dados utiliza iteração em apenas uma direção. Enquanto a classe LinkedList do Node possui os campos: item, next e prev, a classe SinglyLinkedList do Node possui apenas 2 campos: item e next.
Main.java
123456789class Node<E> { E item; Node<E> next; Node(E element, Node<E> next) { this.item = element; this.next = next; } }
Esta estrutura de dados é utilizada em estruturas como maps, onde a iteração é necessária em apenas uma direção. Vamos aprender sobre maps, especialmente HashMap, em seções futuras.
No próximo capítulo, escreveremos uma implementação de SinglyLinkedList para compreender melhor como essa interessante estrutura de dados funciona.
1. Qual estrutura de dados terá melhor desempenho se quisermos encontrar um elemento pelo índice?
2. Qual estrutura de dados apresenta melhor desempenho ao realizar uma operação de exclusão?
3. Como a classe Node participa na operação de uma LinkedList?
Obrigado pelo seu feedback!
Pergunte à IA
Pergunte à IA
Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo
Incrível!
Completion taxa melhorada para 4Linked List em Java
Deslize para mostrar o menu
E se os objetos estivessem ligados entre si?
Vamos avançar para a próxima estrutura de dados, bastante interessante - LinkedList.
Vamos analisar a sintaxe e o esquema de funcionamento de LinkedList:
Como pode ser observado, a sintaxe é absolutamente idêntica à declaração de um ArrayList. De modo geral, qualquer lista pode ser declarada dessa forma.
Mas a parte interessante começa quando tentamos entender como o LinkedList funciona.
Como é Estruturado o LinkedList?
Internamente, o LinkedList funciona com Nodes. Um Node é um objeto que é armazenado dentro do LinkedList. Ele é implementado dentro do LinkedList da seguinte forma:
Main.java
1234567891011class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
Vamos analisar do que essa classe é composta.
Primeiro, é necessário responder à principal dúvida que surge: O que significa <E>? Isto é um genérico.
De forma simples, aqui, você deixa um espaço reservado para o tipo de dado que será especificado durante a inicialização. Esse espaço reservado é utilizado no código, sendo posteriormente substituído pelo tipo de dado definido pelo usuário.
Isso pode ser comparado à sobrecarga.
Veja como funciona:
Assim, em vez de sobrecarregar este método para cada tipo de dado, utiliza-se um genérico no qual se insere o tipo de dado com o qual o método irá trabalhar.
A letra E será simplesmente substituída pelo tipo de dado necessário. No nosso caso, é Integer.
Em seguida, observe o campo item E. Este é o valor do objeto que será armazenado neste Node.
Portanto, se criarmos uma lista como {0, 1, 2, 3}, o primeiro nó armazenará o item 0, o segundo nó armazenará o item 1 e assim por diante.
A seguir, você vê referências para outros objetos Node: Node<E> next e Node<E> prev.
Esta é a principal característica de uma lista ligada. Em um Node, há uma referência para o próximo Node e para o anterior.
É assim que se percorre a lista. Vamos analisar mais detalhadamente a iteração em uma LinkedList.
Ao observar tal esquema, pode-se concluir que a iteração por esta lista funciona de forma diferente.
Em ArrayList<>(), internamente, o programa utiliza um array que dobra de tamanho quando o número de elementos atinge 3/4 de sua capacidade.
Em uma LinkedList<>(), não é necessário recriar um array porque não existe array em uma LinkedList.
Em vez disso, ao adicionar um novo elemento, um novo objeto Node é criado e vinculado por referências ao último elemento anterior.
Pode parecer e soar um pouco complicado, mas como programador, não será necessário configurar tudo isso.
Os métodos de LinkedList são os mesmos que os de ArrayList, pois ambos herdam da interface List, que define os métodos que todos os seus descendentes devem implementar.
Complexidade Algorítmica
No framework Collection, existem diversas estruturas de dados, e cada uma possui sua própria complexidade algorítmica.
A complexidade algorítmica é representada utilizando a notação big O (por exemplo, O(n), O(n^2)), onde "O" significa "big O" e indica um limite superior para o crescimento do tempo de execução em função do tamanho da entrada.
A seguir estão os principais tipos de complexidade algorítmica:
-
O(1)(tempo constante): a complexidade de tempo não depende do tamanho dos dados de entrada. Por exemplo, acessar um elemento em um array pelo índice; -
O(log n)(tempo logarítmico): a complexidade de tempo cresce de forma logarítmica com o tamanho dos dados de entrada. Exemplo: busca binária em um array ordenado; -
O(n)(tempo linear): a complexidade de tempo cresce linearmente com o tamanho dos dados de entrada. Exemplo: percorrer todos os elementos em umArrayList; -
O(n^2)(tempo quadrático): a complexidade de tempo é proporcional ao quadrado do tamanho dos dados de entrada. Exemplo: ordenação por bolha.
Estas são categorias básicas, e existem muitos outros tipos de complexidade algorítmica, como O(n log n), O(2^n), O(n!), entre outros, caracterizando algoritmos mais complexos. A escolha de um algoritmo eficiente, considerando sua complexidade, é um aspecto crucial do desenvolvimento de software.
Agora, vamos retornar às estruturas de dados em Java. Cada estrutura de dados possui sua complexidade algorítmica de tempo dependendo da operação que precisa ser realizada. Veja a tabela:
É possível observar que a busca de um elemento pelo índice em ArrayList possui complexidade constante, pois simplesmente acessamos o índice no array.
Enquanto isso, em LinkedList, a busca pelo índice leva muito mais tempo porque é necessário percorrer todos os nós e encontrar o objeto desejado pelo índice.
Por outro lado, ao analisar a inserção de um elemento, LinkedList apresenta complexidade constante, enquanto ArrayList possui complexidade linear. Isso ocorre porque, para inserir um elemento em uma LinkedList, basta alterar as referências nos nós para os novos, inserindo o elemento entre eles. Para ArrayList, é necessário recriar o array com o novo elemento, o que envolve copiar o array antigo e inserir o elemento, demandando muito mais tempo.
Veja um exemplo:
Main.java
1234567891011121314151617181920212223242526272829package com.example; import java.util.*; public class Main { public static void main(String[] args) { List<Integer> linkedList = new LinkedList<>(); List<Integer> arrayList = new ArrayList<>(); Random random = new Random(); for (int i = 0; i < 1000000; i++) { int randomValue = random.nextInt(100); arrayList.add(randomValue); linkedList.add(randomValue); } long startTimeArrayList = System.nanoTime(); arrayList.add(1000, 50); long endTimeArrayList = System.nanoTime(); long elapsedTimeArrayList = endTimeArrayList - startTimeArrayList; System.out.println("Time taken to put data in ArrayList: " + elapsedTimeArrayList + " nanoseconds"); long startTimeLinkedList = System.nanoTime(); linkedList.add(1000, 50); long endTimeLinkedList = System.nanoTime(); long elapsedTimeLinkedList = endTimeLinkedList - startTimeLinkedList; System.out.println("Time taken to put data in LinkedList: " + elapsedTimeLinkedList + " nanoseconds"); } }
Criamos duas listas: uma é um ArrayList e a outra é um LinkedList. Em seguida, preenchemos ambas com 1.000.000 de inteiros aleatórios. As listas possuem o mesmo conteúdo, cada uma contendo um milhão de números de 1 a 100.
Depois, medimos o tempo necessário para adicionar um elemento no milésimo índice com o valor 50. Utilizamos o método System.nanoTime() para medir o tempo, que exibe o tempo atual em nanossegundos. Em seguida, para cada lista, subtraímos o tempo inicial do tempo final, assim determinando quanto tempo foi gasto para adicionar um elemento no meio da lista.
É possível observar que o LinkedList teve um desempenho significativamente mais rápido, como mostrado na tabela. O LinkedList possui complexidade algorítmica constante, enquanto o ArrayList apresenta complexidade linear.
Por isso, precisamos de diferentes tipos de listas. Se o seu projeto lida com uma grande quantidade de dados onde a otimização é crucial, vale a pena reconsiderar qual tipo de lista o programa executará mais rapidamente em determinados casos. Mas vou contar um segredo: quase sempre utilizo o ArrayList.
SinglyLinkedList
Existe outra estrutura de dados não divulgada chamada SinglyLinkedList. Como o nome sugere, essa estrutura de dados utiliza iteração em apenas uma direção. Enquanto a classe LinkedList do Node possui os campos: item, next e prev, a classe SinglyLinkedList do Node possui apenas 2 campos: item e next.
Main.java
123456789class Node<E> { E item; Node<E> next; Node(E element, Node<E> next) { this.item = element; this.next = next; } }
Esta estrutura de dados é utilizada em estruturas como maps, onde a iteração é necessária em apenas uma direção. Vamos aprender sobre maps, especialmente HashMap, em seções futuras.
No próximo capítulo, escreveremos uma implementação de SinglyLinkedList para compreender melhor como essa interessante estrutura de dados funciona.
1. Qual estrutura de dados terá melhor desempenho se quisermos encontrar um elemento pelo índice?
2. Qual estrutura de dados apresenta melhor desempenho ao realizar uma operação de exclusão?
3. Como a classe Node participa na operação de uma LinkedList?
Obrigado pelo seu feedback!
