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.
std::list
have to be implemented as a linked list? What about Java'sLinkedList
(sometimes names don't say what's in the tin)? $\endgroup$