LinkedList em Java

Olá! Todas as palestras recentes foram dedicadas ao estudo da lista ArrayList . Esta estrutura de dados é muito conveniente e permite resolver muitos problemas. No entanto, Java possui muitas outras estruturas de dados. Por que? Em primeiro lugar, porque a gama de tarefas existentes é muito ampla e, para diferentes tarefas, diferentes estruturas de dados são mais eficazes . Hoje conheceremos uma nova estrutura - uma lista duplamente vinculada LinkedList . Vamos descobrir como funciona, por que é chamado de duplamente conectado e como difere de ArrayList . Em uma LinkedList, os elementos são, na verdade, links de uma cadeia. Cada elemento, além dos dados que armazena, possui um link para o elemento anterior e o próximo . Esses links permitem que você passe de um elemento para outro. É criado assim:

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

Conclusão:

[Hello World! My name is Earl, I love Java, I live in Moscow]

A estrutura da nossa lista ficará assim: Vamos ver como um novo elemento é adicionado. Isso é feito usando o add().

earlBio.add(str2);

No momento desta linha de código, nossa lista consiste em um elemento – a string str1. Vamos ver o que acontece a seguir na imagem: Como resultado str2, e str1se conectar através dos links armazenados neles nexte previous: Agora você deve entender a ideia principal de uma lista duplamente vinculada. Os elementos LinkedListformam uma lista única justamente graças a esta cadeia de links. Não há array dentro de LinkedList, como in ArrayList, ou algo semelhante. Todo o trabalho com ArrayList (em geral) se resume a trabalhar com o array interno. Todo o trabalho LinkedListse resume à mudança de links. Isso é visto claramente adicionando um elemento ao meio da lista:

public class Main {

   public static void main(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 Moscow");

       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 sobrecarregado add()permite especificar um índice específico para o novo elemento. Neste caso, queremos adicionar uma linha str2entre str1e str3. Isto é o que acontecerá dentro: E como resultado da alteração dos links internos, o elemento str2é adicionado com sucesso à lista: Agora todos os 3 elementos estão vinculados. Do primeiro elemento da cadeia nextvocê pode ir até o último e voltar. Já descobrimos mais ou menos a inserção, mas e quanto à exclusão de elementos? O princípio de funcionamento é o mesmo. Simplesmente redefinimos as ligações dos dois elementos “nas laterais” daquele que está sendo removido:

public class Main {

   public static void main(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 Moscow");

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

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

Isto é o que acontecerá se excluirmos o elemento com índice 1 (está no meio da lista): Após redefinir os links, obtemos o resultado desejado: Ao contrário da exclusão, ArrayListnão há deslocamentos de elementos do array e assim por diante. Simplesmente redefinimos as referências dos elementos str1e str3. Agora eles apontam um para o outro, e o objeto str2“saiu” dessa cadeia de elos e não faz mais parte da lista.

Visão geral dos métodos

Tem LinkedListmuitas semelhanças com ArrayListos métodos. Por exemplo, métodos como add(), remove(), indexOf(), clear(), contains()(é o elemento contido na lista), set()(inserir um elemento com substituição) size()estão presentes em ambas as classes. Embora (como descobrimos no exemplo add()e remove()) muitos deles funcionem de maneira diferente internamente, no final das contas eles fazem a mesma coisa. Porém, LinkedListpossui métodos separados para trabalhar com o início e o fim da lista, que não estão presentes em ArrayList:

• addFirst(), addLast(): 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 + '\'' +
               '}';
   }
}

Conclusão:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
[Car{model='Ford Mondeo'}, Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]

Com isso, a Ford acabou no topo da lista e a Fiat no final.

• peekFirst(), peekLast(): retorna o primeiro/último elemento da lista. Retorne nullse 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());
}

Conclusão:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}

• pollFirst(), pollLast(): retorna o primeiro/último elemento da lista e remove-o da lista . Retornar nullse 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 left on the list?");
   System.out.println(cars);
}

Conclusão:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]

• toArray(): retorna uma matriz de elementos 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));
}

Conclusão:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]

Agora sabemos como funciona LinkedListe como difere do ArrayList. Quais são os benefícios de usar LinkedList? Em primeiro lugar, ao trabalhar com o meio da lista . Inserir e excluir no meio LinkedListé muito mais simples do que no ArrayList. Simplesmente redefinimos os links dos elementos vizinhos, e o elemento desnecessário “cai” da cadeia de links. Enquanto estamos em ArrayListnós:

• verifique se há espaço suficiente (ao inserir)
• se não for suficiente, crie um novo array e copie os dados lá (ao colar)
• excluir/inserir um elemento e deslocar todos os outros elementos para a direita/esquerda (dependendo do tipo de operação). Além disso, a complexidade deste processo depende muito do tamanho da lista. Uma coisa é copiar/mover 10 elementos, outra é fazer o mesmo com um milhão de elementos.

Ou seja, se no seu programa as operações de inserção/exclusão ocorrerem com mais frequência com o meio da lista, LinkedListela deverá ser mais rápida 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 to run for LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Conclusão:

Время работы для LinkedList (в мorсекундах) = 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 to run for ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Conclusão:

Время работы для ArrayList (в миллисекундах) = 181

De repente! Parece que estávamos realizando uma operação que LinkedListdeveria ser muito mais eficiente - inserir 100 elementos no meio da lista. E nossa lista é enorme - 5.000.000 de elementos: ArrayListtivemos que deslocar alguns milhões de elementos cada vez que os inserimos! Qual é o motivo de sua vitória? Primeiro, um elemento é acessado em ArrayListum período fixo de tempo. Quando você indica:

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

então no caso de ArrayList[2_000_000] este é um endereço específico na memória, pois possui um array dentro. Enquanto a LinkedListmatriz não. Ele procurará o elemento número 2_000_000 ao longo da cadeia de links. Para ele, este não é um endereço na 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………

Com isso, a cada inserção (exclusão) no meio da lista, ArrayListele já sabe o endereço exato na memória ao qual deve acessar, mas LinkedListainda precisa “descobrir” o lugar certo. Em segundo lugar , a questão está na estrutura de ArrayList'a em si. A expansão da matriz interna, a cópia de todos os elementos e a mudança de elementos são realizadas por uma função interna especial - System.arrayCopy(). Funciona muito rapidamente porque é especialmente otimizado para este trabalho. Mas em situações em que não há necessidade de “pisar” no índice desejado, LinkedListele realmente se mostra melhor. Por exemplo, se a inserção ocorrer no início da lista. Vamos tentar inserir um milhão de elementos aí:

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("Result in milliseconds: " + msDelay);
       return msDelay;

   }

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

}

Conclusão:

Результат в миллисекундах: 43448
Результат в миллисекундах: 107

Um resultado completamente diferente! Demorou mais de 43 segundos para inserir um milhão de elementos no início da lista ArrayList, enquanto LinkedListfoi concluído em 0,1 segundos! Foi precisamente o facto de nesta situação LinkedListnão termos de “percorrer” todas as vezes a cadeia de elos até ao meio da lista. Ele imediatamente encontrou o índice necessário no início da lista, e aí a diferença nos princípios de funcionamento já estava do seu lado :) Na verdade, a discussão “ ArrayListversus LinkedList” é muito difundida, e não vamos nos aprofundar nisso no momento nível. A principal coisa que você precisa lembrar:

• Nem todas as vantagens de uma determinada coleção “no papel” funcionarão na realidade (vimos isso usando o exemplo do meio da lista)
• Não se deve ir a extremos na hora de escolher uma coleção (“ ArrayListé sempre mais rápido, use e não se enganará. LinkedListNinguém usa há muito tempo”).

Embora até o criador LinkedListJoshua Bloch o diga :) No entanto, este ponto de vista está longe de ser 100% correto e estamos convencidos disso. No nosso exemplo anterior LinkedListfuncionou 400 (!) vezes mais rápido. Outra coisa é que são poucas as situações em que LinkedListessa seria a melhor escolha. Mas eles existem e, no momento certo, LinkedListpodem ajudá-lo seriamente. Não se esqueça do que falamos no início da palestra: diferentes estruturas de dados são mais eficazes para diferentes tarefas. É impossível dizer com 100% de confiança qual estrutura de dados será melhor até que todas as condições do problema sejam conhecidas. Posteriormente você saberá mais sobre essas coleções e será mais fácil fazer uma escolha. Mas a opção mais simples e eficaz é sempre a mesma: testar ambos em dados reais do seu programa. Então você poderá ver com seus próprios olhos os resultados de ambas as listas e definitivamente não irá errar :)