Что лучше использовать: ArrayList или LinkedList, если я хочу удалить элемент из середины списка?

ArrayList.

При удалении элемента из середины списка:

• ArrayList: Требует смещения всех последующих элементов, что в худшем случае (при удалении первого элемента) занимает время $О(n)$, где $n$ — количество элементов. Однако, в среднем, операция остается $О(n)$, так как нужно сместить только половину элементов. Фактическая производительность часто выше из-за лучшей локальности данных.
• LinkedList: Требует итерации по элементам до нахождения нужного узла ($O(n)$ в худшем случае, если итерация начинается с начала или конца). После нахождения узла удаление занимает $О(1)$.

Несмотря на то, что удаление самого узла в LinkedList быстрее, поиск узла до удаления делает общую операцию в среднем медленнее, чем в 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; // Размер списка
        int removeIndex = size / 2; // Индекс для удаления (середина)

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

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Удаление из середины
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("Время удаления из 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); // Удаление из середины
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("Время удаления из LinkedList: " + durationLinkedList + " ns");
    }
}

Результаты бенчмарка показывают, что для удаления элемента из середины, ArrayList, как правило, быстрее, несмотря на теоретическую сложность сдвига. Это связано с тем, что поиск элемента по индексу в LinkedList ($O(n)$) выполняется медленнее, чем сдвиг в ArrayList.

// ArrayList - доступ по индексу O(1), удаление O(n) (сдвиг)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // Удаление "B" - требует сдвига "C"

// LinkedList - доступ по индексу O(n), удаление O(1) (после нахождения узла)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // Удаление "B" - сначала нужно найти узел "B" (O(n)), затем удалить (O(1))

В итоге, для операции удаления из середины, если вы знаете индекс, ArrayList часто является более предпочтительным выбором из-за более быстрой операции доступа по индексу, что компенсирует затраты на сдвиг.