O que é melhor usar: ArrayList ou LinkedList, se eu quiser remover um elemento do meio da lista?

ArrayList.

Ao remover um elemento do meio da lista:

• ArrayList: Requer deslocar todos os elementos seguintes, o que no pior caso (ao remover o primeiro elemento) leva tempo $O(n)$, onde $n$ é o número de elementos. No entanto, em média, a operação mantém-se $O(n)$, pois apenas é necessário deslocar metade dos elementos. O desempenho real costuma ser melhor devido a uma melhor localidade dos dados.
• LinkedList: Requer iterar pelos elementos até encontrar o nó desejado ($O(n)$ no pior caso, se a iteração começar do início ou do fim). Após encontrar o nó, removê-lo leva $O(1)$.

Embora remover o nó em si na LinkedList seja mais rápido, procurar o nó antes de removê-lo torna a operação em média mais lenta do que no ArrayList.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListRemovalComparison {

    public static void main(String[] args) {
        int size = 100000; // Tamanho da lista
        int removeIndex = size / 2; // Índice para remoção (meio)

        // ArrayList
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
        }

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Remoção do meio
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("Tempo de remoção do ArrayList: " + durationArrayList + " ns");

        // LinkedList
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            linkedList.add(i);
        }

        long startTimeLinkedList = System.nanoTime();
        linkedList.remove(removeIndex); // Remoção do meio
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("Tempo de remoção do LinkedList: " + durationLinkedList + " ns");
    }
}

Os resultados do benchmark mostram que, para remover um elemento do meio, o ArrayList geralmente é mais rápido, apesar da complexidade teórica do deslocamento. Isto deve-se ao fato de a busca por índice na LinkedList ($O(n)$) ser mais lenta do que o deslocamento no ArrayList.

// ArrayList - acesso por índice O(1), remoção O(n) (deslocamento)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // Remoção de "B" - requer deslocar "C"

// LinkedList - acesso por índice O(n), remoção O(1) (após encontrar o nó)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // Remoção de "B" - primeiro é preciso encontrar o nó "B" (O(n)), depois remover (O(1))

Resumindo, para a operação de remoção do meio, se souber o índice, o ArrayList costuma ser uma escolha mais preferida devido à operação de acesso mais rápida por índice, o que compensa os custos do deslocamento.