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
remove will invalidate all iterators for a list other than the iterator used to do the
remove. The indexed based
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.