Какую реализацию List в Java выбрать для частого удаления элементов из середины списка?

Для частого удаления элементов из произвольных позиций (не только начала/конца) в однопоточном приложении лучше использовать LinkedList.

Почему LinkedList?

• Сложность O(1): После нахождения нужного узла (что само по себе O(n)), операция удаления в LinkedList выполняется за константное время. Нужно лишь перенаправить ссылки у соседних узлов.
• Нет сдвига данных: В отличие от массива, не требуется перемещение последующих элементов.

Почему не ArrayList? В ArrayList удаление элемента из середины требует сдвига всех последующих элементов на одну позицию, что является операцией O(n).

Пример:

// LinkedList - эффективное удаление из середины
List<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B"); // Узел для удаления
linkedList.add("C");
linkedList.remove(1); // Быстро: меняются ссылки B->A и B->C

// ArrayList - неэффективное удаление из середины
List<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B"); // Элемент для удаления
arrayList.add("C");
arrayList.add("D");
arrayList.remove(1); // Медленно: элементы "C" и "D" сдвигаются влево

Компромисс: LinkedList проигрывает в скорости доступа по индексу (O(n)). Если нужны и частые удаления, и частый доступ по индексу, возможно, стоит рассмотреть другую структуру данных (например, TreeSet или CopyOnWriteArrayList для многопоточности).