I want to find out how to efficiently insert an element between two elements in a list in Java. For example:
[0, 5, 5, 1]
would become
[0, 5, 4, 5, 1]
where 4 has been inserted into the list.
What is the recommended way to implement this (as opposed to copying every single element into a new list?)
Use List<E>#add(int, E) to specify the position at which an element will be added to a list.
Inserts the specified element at the specified position in this list (optional operation). Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
So, following your example (using Guava for convenience):
List<Integer> foo = Lists.newArrayList(0, 5, 5, 1);
foo.add(2, 4);
System.out.println(foo); // prints [0, 5, 4, 5, 1]