Java: Is there a way to efficiently insert or remove many elements from the middle of a LinkedList?
- by allyourcode
I was expecting to find this in Java's LinkedList, since the point of linked lists is to be able to efficiently insert (and remove) anywhere (assuming you have some kind of pointer to the location where you want to insert or remove). I'm not finding anything in the API though. Am I overlooking something?
The closest thing I can find to this are the add and remove method in ListIterator. This has some limitations though. In particular, other iterators become invalid as soon as the underlying LinkedList is modified via remove, according to the API. This is born out in my tests as well; the following program results in a IllegalStateException:
import java.util.*;
public class RemoveFromLinkedList {
public static void main(String[] args) {
LinkedList<Integer> myList= new LinkedList<Integer>();
for (int i = 0; i < 10; ++i) {
myList.add(i);
}
ListIterator<Integer> i1 = myList.listIterator();
ListIterator<Integer> i2 = myList.listIterator();
for (int i = 0; i < 3; ++i) {
i1.next();
i2.next();
}
System.out.println("i1.next() should be 3: " + i1.next());
i1.remove();
i1.remove();
// Exception!
System.out.println("i2.next() should be 5: " + i2.next());
}
}
Ideally, what I'm expecting is something like this:
// In my imagination only. This is the way Java actually works, afaict.
// Construct two insertion/deletion points in LinkedList myLinkedList.
myIterator = myLinkedList.iterator();
for (...) {
myIterator.next();
}
start = myIterator.clone();
for (...) {
myIterator.next();
}
// Later...
after = myLinkedList.spliceAfter(myIterator, someOtherLinkedList);
// start, myIterator, and after are still all valid; thus, I can do this:
// Removes everything I just spliced in, as well as some other stuff before that.
myLinkedList.remove(start, after);
// Now, myIterator is invalid, but not start, nor after.
C++ has something like this for its list class (template). Only iterators pointing to moved elements become invalidated, not ALL iterators.
