Java LinkedList

Oi! Todas as lições mais recentes foram dedicadas a ArrayList . Essa estrutura de dados é muito conveniente e útil. Ele pode lidar com muitas tarefas. Mas Java tem muitas outras estruturas de dados. Por que? Acima de tudo, porque a gama de tarefas é enorme e as estruturas de dados mais eficientes são diferentes para tarefas diferentes. Hoje conheceremos uma nova estrutura: Java LinkedList , uma lista duplamente encadeada.

Vamos ver como ele está organizado, por que é chamado de link duplo, como ele difere de ArrayList . Os elementos em um Java LinkedList são, na verdade, links em uma única cadeia. Além dos dados, cada elemento armazena referências aos elementos anteriores e posteriores. Essas referências permitem mover de um elemento para outro. É assim que você cria um:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

Saída: [Olá, Mundo! Meu nome é Earl, adoro Java, moro no Canadá] Veja como fica nossa lista: LinkedList - 2

Vamos ver como adicionar um novo elemento. Isso é feito usando o método add() .

earlBio.add(str2);

No ponto do código, nossa lista consiste em um elemento: a String str1 . Vejamos o que acontece a seguir na figura: LinkedList - 3

Como resultado, str2 e str1 tornam-se vinculados por meio dos links próximo e anterior armazenados nestes nós da lista: LinkedList - 4

Agora você deve entender a ideia principal de uma lista duplamente vinculada. Essa cadeia de links é precisamente o que torna os elementos LinkedList uma única lista. Ao contrário de ArrayList , LinkedList não possui uma matriz ou qualquer coisa parecida com uma matriz dentro. Qualquer (bem, a maioria) trabalho com ArrayList se resume a trabalhar com o array interno. Qualquer trabalho com Java LinkedListresume-se a mudar de links. Isso pode ser visto claramente adicionando um elemento no meio da lista:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

Como você pode ver, o método add() sobrecarregado permite que você especifique um índice específico para um novo item. Neste caso, queremos adicionar String str2 entre str1 e str3 . Isto é o que acontecerá internamente: LinkedList - 5

Após alterar os links internos, str2 foi adicionado com sucesso à lista: LinkedList - 6

Agora todos os 3 elementos estão conectados. Você pode mover através do próximo link do primeiro elemento da cadeia para o último e vice-versa. Portanto, estamos bastante confortáveis com a inserção, mas e a remoção de elementos? O princípio é exatamente o mesmo. Apenas atualizamos os links nos dois elementos "à esquerda e à direita" do elemento que está sendo removido:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

Veja o que acontece se excluirmos o item com índice 1 (está no meio da lista): LinkedList - 7

Após atualizar os links, obtemos o resultado desejado: LinkedList - 8

Ao contrário da operação de remoção em ArrayList , aqui não há necessidade de deslocar os elementos do array ou fazer qualquer coisa do tipo. Acabamos de atualizar os links para str1 e str3 . Eles agora apontam um para o outro, e str2 " caiu fora " da cadeia de links e não faz mais parte da lista.

Visão geral dos métodos

LinkedList tem muitos métodos em comum com ArrayList . Por exemplo, ambas as classes têm métodos como add() , remove() , indexOf() , clear() , contains() (indica se um item está na lista), set() (substitui um elemento existente) e tamanho() . Embora muitos deles funcionem de maneira diferente internamente (como descobrimos com add() e remove() ), o resultado final é o mesmo. No entanto, LinkedList possui métodos separados para trabalhar com o início e o fim da lista, o que ArrayList não possui:

addFirst() , addLast() : Estes métodos para adicionar um elemento ao início/fim da lista

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

Saída: [Carro{model='Ferrari 360 Spider'}, Carro{model='Bugatti Veyron'}, Carro{model='Lamborghini Diablo'}] [Carro{model='Ford Mondeo'}, Carro{model=' Ferrari 360 Spider'}, Carro{model='Bugatti Veyron'}, Carro{model='Lamborghini Diablo'}, Carro{model='Fiat Ducato'}] Terminamos com "Ford" no topo da lista , e "Fiat" no final.

peekFirst() , peekLast() : Os métodos retornam o primeiro/último elemento da lista. Eles retornam null se a lista estiver vazia.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

Saída: Carro{model='Ferrari 360 Spider'} Carro{model='Lamborghini Diablo'}

pollFirst() , pollLast() : Esses métodos retornam o primeiro/último elemento da lista e o removem da lista. Eles retornam null se a lista estiver vazia

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

Resultado: Carro{model='Ferrari 360 Spider'} Carro{model='Lamborghini Diablo'} O que falta na lista? [Carro{model='Bugatti Veyron'}]

toArray() : Este método retorna um array contendo os itens da lista

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

Output: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Agora sabemos como o LinkedList funciona e como sua organização difere do ArrayList . Quais são os benefícios de usar LinkedList ? Acima de tudo, nos beneficiamos quando trabalhamos no meio da lista. As operações de inserção e remoção no meio de uma LinkedList são muito mais simples do que em uma ArrayList . Simplesmente atualizamos os links dos elementos vizinhos e o elemento indesejado "cai fora" da cadeia de links. Mas em um ArrayList , devemos

verifique se há espaço suficiente (ao inserir)
caso contrário, criamos uma nova matriz e copiamos os dados para lá (ao inserir)
removemos/inserimos o elemento e movemos todos os outros elementos para a direita/esquerda (dependendo do tipo de operação). E a complexidade desse processo depende muito do tamanho da lista. Uma coisa é copiar/mover 10 elementos e outra é fazer o mesmo com um milhão de elementos.

Em outras palavras, se operações de inserção/remoção no meio da lista são mais comuns em seu programa, LinkedList deve ser mais rápido que ArrayList .

Em teoria

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Saída: Tempo gasto por LinkedList (em milissegundos) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Saída: Tempo gasto por ArrayList (em milissegundos) = 181 Isso foi inesperado! Realizamos uma operação onde LinkedList deveria ser muito mais eficiente: inserir 100 itens no meio de uma lista. E nossa lista é enorme: 5.000.000 de elementos. ArrayList teve que deslocar alguns milhões de itens a cada inserção! Como ganhou? Primeiro, o tempo necessário para ArrayList acessar os elementos é fixo (constante). Quando você escreve

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

então ArrayList [2_000_000] é um endereço de memória específico (afinal, a lista possui um array interno). Mas, um LinkedList não possui um array. Ele procurará o elemento número 2_000_000 ao longo da cadeia de links. Para LinkedList, este não é um endereço de memória, mas um link que ainda precisa ser alcançado: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next……… Como resultado, durante cada inserção (remoção) no meio da lista , ArrayList já sabe o endereço de memória exato para acessar, mas LinkedList ainda precisa "chegar lá". Em segundo lugar, há a estrutura do ArrayListem si. Uma função interna especial ( System.arrayCopy() ) expande o array interno e copia e desloca todos os elementos. É muito rápido, porque é otimizado para este trabalho específico. Mas quando você não precisa "chegar" a um determinado índice, o LinkedList é o vencedor. Suponha que inserimos no início da lista. Vamos tentar inserir um milhão de elementos lá:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

Saída: O resultado em milissegundos: 43448 O resultado em milissegundos: 107 Agora obtemos um resultado totalmente diferente! ArrayList gastou mais de 43 segundos inserindo um milhão de itens na frente da lista, enquanto LinkedList conseguiu fazer isso em 0,1 segundos! LinkedList se beneficiou aqui, porque não precisou percorrer toda a cadeia de links até o meio da lista. Ele encontra imediatamente o índice necessário no início da lista, então o algoritmo diferente já é uma vantagem. :) Na verdade, a discussão " ArrayList versus LinkedList " é muito difundida e não vamos nos aprofundar nela no nível atual. A principal coisa que você precisa lembrar é o seguinte:

Nem todas as vantagens teóricas de qualquer coleção em particular sempre funcionam na realidade (vimos isso com o exemplo envolvendo o meio da lista)
Não adote uma posição extrema na hora de escolher uma coleção (" ArrayList é sempre mais rápido. Use e não vai errar. Ninguém usa LinkedList há muito tempo").

Embora até mesmo o autor do LinkedList , Joshua Bloch, diga que esse é o caso. :) Ainda assim, essa perspectiva está longe de ser 100% correta e nos convencemos disso. Em nosso exemplo anterior, LinkedList foi 400 (!) vezes mais rápido. Outra coisa é que realmente existem poucas situações em que o LinkedList é a melhor escolha. Mas eles existem, e no momento certo LinkedListpode recompensá-lo generosamente. Não se esqueça do que dissemos no início da lição: as estruturas de dados mais eficientes são diferentes para tarefas diferentes. É impossível ter 100% de certeza de qual estrutura de dados será a melhor até que você conheça todas as condições de sua tarefa. Você saberá mais sobre essas coleções posteriormente, o que facilitará a escolha. Mas a opção mais simples e eficaz é sempre a mesma: experimente ambos nos dados reais usados em seu programa. Então você será capaz de ver por si mesmo como ambos os tipos de listas funcionam e você definitivamente não errará. :) Para reforçar o que você aprendeu, sugerimos que você assista a uma vídeo aula do nosso Curso de Java

Mais leitura:
Estrutura de Dados Java LinkedList