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

Для частых операций вставки (или удаления) в середину списка оптимальным выбором является LinkedList.

Почему LinkedList быстрее для вставки? LinkedList реализован как двусвязный список. Каждый элемент (Node) содержит ссылки на предыдущий и следующий узлы. Вставка в известную позицию требует лишь обновления ссылок соседних узлов.

Пример вставки в середину LinkedList:

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "C", "D"));
ListIterator<String> iterator = list.listIterator();

// Итератор позволяет эффективно находить позицию и вставлять
while (iterator.hasNext()) {
    if (iterator.next().equals("C")) {
        iterator.previous(); // Возвращаемся к позиции перед "C"
        iterator.add("B");   // Вставляем "B" перед "C"
        break;
    }
}
System.out.println(list); // Вывод: [A, B, C, D]

Практические рекомендации:

• Используйте LinkedList, если:
  • Преобладают операции вставки/удаления в начале, конце или середине (при использовании ListIterator).
  • Не требуется частый произвольный доступ по индексу (get(i)).
• Используйте ArrayList, если:
  • Преобладает чтение и доступ по индексу.
  • Вставки происходят преимущественно в конец списка.
  • Важна меньшая потребляемая память на элемент (т.к. LinkedList хранит дополнительные ссылки).