In which data structure is inserting an element in the middle faster: ArrayList or LinkedList?

Inserting an element in the middle is faster in LinkedList than in ArrayList, if we only consider the insertion operation.

The reason is:

• In ArrayList, elements are stored in an array, so inserting in the middle requires shifting all subsequent elements to the right, which takes O(n) time.

• In LinkedList, elements are linked by references, so it is enough to change the links of neighboring nodes to insert a new element, which takes O(1) for the insertion itself, but finding the position for insertion is O(n).

Thus, if you already have a reference to the desired node, insertion in LinkedList is faster. But if you need to find the position first, the time is roughly the same.

Example:

List<String> list = new LinkedList<>();
// adding elements
list.add("a");
list.add("b");
list.add("c");

// inserting in the middle
list.add(1, "x");