LinkedList.

Serie - Fundamentos de Estrutura de Dados Elementar com Java.

LinkedList. Como funciona o Doubly-linked List.

  A estrutura de dados do LinkedList é sim uma Linked List (ou Lista Ligada), porém de forma mais rigorosa, ela é mais especificamente uma Doubly-linked List (ou Lista Duplamente Ligada).

  A Doubly-linked List funciona no Java, através de um objeto chamado Node, podemos vê-lo aqui no código fonte do Java:

Node(Node<E> prev, E element, Node<E> next)
  { ... }

  De forma rudimentar, o parametro element é o value, ou seja, o objeto que está sendo armazenado. Já os paramentros prev e next, funcionam como ponteiros, sendo respectivamente prev (previous) quem aponta para o node anterior, e next quem aponta para o próximo node que está a sua frente.

  Isso significa que cada node possui seu element e ponteiros para seu próximo e anterior node.

  exemplo em código:

final var __ = " ; size: ";
var numbersLinkedList = new LinkedList<Integer>();
numbersLinkedList.addAll(Arrays.asList(
  4,6,8,9
));
System.out.println(numbersLinkedList+__+numbersLinkedList.size());

  Vale ressaltar que, para adição, o LinkedList é muito rápido, pois não precisa se redimensionar, internamente ele não usa um array como ArrayList, ele armazena no baixo nivel os nodes em locais como a Heap, como a Heap é dinâmica, os nodes simplesmente são armazenados lá, e para encontrarmos é via ponteiro dos outros nodes.

  exemplo em código:

final var __ = " ; size: ";
var numbersLinkedList = new LinkedList<Integer>();
numbersLinkedList.addAll(Arrays.asList(
  4,6,8,10
));
System.out.println(numbersLinkedList+__+numbersLinkedList.size());
numbersLinkedList.add(3, 9);
System.out.println(numbersLinkedList+__+numbersLinkedList.size());

  Como pode ver, além do novo node, foi preciso apenas alterar dois ponteiros de outros nodes. Para se ter ideia, LinkedList é cerca de 9x mais rápido que ArrayList no quesito adição que não seja no final da estrutura de dados. Afinal de contas, em listas ligadas, seus itens podem estar em qualquer lugar da memória.

  Porém como nada é bala de prata, LinkedList é pessimo no quesito para fazer busca na estrutura de dados, pois para fazer search ele precisa fazer equals em for em todos os nodes, mesmo que o ArrayList faça o mesmo, ainda assim o LinkedList é cerca de 130x pior que o ArrayList em search, pois diferentemento do ArrayList que é sequencial (o que facilita em fazer search), o LinkedList vai precisar verificar Node a Node, para isso ira em cada Node, ver se corresponde ao element procurado, caso contrario vai precisar verificar o ponteiro do próximo Node, ir no endereço da memória, e repetir o processo. Quanto maior for a LinkedList, pior vai ser para fazer search.

Vantagens e Desvantagens

Vantagens

• 1 - Eficiente para inserções e remoções frequentes, inclusive em posições aleatórias, pois não requer realocação de memória.
• 2 - Suporta eficientemente operações de remoção e inserção no meio da lista.

Desvantagens

• 1 - O acesso direto aos elementos é mais lento do que em ArrayList devido à necessidade de percorrer os Nodes sequencialmente, ou melhor, não existe operação de busca por índice.

Uso comum

  Implementação de listas encadeadas para operações eficientes de inserção e remoção.

  Cenário de uso: Em um editor de texto colaborativo em tempo real, uma LinkedList pode ser usada para representar a sequência de caracteres, permitindo inserções e remoções eficientes em qualquer posição do texto.