ArrayList implementa a interface List usando um array, provavelmente um Object[].
LinkedList usa uma lista-ligada para implementar List.
Na dúvida sobre oque uma lista-ligada venha a ser, consulte qualquer livro elementar de estruturas de dados.
Quanto a qual usar depende das caracteristicas do teu programa:
-Insere e remove somente do final da lista? ArrayList
-Usa acesso aleatorico, List.get(i)? ArrayList
-Insere e remove do começo e do meio da lista? LinkedList
-Precisa usar o menos possivel de memoria? ArrayList
“Subjetivando” a resposta, a LinkedList organiza automaticamente a lista no caso você inserir um valor em uma posição que não seja no final da lista (ou seja, usando o add() do ArrayList, o valor adicionado vai para o final, enquanto no LinkedList, você pode escolher a posição para o novo item). Estou certo?
A interface List indica que tanto ArrayList quanto o LinkedList podem inserir, normalmente no final, ou em qualquer local arbitrário.
A diferença entre os dois nesse caso de inserção, é que o ArrayList pode precisar de um tempo a mais para expandir o seu espaço interno e/ou mover os elementos de lugar para comportar novos elementos. O LinkedList por outro lado, pode demorar mais que o ArrayList para criar um nó e ligar aos nós adjacentes, fora o seek que é bem mais lento também.
LinkedList também pode ser usada como uma Deque, com operações FIFO para ambos os lados, ou com uma Stack, com operações LIFO, apesar que a ArrayDeque pode ser mais rápida que ela em ambas as situações.