Quais são as principais diferenças entre LinkedList e ArrayList em Java?

As principais diferenças entre LinkedList e ArrayList residem na sua estrutura de dados interna e, consequentemente, no desempenho de várias operações:

Estrutura interna:

• ArrayList usa um array dinâmico para armazenar elementos.
• LinkedList usa uma lista duplamente ligada, onde cada nó contém dados e referências aos nós anterior e seguinte.

Desempenho das operações:

Operação	ArrayList	LinkedList	Razão
Adicionar ao final	O(1)	O(1)	No ArrayList, geralmente há espaço, no LinkedList, é fácil adicionar um novo nó ao final.
Adicionar ao início ou no meio	O(n)	O(1)	No ArrayList, é necessário deslocar elementos. No LinkedList, basta alterar algumas referências.
Remover do final	O(1)	O(1)	No ArrayList, não há deslocamento. No LinkedList, é fácil remover o último nó.
Remover do início ou no meio	O(n)	O(1)	No ArrayList, é necessário deslocar elementos. No LinkedList, basta alterar algumas referências.
Obter elemento por índice	O(1)	O(n)	No ArrayList, acesso direto por índice. No LinkedList, é necessário percorrer a lista.
Procurar elemento	O(n)	O(n)	Requer escanear toda a lista em ambos os casos.

Uso de memória:

• LinkedList geralmente consome mais memória devido ao armazenamento adicional de referências aos nós anterior e seguinte.

Aplicabilidade:

• ArrayList é preferido quando as operações de acesso por índice e adição/remoção no final são frequentes.
• LinkedList é preferido quando as operações frequentes são adicionar ou remover elementos no início ou no meio da lista.

Exemplo: Adicionar no início

// ArrayList
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add(0, "First"); // O(n) - deslocamento de elementos existentes

// LinkedList
LinkedList<String> linkedList = new LinkedList<>();
linkedList.addFirst("First"); // O(1) - apenas alteração de referências