Introdução à coleção LinkedList

1. História deLinkedList

Java tem outra classe de coleção que Java herdou da linguagem C++. Esta é a LinkedListclasse que implementa uma "lista encadeada".

Externamente, a LinkedListparece ser o mesmo que um arquivo ArrayList. A LinkedListclasse tem todos os mesmos métodos que a ArrayListclasse. Em princípio, você sempre pode usar a LinkedListem vez de an ArrayListe tudo funcionará.

Então, por que precisamos de outra classe de lista?

A resposta tem tudo a ver com a estrutura interna da LinkedListclasse. Em vez de um array, ele usa uma lista duplamente encadeada . Vamos explicar o que é isso um pouco mais tarde.

A LinkedListdiferente estrutura interna da classe torna mais rápida a inserção de elementos no meio da lista.

Na Internet, muitas vezes você pode encontrar comparações das classes ArrayListe LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Tudo parece bastante claro: se você precisar inserir elementos na lista com frequência, use LinkedList; se raramente, use ArrayList. Mas a realidade é um pouco diferente.

2. Ninguém usaLinkedList

Ninguém usa LinkedList.

Até o autor da LinkedListaula twittou recentemente: "Alguém realmente usa LinkedList? Eu escrevi e nunca uso."

Então, qual é o problema?

Primeiro, a ArrayListturma começou a conseguir inserir elementos no meio da lista muito rapidamente. Ao inserir um elemento no meio da lista, você deve deslocar todos os elementos após o ponto de inserção em 1 no final da lista. Isso costumava levar tempo.

Mas agora tudo mudou. Todos os elementos de um array estão próximos uns dos outros no mesmo bloco de memória, então a operação para deslocar os elementos é realizada por um comando muito rápido de baixo nível: .System.arraycopy()

Além disso, os processadores de hoje têm um cache grande que geralmente pode conter todo o array, o que permite que os elementos do array sejam deslocados dentro do cache em vez de na memória. Um milhão de elementos são facilmente deslocados em um único milissegundo.

Em segundo lugar, a LinkedListclasse pode inserir elementos rapidamente se você inseri-los usando um iterador. Se você usar um iterador para passar por um LinkedListe inserir constantemente novos elementos (ou remover os existentes), a operação é super rápida.

Se você simplesmente adicionar elementos a um LinkedListobjeto dentro de um loop, cada operação de inserção rápida será acompanhada por uma operação lenta de "obter elemento".

A realidade é bem mais próxima disso:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Por que obter um elemento de uma LinkedListoperação tão lenta?

Você pode responder a essa pergunta depois de se familiarizar um pouco com LinkedLista estrutura.

3. Como LinkedListestá estruturado

LinkedListtem uma estrutura interna diferente de ArrayList. Não possui um array interno para armazenar elementos. Em vez disso, ele usa uma estrutura de dados chamada doublely inked list .

Cada elemento de uma lista duplamente encadeada armazena uma referência ao elemento anterior e ao próximo elemento. Isso é como uma fila em uma loja, onde cada pessoa se lembra da pessoa que está à sua frente e também da pessoa que está atrás dela.

É assim que essa lista se parece na memória:

A cabeça e a cauda (células com fundo cinza) são as variáveis first​​e last, que armazenam referências a Nodeobjetos.

No meio, você tem uma cadeia de Nodeobjetos (objetos, não variáveis). Cada um deles é composto por três campos:

• prev— armazena uma referência (link) ao Nodeobjeto anterior (células com fundo amarelo).
• value— armazena o valor deste elemento da lista (células com fundo verde).
• next— armazena uma referência (link) para o próximo Nodeobjeto (células com fundo azul)

O segundo objeto (endereço F24) é o próximo ( next) para o primeiro objeto e o anterior ( prev) para o terceiro objeto. O campo amarelo do terceiro objeto contém o endereço F24 e o campo azul do primeiro objeto contém o endereço F24.

As setas do primeiro e terceiro objetos apontam para o mesmo segundo objeto. Portanto, seria mais correto desenhar as setas assim.

4. Insira um elemento em uma lista encadeada

Para adicionar alguém à linha assim, você só precisa obter a permissão de duas pessoas próximas uma da outra. A primeira pessoa se lembra do recém-chegado como "a pessoa atrás de mim" e a segunda pessoa se lembra dele como "a pessoa na minha frente".

Tudo o que você precisa fazer é alterar as referências dos dois objetos vizinhos:

Adicionamos um novo item à nossa lista alterando as referências do segundo e terceiro objetos. O novo objeto é o próximo para o antigo segundo objeto e o anterior para o antigo terceiro objeto. E, claro, o próprio novo objeto precisa armazenar as referências corretas: seu objeto anterior é o antigo segundo objeto e seu próximo objeto é o antigo terceiro objeto.

Remover um elemento é ainda mais fácil: se quisermos remover, digamos, o 100º objeto da lista, basta alterar o campo do 99º objeto nextpara que aponte para o 101º objeto e alterar o prevcampo do 101º objeto para que aponte para o 99º. É isso.

Mas conseguir o 100º objeto não é tão fácil.

5. Remova um elemento de uma lista

Para obter o 100º elemento de uma lista encadeada, você precisa:

Obtenha o primeiro objeto: você faz isso usando a firstvariável no LinkedListobjeto. O nextcampo do 1º objeto armazena uma referência ao 2º objeto. É assim que obtemos o segundo objeto. O segundo objeto tem uma referência ao terceiro, e assim por diante.

Se precisarmos obter uma referência ao 100º objeto, precisamos mover sequencialmente por todos os objetos do 1º ao 100º. E se precisarmos do milionésimo elemento em uma lista, precisamos iterar mais de um milhão de objetos um após o outro!

E se esses objetos foram adicionados à lista em momentos diferentes, eles estarão localizados em diferentes partes da memória e é improvável que acabem no cache do processador ao mesmo tempo. Isso significa que iterar sobre os elementos de uma lista encadeada não é apenas lento, mas muito lento.

É com isso que estamos lidando.

Então, por que estamos ensinando como LinkedListfunciona essa lentidão?

Bem, durante as entrevistas de emprego, você será questionado sobre como LinkedListdifere deArrayList . Definitivamente.