What type of collection is preferred for quick addition of elements in the middle of the data structure?

For quick insertion of elements into the middle of a data structure in Java, the LinkedList collection is preferred. Unlike ArrayList, where inserting in the middle requires shifting elements and has a complexity of O(n), LinkedList is implemented as a doubly linked list, which allows inserting elements in O(1) if the node's position is known (or O(n) for searching the position).

Example of using LinkedList:

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
// Insert element "C" in the middle
ListIterator<String> iterator = list.listIterator(1);
iterator.add("C");

Thus, for frequent insertions in the middle, it is better to use LinkedList.