¿Qué es mejor usar: ArrayList o LinkedList, si quiero eliminar un elemento del medio de la lista?

ArrayList.

Al eliminar un elemento del medio de la lista:

• ArrayList: Requiere desplazar todos los elementos posteriores, lo cual en el peor caso (al eliminar el primer elemento) lleva tiempo $O(n)$, donde $n$ es la cantidad de elementos. Sin embargo, en promedio, la operación sigue siendo $O(n)$, ya que solo es necesario desplazar la mitad de los elementos. El rendimiento real suele ser mejor debido a una mejor localización de datos.
• LinkedList: Requiere iterar por los elementos hasta encontrar el nodo deseado ($O(n)$ en el peor caso, si la iteración comienza desde el principio o el final). Después de encontrar el nodo, eliminarlo toma $O(1)$.

Aunque eliminar el nodo en sí en LinkedList es más rápido, buscar el nodo antes de eliminarlo hace que la operación en promedio sea más lenta que en 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; // Tamaño de la lista
        int removeIndex = size / 2; // Índice para eliminar (el medio)

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

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Eliminación del medio
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("Tiempo de eliminación de 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); // Eliminación del medio
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("Tiempo de eliminación de LinkedList: " + durationLinkedList + " ns");
    }
}

Los resultados del benchmark muestran que, para eliminar un elemento del medio, ArrayList generalmente es más rápido, a pesar de la complejidad teórica del desplazamiento. Esto se debe a que la búsqueda por índice en LinkedList ($O(n)$) es más lenta que el desplazamiento en ArrayList.

// ArrayList - acceso por índice O(1), eliminación O(n) (desplazamiento)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // Eliminación de "B" - requiere desplazar "C"

// LinkedList - acceso por índice O(n), eliminación O(1) (después de encontrar el nodo)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // Eliminación de "B" - primero hay que encontrar el nodo "B" (O(n)), luego eliminar (O(1))

En resumen, para la operación de eliminar del medio, si conoces el índice, ArrayList suele ser la opción más recomendable debido a su operación de acceso más rápida por índice, lo que compensa los costos del desplazamiento.