Replacing a sublist with another list in Java in constant time

Question

Is there a List-like container in Java that provides the capability of replacing a sublist with another list in constant time, given an iterator to the start and end of the sublist?

For example I could do the following:

List<T> l1, l2;
ListIterator<T> i1, i2;

// Initialize the above variables correctly...

l1.replace(i1, i2, l2);

If I was rolling my own linked list, this would be easy so I'd assume this is a feasible task using Collections.

Thanks in advance!

Answer 1

No, there's no way to do this in constant time using the built-in APIs.

If I was rolling my own linked list, this would be easy so I'd assume this is a feasible task using Collections.

Not quite. Even rolling your own implementation, you can't do this in constant time in a way that

• would only change l1, not l2
• would let you do the same operation more than once, perhaps with l3 and l2

It is easy to imagine that if this were built into the JDK APIs, these problems could result in accidental behavior that was really unpleasant to debug.

Answer 2

Take a look at the AbstractList.html#addAll.