Lista Encadeada
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 operação de LinkedList:
Como você pode ver, a sintaxe é absolutamente idêntica à declaração de um ArrayList. Em geral, qualquer lista pode ser declarada desta forma.
Mas a parte interessante começa quando tentamos entender como funciona o LinkedList.
Como é estruturada uma LinkedList?
Internamente, uma LinkedList funciona com Nodes. Um Node é um objeto que é armazenado dentro de uma LinkedList. Ele é implementado dentro da LinkedList da seguinte maneira:
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 destrinchar o que essa classe engloba.
Primeiro, precisamos responder à principal questão que surge: O que <E> significa? Isso é um genérico.
Em termos simples, aqui, deixamos um espaço reservado para o tipo de dado que será especificado durante a inicialização. Usamos esse marcador no código, que será substituído pelo tipo de dado especificado pelo usuário mais tarde.
Isso pode ser comparado a sobrecarga.
Vamos ver como isso funciona:
Então, ao invés de sobrecarregar este método para cada tipo de dado, usamos um genérico no qual inserimos o tipo de dado com o qual o método irá funcionar.
A letra E será simplesmente substituída pelo tipo de dado requerido. No nosso caso, é Integer.
A seguir, vamos prestar atenção ao campo E item. Este é o valor do objeto que será armazenado neste Nó. Então, 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, vemos referências a outros objetos Nó: Node<E> next e Node<E> prev.
Esta é a principal característica de uma lista ligada. Em um Nó, existe uma referência para o próximo e para o anterior. É assim que iteramos pela lista. Vamos examinar mais de perto a iteração através de uma LinkedList.
Ao analisar tal esquema, podemos concluir que iterar por uma lista desse tipo funcionará de maneira um pouco diferente.
No ArrayList<>(), sob o capô, o programa utiliza um array que dobra de tamanho quando o número de elementos ocupa 3/4 do tamanho do array.
Em uma LinkedList<>(), não precisamos recriar um array porque não existe array em uma LinkedList. Ao invés disso, um novo objeto Node será criado ao adicionar um novo elemento, ligado por referências ao último elemento antigo.
Entendo que parece e soa um pouco complicado, mas você não precisará configurar tudo isso como programador. Os métodos para LinkedList são os mesmos daqueles para ArrayList porque ambos herdam da interface List, que define os métodos que todos os seus descendentes devem implementar.
Então, por que precisamos saber sobre diferentes tipos de listas?
A resposta é:
Complexidade Algorítmica
No framework Collection, existem muitas estruturas de dados diferentes, e cada uma delas possui sua complexidade algorítmica.
A complexidade algorítmica é representada usando a notação big O (por exemplo, O(n), O(n^2)), onde "O" representa o "big O" e indica um limite superior no crescimento do tempo de execução como função do tamanho da entrada. Aqui estão os principais tipos de complexidade algorítmica:
-
O(1) (tempo constante): A complexidade temporal 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 temporal cresce logaritmicamente com o tamanho dos dados de entrada. Exemplo: pesquisa binária em um array ordenado.
-
O(n) (tempo linear): A complexidade temporal cresce linearmente com o tamanho dos dados de entrada. Exemplo: iterar por todos os elementos em um ArrayList.
-
O(n^2) (tempo quadrático): A complexidade temporal é proporcional ao quadrado do tamanho dos dados de entrada. Exemplo: ordenação por bolha.
Estes são categorias básicas, e existem muitos outros tipos de complexidade algorítmica, tais como O(n log n), O(2^n), O(n!), entre outros, caracterizando algoritmos mais complexos. Escolher um algoritmo eficiente, considerando sua complexidade, é um aspecto crucial do desenvolvimento de software.
Agora, vamos voltar às estruturas de dados em Java. Cada estrutura de dados tem sua complexidade algorítmica dependendo da operação que precisa ser realizada. Vamos dar uma olhada na tabela:
Nota
Como você pode observar nesta tabela, exploraremos muitas outras estruturas de dados mais adiante. Por enquanto, você deve dar uma olhada em
ArrayListeLinkedList.
Você pode ver que procurar um elemento pelo índice em um ArrayList tem complexidade constante, já que simplesmente acessamos o índice no array.
Entretanto, em um LinkedList, procurar por índice leva muito mais tempo porque temos que atravessar todos os nós e encontrar o objeto que precisamos pelo índice.
Por outro lado, se observarmos a inserção de um elemento, o LinkedList tem complexidade constante, enquanto o ArrayList tem complexidade linear.
Isso acontece porque, para inserir um elemento em um LinkedList, apenas precisamos alterar os links nos nós para novos, inserindo o elemento entre eles. Para um ArrayList, precisamos recriar o array com o novo elemento, o que envolve copiar o array antigo e inserir o elemento, levando muito mais tempo.
Vamos ver 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. Depois, as populamos com 1.000.000 de inteiros aleatórios. As listas têm o mesmo conteúdo, cada uma contendo um milhão de números de 1 a 100.
Em seguida, 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 mostra o tempo atual em nanosegundos. Então, para cada lista, subtraímos o tempo inicial do tempo final, determinando assim quanto tempo foi gasto adicionando um elemento no meio da lista.
Você pode ver que o LinkedList teve um desempenho significativamente mais rápido, conforme evidenciado na tabela. LinkedList tem complexidade algorítmica constante, enquanto ArrayList possui complexidade linear.
É por isso que precisamos de diferentes tipos de listas. Se o seu projeto lida com uma grande quantidade de dados onde a otimização é crucial, repensar qual tipo de lista terá um desempenho mais rápido em certos casos é válido. Mas vou te contar um segredo: quase sempre uso ArrayList.
ListaLigadaSimples
Existe outra estrutura de dados não revelada chamada ListaLigadaSimples. Como o nome sugere, essa estrutura de dados utiliza iteração em apenas uma direção. Enquanto a classe LinkedList possui os campos item, next e prev em seus nós, a classe ListaLigadaSimples possui apenas 2 campos em seus nós: 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 mapas, onde a iteração é necessária apenas em uma direção. Aprenderemos sobre mapas, especialmente HashMap, em seções futuras. No próximo capítulo, escreveremos uma implementação de SinglyLinkedList para entender melhor como esta interessante estrutura de dados funciona.
1. Qual estrutura de dados terá um desempenho mais rápido se quisermos encontrar um elemento pelo índice?
2. Qual estrutura de dados terá um desempenho melhor ao realizar uma operação de exclusão?
3. Como a classe Node participa na operação de LinkedList?
Obrigado pelo seu feedback!
Pergunte à IA
Pergunte à IA
Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo
Awesome!
Completion rate improved to 4Lista Encadeada
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 operação de LinkedList:
Como você pode ver, a sintaxe é absolutamente idêntica à declaração de um ArrayList. Em geral, qualquer lista pode ser declarada desta forma.
Mas a parte interessante começa quando tentamos entender como funciona o LinkedList.
Como é estruturada uma LinkedList?
Internamente, uma LinkedList funciona com Nodes. Um Node é um objeto que é armazenado dentro de uma LinkedList. Ele é implementado dentro da LinkedList da seguinte maneira:
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 destrinchar o que essa classe engloba.
Primeiro, precisamos responder à principal questão que surge: O que <E> significa? Isso é um genérico.
Em termos simples, aqui, deixamos um espaço reservado para o tipo de dado que será especificado durante a inicialização. Usamos esse marcador no código, que será substituído pelo tipo de dado especificado pelo usuário mais tarde.
Isso pode ser comparado a sobrecarga.
Vamos ver como isso funciona:
Então, ao invés de sobrecarregar este método para cada tipo de dado, usamos um genérico no qual inserimos o tipo de dado com o qual o método irá funcionar.
A letra E será simplesmente substituída pelo tipo de dado requerido. No nosso caso, é Integer.
A seguir, vamos prestar atenção ao campo E item. Este é o valor do objeto que será armazenado neste Nó. Então, 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, vemos referências a outros objetos Nó: Node<E> next e Node<E> prev.
Esta é a principal característica de uma lista ligada. Em um Nó, existe uma referência para o próximo e para o anterior. É assim que iteramos pela lista. Vamos examinar mais de perto a iteração através de uma LinkedList.
Ao analisar tal esquema, podemos concluir que iterar por uma lista desse tipo funcionará de maneira um pouco diferente.
No ArrayList<>(), sob o capô, o programa utiliza um array que dobra de tamanho quando o número de elementos ocupa 3/4 do tamanho do array.
Em uma LinkedList<>(), não precisamos recriar um array porque não existe array em uma LinkedList. Ao invés disso, um novo objeto Node será criado ao adicionar um novo elemento, ligado por referências ao último elemento antigo.
Entendo que parece e soa um pouco complicado, mas você não precisará configurar tudo isso como programador. Os métodos para LinkedList são os mesmos daqueles para ArrayList porque ambos herdam da interface List, que define os métodos que todos os seus descendentes devem implementar.
Então, por que precisamos saber sobre diferentes tipos de listas?
A resposta é:
Complexidade Algorítmica
No framework Collection, existem muitas estruturas de dados diferentes, e cada uma delas possui sua complexidade algorítmica.
A complexidade algorítmica é representada usando a notação big O (por exemplo, O(n), O(n^2)), onde "O" representa o "big O" e indica um limite superior no crescimento do tempo de execução como função do tamanho da entrada. Aqui estão os principais tipos de complexidade algorítmica:
-
O(1) (tempo constante): A complexidade temporal 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 temporal cresce logaritmicamente com o tamanho dos dados de entrada. Exemplo: pesquisa binária em um array ordenado.
-
O(n) (tempo linear): A complexidade temporal cresce linearmente com o tamanho dos dados de entrada. Exemplo: iterar por todos os elementos em um ArrayList.
-
O(n^2) (tempo quadrático): A complexidade temporal é proporcional ao quadrado do tamanho dos dados de entrada. Exemplo: ordenação por bolha.
Estes são categorias básicas, e existem muitos outros tipos de complexidade algorítmica, tais como O(n log n), O(2^n), O(n!), entre outros, caracterizando algoritmos mais complexos. Escolher um algoritmo eficiente, considerando sua complexidade, é um aspecto crucial do desenvolvimento de software.
Agora, vamos voltar às estruturas de dados em Java. Cada estrutura de dados tem sua complexidade algorítmica dependendo da operação que precisa ser realizada. Vamos dar uma olhada na tabela:
Nota
Como você pode observar nesta tabela, exploraremos muitas outras estruturas de dados mais adiante. Por enquanto, você deve dar uma olhada em
ArrayListeLinkedList.
Você pode ver que procurar um elemento pelo índice em um ArrayList tem complexidade constante, já que simplesmente acessamos o índice no array.
Entretanto, em um LinkedList, procurar por índice leva muito mais tempo porque temos que atravessar todos os nós e encontrar o objeto que precisamos pelo índice.
Por outro lado, se observarmos a inserção de um elemento, o LinkedList tem complexidade constante, enquanto o ArrayList tem complexidade linear.
Isso acontece porque, para inserir um elemento em um LinkedList, apenas precisamos alterar os links nos nós para novos, inserindo o elemento entre eles. Para um ArrayList, precisamos recriar o array com o novo elemento, o que envolve copiar o array antigo e inserir o elemento, levando muito mais tempo.
Vamos ver 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. Depois, as populamos com 1.000.000 de inteiros aleatórios. As listas têm o mesmo conteúdo, cada uma contendo um milhão de números de 1 a 100.
Em seguida, 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 mostra o tempo atual em nanosegundos. Então, para cada lista, subtraímos o tempo inicial do tempo final, determinando assim quanto tempo foi gasto adicionando um elemento no meio da lista.
Você pode ver que o LinkedList teve um desempenho significativamente mais rápido, conforme evidenciado na tabela. LinkedList tem complexidade algorítmica constante, enquanto ArrayList possui complexidade linear.
É por isso que precisamos de diferentes tipos de listas. Se o seu projeto lida com uma grande quantidade de dados onde a otimização é crucial, repensar qual tipo de lista terá um desempenho mais rápido em certos casos é válido. Mas vou te contar um segredo: quase sempre uso ArrayList.
ListaLigadaSimples
Existe outra estrutura de dados não revelada chamada ListaLigadaSimples. Como o nome sugere, essa estrutura de dados utiliza iteração em apenas uma direção. Enquanto a classe LinkedList possui os campos item, next e prev em seus nós, a classe ListaLigadaSimples possui apenas 2 campos em seus nós: 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 mapas, onde a iteração é necessária apenas em uma direção. Aprenderemos sobre mapas, especialmente HashMap, em seções futuras. No próximo capítulo, escreveremos uma implementação de SinglyLinkedList para entender melhor como esta interessante estrutura de dados funciona.
1. Qual estrutura de dados terá um desempenho mais rápido se quisermos encontrar um elemento pelo índice?
2. Qual estrutura de dados terá um desempenho melhor ao realizar uma operação de exclusão?
3. Como a classe Node participa na operação de LinkedList?
Obrigado pelo seu feedback!
