Linked list: advantages of preventing movement of nodes and invalidating iterators on add/remove

Question

C++ and Java include native classes for linked lists, C++ std::list and Java LinkedList

For C++ std::list, nodes can be "moved" within a list, or from list to list (if the lists are compatible), via std::list::splice(), which in turn is used by std::list::merge() and std::list::sort().

With Java's native LinkedList, there is no method like splice() to move nodes. Attempting to emulate splice() by using listiterator add(element) and listiterator remove() methods doesn't work because add or remove will invalidate all iterators for a list other than the iterator used to do the add or remove. The indexed based get(index), add(index, element) and remove(index) functions could be used, but have time complexity O(n).

As for C++ std::list versions of add and remove, note that std::list::insert() doesn't invalidate any iterators, and std::list::erase only invalidates iterators that point to deleted nodes, and depending on the compiler, iterator invalidation may only occur with a debug build, while a release build (meant for speed) will not invalidate any iterators.

I ran into this issue with an SE question about implementing a merge sort with Java's native LinkedList. With C++, merge sort can be implemented using iterators using either top down (uses stack to store iterators) or bottom up (uses small (26 to 32) array of iterators), both of which sort a list by moving nodes within the original list via splice(), using the iterators as pointers to sorted run boundaries.

Why does Java's native LinkedList not include a splice method?

---

Some background on C++ and Java linked lists:

C++ std::list is usually implemented as a doubly linked list. I'm not aware of any exceptions to this, but it's possible since the standard doesn't require specific implementations. std::list is a standalone class. Visual Studio implements std::list as a circular doubly linked list with a dummy node. std::list::end is an iterator to the dummy node.

Java LinkedList is always implemented as a doubly linked list, and part of the ArrayList family of classes.

Answer 1

I think this is due to the differences in the philosophy underlying the design of both programming languages. The C++ philosophy allows data structures to cause undefined behavior as soon as the user violates an invariant, while Java wants to avoid that in all cases. Java aims to raise exceptions when invariants are broken, or, when that can not be detected, to allow unspecified results when the invariant is broken.

This is not just a "C++ vs Java" difference, but a general difference in programming languages between the philosophies "undefined behavior can happen if you're not careful" and "undefined behavior can't happen, ever, and I'll try hard to report errors at runtime".

Existing iterators, being pointers to nodes, are not invalidated by moving, adding, or removing nodes, as long as the iterators don't point to nodes that are later deleted.

The last part is crucial. C++ can say "iterators are invalidated", while Java wants to detect if those are used after they are invalidated (and raise an exception).

Detection can be expensive, and require each list to be aware of the iterators that are currently scanning the list, so that they can be checked and possibly flagged as invalid. Each list object should have a list of (weak references to) all the active iterators, and check whether they refer to deleted list cells.

Since this would impact performance, a simpler approach is to invalidate all the iterators every time the list is modified. This can be done by storing a single number in both list and its iterators. When the iterator is created, the number is copied from the list. When the list is modified, the number is incremented. When the iterator is used, we quickly compare the two numbers, and throw if they differ.

This is reasonably cheap, even if it's suboptimal because it invalidates all iterators, when that is not really necessary.

There is some middle ground between these two approaches. A Java library could avoid undefined behavior, and allow the list to be in an invalid state when the invariant is broken, but allow iterators to remain valid in more cases (without trying to check this). This means that all list methods can potentially throw, or produce invalid results, including failing to terminate. Debugging can be quite hard in such conditions, but that's the price to pay when invariants are not checked early at runtime.