Для эффективного добавления элементов в середину структуры в Java лучше всего подходит коллекция LinkedList.

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

Пример использования LinkedList:

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("D");

// Вставим "C" в позицию 2 (между B и D)
list.add(2, "C");

System.out.println(list); // [A, B, C, D]

Если же нужно часто обращаться к элементам по индексу, стоит учитывать, что LinkedList имеет доступ O(n), в отличие от ArrayList с O(1).

Какой тип коллекции лучше всего подходит для эффективного добавления элементов в середину структуры?