Tweeted twitter.com/StackCompSci/status/1137464402091937792
13 added 153 characters in body
source | link

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. Data can be moved between nodes usingThe indexed based get(index), add(index, element) and setremove(index) functions could be used, but these are indexed base methods withhave time complexity O(index), and a data based merge sort normally requires O(n) space or a constant time slower in place merge sort such as block sort.

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.

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 add and 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. Data can be moved between nodes using get and set, but these are indexed base methods with time complexity O(index), and a data based merge sort normally requires O(n) space or a constant time slower in place merge sort such as block sort.

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.

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.

12 deleted 576 characters in body
source | link

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

For C++ std::list, nodes can be moved"moved" within a list, or from list to list (if the lists are compatible), via iterators and std::list::splice()std::list::splice(), which in turn is used by std::list::merge()std::list::merge() and std::list::sort(). 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 deletedstd::list::sort().

With Java's native LinkedListLinkedList, there is no method like splice() to move nodes,. Attempting to emulate splice() by using add and any addremove methods doesn't work because add or remove operationsremove will invalidate all iterators exceptfor a list other than the oneiterator used to do the addadd or remove, probably because the iterators include an index member, which in my opinion is a needless member. Something like std::next()remove could. Data can be used to convert an index into an appropriate iteratormoved between nodes using get and set, but these are indexed base methods with time complexity O(index), and a scan loop could be donedata based merge sort normally requires O(n) space or a constant time slower in place merge sort such as block sort.

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 convert andeleted nodes, and depending on the compiler, iterator into an indexinvalidation 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 will just movesort a list by moving nodes within the original list. This isn't possible with Java's LinkedList via splice(), using the iterators as pointers to sorted run boundaries.

Why does Java's linked list implementation have these limitations? What would it cost to allow movement of nodes and to allow add/remove calls that don't invalidate iteratorsnative LinkedList not include a splice method?

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

As noted above, C++ std::list::iterators are not invalidated by add or remove or splice operations (unless the iterator references a deleted node). std::list::splice allows nodes to be to be "moved" (relinked) within an existing list, and is used by std::list::sort to sort a list "in place". A set of iterators (on the stack for top down, in a small array for bottom up) are used by merge sort to track run boundaries, while std::splice() is used to "move" nodes within the original list to implement an in place merge sort.

Java's LinkedList doesn't have an equivalent to std::list::splice, and there is no method which allows nodes to be "moved" within a list. In addition, all java iterators for a list except the one used for add or remove are invalidated by an add or remove operation. So if trying to replace a move operation with an peek, add, remove, in addition to the overhead of creating and deletion of a node, indexing with O(index) time is required since the iterators are invalidated by add or remove. The alternative is to move the data between nodes (get / set) rather than "move" nodes, and would require an in place merge sort like block sort with additional constant time overhead, or a second list or array for a conventional merge sort.

In C++ std::list, nodes can be moved within a list, or from list to list (if the lists are compatible), via iterators and std::list::splice(), which in turn is used by std::list::merge() and std::list::sort(). 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.

With Java's native LinkedList, there is no method to move nodes, and any add or remove operations will invalidate all iterators except the one used to do the add or remove, probably because the iterators include an index member, which in my opinion is a needless member. Something like std::next() could be used to convert an index into an appropriate iterator, and a scan loop could be done to convert an iterator into an index.

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 will just move nodes within the original list. This isn't possible with Java's LinkedList.

Why does Java's linked list implementation have these limitations? What would it cost to allow movement of nodes and to allow add/remove calls that don't invalidate iterators?

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

As noted above, C++ std::list::iterators are not invalidated by add or remove or splice operations (unless the iterator references a deleted node). std::list::splice allows nodes to be to be "moved" (relinked) within an existing list, and is used by std::list::sort to sort a list "in place". A set of iterators (on the stack for top down, in a small array for bottom up) are used by merge sort to track run boundaries, while std::splice() is used to "move" nodes within the original list to implement an in place merge sort.

Java's LinkedList doesn't have an equivalent to std::list::splice, and there is no method which allows nodes to be "moved" within a list. In addition, all java iterators for a list except the one used for add or remove are invalidated by an add or remove operation. So if trying to replace a move operation with an peek, add, remove, in addition to the overhead of creating and deletion of a node, indexing with O(index) time is required since the iterators are invalidated by add or remove. The alternative is to move the data between nodes (get / set) rather than "move" nodes, and would require an in place merge sort like block sort with additional constant time overhead, or a second list or array for a conventional merge sort.

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 add and 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. Data can be moved between nodes using get and set, but these are indexed base methods with time complexity O(index), and a data based merge sort normally requires O(n) space or a constant time slower in place merge sort such as block sort.

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?

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

11 added 13 characters in body
source | link

In C++ std::list, nodes can be moved within a list, or from list to list (if the lists are compatible), via iterators and std::list::splice(), which in turn is used by std::list::merge() and std::list::sort(). 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.

With Java's native LinkedList, there is no method to move nodes, and any add or remove operations will invalidate all iterators except the one used to do the add or remove, probably because the iterators include an index member, which in my opinion is a needless member. Something like std::next() could be used to convert an index into an appropriate iterator, and a scan loop could be done to convert an iterator into an index.

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 will just move nodes within the original list. This isn't possible with Java's LinkedList.

Why does Java's linked list implementation have these limitations? What would it cost to allow movement of nodes and to allow add/remove calls that don't invalidate iterators?


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.

As noted above, C++ std::list::iterators are not invalidated by add or remove or splice operations (unless the iterator references a deleted node). std::list::splice allows nodes to be to be "moved" (relinked) within an existing list, and is used by std::list::sort to sort a list "in place". A set of iterators (on the stack for top down, in a small array for bottom up) are used by merge sort to track run boundaries, while std::splice() is used to "move" nodes within the original list to implement an in place merge sort.

JavaJava's LinkedList doesn't have an equivalent to std::list::splice, and there is no method which allows nodes to be "moved" within a list. In addition, all java iterators for a list except the one used for add or remove are invalidated by an add or remove operation. So if trying to replace a move operation with an peek, add, remove, in addition to the overhead of creating and deletion of a node, indexing with O(index) time is required since the iterators are invalidated by add or remove. The alternative is to move the data between nodes (get / set) rather than "move" nodes, and would require an in place merge sort like block sort with additional constant time overhead, or a second list or array for a conventional merge sort.

In C++ std::list, nodes can be moved within a list, or from list to list (if the lists are compatible), via iterators and std::list::splice(), which in turn is used by std::list::merge() and std::list::sort(). 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.

With Java's native LinkedList, there is no method to move nodes, and any add or remove operations will invalidate all iterators except the one used to do the add or remove, probably because the iterators include an index member, which in my opinion is a needless member. Something like std::next() could be used to convert an index into an appropriate iterator, and a scan loop could be done to convert an iterator into an index.

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 will just move nodes within the original list. This isn't possible with Java's LinkedList.

Why does Java's linked list implementation have these limitations? What would it cost to allow movement of nodes and to allow add/remove calls that don't invalidate iterators?


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.

As noted above, C++ std::list::iterators are not invalidated by add or remove or splice operations (unless the iterator references a deleted node). std::list::splice allows nodes to be to be "moved" (relinked) within an existing list, and is used by std::list::sort to sort a list "in place". A set of iterators (on the stack for top down, in a small array for bottom up) are used by merge sort to track run boundaries, while std::splice() is used to "move" nodes within the original list to implement an in place merge sort.

Java doesn't have an equivalent to std::list::splice, and there is no method which allows nodes to be "moved" within a list. In addition, all java iterators for a list except the one used for add or remove are invalidated by an add or remove operation. So if trying to replace a move operation with an peek, add, remove, in addition to the overhead of creating and deletion of a node, indexing with O(index) time is required since the iterators are invalidated by add or remove. The alternative is to move the data between nodes (get / set) rather than "move" nodes, and would require an in place merge sort like block sort with additional constant time overhead, or a second list or array for a conventional merge sort.

In C++ std::list, nodes can be moved within a list, or from list to list (if the lists are compatible), via iterators and std::list::splice(), which in turn is used by std::list::merge() and std::list::sort(). 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.

With Java's native LinkedList, there is no method to move nodes, and any add or remove operations will invalidate all iterators except the one used to do the add or remove, probably because the iterators include an index member, which in my opinion is a needless member. Something like std::next() could be used to convert an index into an appropriate iterator, and a scan loop could be done to convert an iterator into an index.

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 will just move nodes within the original list. This isn't possible with Java's LinkedList.

Why does Java's linked list implementation have these limitations? What would it cost to allow movement of nodes and to allow add/remove calls that don't invalidate iterators?


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.

As noted above, C++ std::list::iterators are not invalidated by add or remove or splice operations (unless the iterator references a deleted node). std::list::splice allows nodes to be to be "moved" (relinked) within an existing list, and is used by std::list::sort to sort a list "in place". A set of iterators (on the stack for top down, in a small array for bottom up) are used by merge sort to track run boundaries, while std::splice() is used to "move" nodes within the original list to implement an in place merge sort.

Java's LinkedList doesn't have an equivalent to std::list::splice, and there is no method which allows nodes to be "moved" within a list. In addition, all java iterators for a list except the one used for add or remove are invalidated by an add or remove operation. So if trying to replace a move operation with an peek, add, remove, in addition to the overhead of creating and deletion of a node, indexing with O(index) time is required since the iterators are invalidated by add or remove. The alternative is to move the data between nodes (get / set) rather than "move" nodes, and would require an in place merge sort like block sort with additional constant time overhead, or a second list or array for a conventional merge sort.

    Post Reopened by Gilles
10 rephrase the question so that it's primarily about data structure design rather than about the specific languages, to make it on-topic; minor presentation improvements
source | link
9 deleted 1 character in body
source | link
8 deleted 1 character in body
source | link
7 added 13 characters in body
source | link
6 added 1403 characters in body
source | link
5 added 1403 characters in body
source | link
4 edited tags
| link
3 clarify title
source | link
    Migration Rejected
    Post Unlocked by Community
    Post Locked by Community
    Post Migrated Away to stackoverflow.com by David Richerby, Evil, Raphael
    Post Closed as "off-topic" by David Richerby, Evil, Raphael
2 added 68 characters in body
source | link
1
source | link