Diferentemente de arrays, os elementos não são armazenados de forma contígua, mas ligados por referências.

Cada nó em uma LinkedList contém:

• Dado: o valor armazenado (ex.: "A", "B").

• Referência ao próximo: aponta para o próximo nó.

• Referência ao anterior (em uma lista duplamente ligada): aponta para o nó anterior.

Exemplo da vida real

Imagine uma corrente: cada elo (nó) conhece apenas o próximo (e, em uma lista duplamente ligada, também o anterior). Isso permite adicionar ou remover elos facilmente no início ou fim, sem mover os outros.

Exemplos práticos de uso da LinkedList

• Navegação em playlists de música: avançar ou retroceder faixas.

• "Desfazer" (undo) em editores de texto: armazenar estados anteriores.

• Gerenciamento de processos em sistemas operacionais: filas de execução.

• Fila de impressão: como uma Queue.

• Cache ou buffers de dados: inserções/remoções frequentes.

LinkedList em Java

A classe LinkedList, do pacote java.util, implementa uma lista duplamente ligada, onde cada nó conhece o anterior e o próximo.

Como usar como Lista

import java.util.LinkedList;

public class LinkedListExemplo {
    public static void main(String[] args) {
        LinkedList<String> lista = new LinkedList<>();

        lista.add("A");
        lista.add("B");
        lista.add("C");

        System.out.println(lista.get(1)); // "B"

        lista.remove("B"); // Remove o elemento "B"
        lista.addFirst("X"); // Adiciona no início
        lista.addLast("Z");  // Adiciona no fim

        // Iteração com for-each
        for (String item : lista) {
            System.out.println(item); // X, A, C, Z
        }

        // Iteração com Iterator
        Iterator<String> iterator = lista.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next()); // X, A, C, Z
        }
    }
}

Como usar como Fila

import java.util.LinkedList;
import java.util.Queue;

public class FilaExemplo {
    public static void main(String[] args) {
        Queue<String> fila = new LinkedList<>();

        fila.offer("A");
        fila.offer("B");
        fila.offer("C");

        System.out.println(fila.poll()); // "A"
    }
}

Como usar como Pilha

import java.util.LinkedList;

public class PilhaExemplo {
    public static void main(String[] args) {
        LinkedList<String> pilha = new LinkedList<>();

        pilha.push("A");
        pilha.push("B");
        pilha.push("C");

        while (!pilha.isEmpty()) {
            System.out.println(pilha.pop()); // C, B, A
        }
    }
}

Vantagens

• Versatilidade: atua como lista, fila ou pilha.

• Inserções/remoções rápidas no início e no fim: O(1) para essas operações.

• Suporte nativo a operações: addFirst(), addLast(), removeFirst(), removeLast().

• Permite elementos null.

Desvantagens

• Acesso por índice lento: O(n), pois percorre a lista até o elemento desejado.

• Maior consumo de memória: armazena referências prev e next para cada nó, ao contrário de estruturas baseadas em array (como ArrayList).

• Não é segura para threads: requer sincronização manual em ambientes concorrentes.

Comparações

LinkedList vs ArrayList

Quando usar LinkedList:Se o foco for inserções e remoções frequentes nas extremidades, a LinkedList é ideal.

Quando evitar:Se precisar acessar elementos por índice frequentemente, prefira ArrayList.

Operações Avançadas

A LinkedList suporta métodos avançados, como:

• Iteração reversa com descendingIterator():

public class ReversaExemplo {
  public static void main(String[] args) {
    Iterator<String> descIterator = lista.descendingIterator();
    while (descIterator.hasNext()) {
        System.out.println(descIterator.next()); // Z, C, A, X
    }
  }
}

• ListIterator para navegação bidirecional:

public class ListIteratorExemplo {
  public static void main(String[] args) {
    ListIterator<String> listIterator = lista.listIterator();
    while (listIterator.hasNext()) {
      System.out.println(listIterator.next());
    }
    while (listIterator.hasPrevious()) {
      System.out.println(listIterator.previous());
    }
  }
}

Erros Comuns

• Acesso por índice em loops: usar get(i) em loops é lento (O(n) por acesso).

public class LoopExemplo {
  public static void main(String[] args) {
    // Evite
    for (int i = 0; i < lista.size(); i++) {
      System.out.println(lista.get(i));
    }
    // Prefira
    for (String item : lista) {
      System.out.println(item);
    }   
  }
}

• Não verificar lista vazia: chamar pop() ou poll() em uma lista vazia pode lançar exceção.

  if (!lista.isEmpty()) {
      String item = lista.pop();
  }

• Modificações concorrentes: alterar a lista durante iteração causa ConcurrentModificationException.

  Iterator<String> iterator = lista.iterator();
  while (iterator.hasNext()) {
      String item = iterator.next();
      // Use iterator.remove() em vez de lista.remove(item)
      iterator.remove();
  }

Sincronização para Concorrência

A LinkedList não é segura para threads. Para usá-la em ambientes concorrentes, sincronize manualmente:

import java.util.Collections;

LinkedList<String> lista = new LinkedList<>();
List<String> threadSafeList = Collections.synchronizedList(lista);

// Ou use CopyOnWriteArrayList para cenários específicos
import java.util.concurrent.CopyOnWriteArrayList;
List<String> copyOnWriteList = new CopyOnWriteArrayList<>();

Boas Práticas

• Use tipos genéricos: evite erros em tempo de execução.

  LinkedList<String> lista = new LinkedList<>(); // Correto
  LinkedList listaRaw = new LinkedList(); // Evite

• Prefira métodos específicos: use addFirst()/addLast() em vez de add(0)/add(size()) para melhor desempenho.

• Verifique lista vazia: antes de chamar pop(), poll() ou peek().

• Evite modificações concorrentes: use Iterator ou ListIterator para remoções seguras durante iteração.

Comparação de Desempenho

Nota: ArrayDeque é geralmente preferido para filas e pilhas devido à eficiência e menor consumo de memória. A LinkedList é usada quando se precisa de suporte à interface List ou compatibilidade com APIs legadas.

Estrutura Visual da LinkedList

A LinkedList pode ser visualizada assim:

[null]<--[X|prev|next]<-->[A|prev|next]<-->[C|prev|next]<-->[Z|prev|next]-->null

• Cada nó armazena o dado (X, A, etc.) e ponteiros para o nó anterior (prev) e próximo (next).

• O primeiro nó tem prev = null, e o último tem next = null.

Resumo Prático

• Use LinkedList para inserções/remoções rápidas no início ou fim.

• Evite quando o acesso aleatório por índice for frequente.

• Alternativa eficiente: prefira ArrayDeque para filas ou pilhas, exceto quando precisar da interface List.

• Sincronização: use Collections.synchronizedList() em ambientes concorrentes.

Conclusão

A LinkedList é uma estrutura poderosa e flexível na biblioteca Java, ideal para cenários com manipulações frequentes nas extremidades. Apesar de seu acesso por índice ser lento, ela brilha em operações como addFirst(), addLast(), push() e pop(). Para casos onde a eficiência de memória ou acesso rápido por índice é crucial, considere ArrayList ou ArrayDeque.

Powered by wisp