Which data structure provides faster insertion of an element in the middle: ArrayList or LinkedList?

To insert an element into the middle of a list, a LinkedList usually provides a faster operation than an ArrayList.

The reason is:

• In ArrayList, inserting in the middle requires shifting all subsequent elements, which has a time complexity of O(n).
• In LinkedList, it is enough to change the links of neighboring nodes to insert an element, which takes O(1) if you have a reference to the node. However, finding this node takes O(n) if the reference is absent.

If you have a reference to the insertion position, LinkedList is faster; if not, both options are roughly equal in time due to the search requirement.

LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
ListIterator<Integer> it = list.listIterator(1); // insertion position
it.add(99); // insert in the middle