2

I'm no data structures expert, but as I understand it linked lists have proven to be quite inefficient in most scenarios mostly due to cache misses. One of the few reasons I would ever consider using them is for the unique ability to merge/split two of them in constant time; yet the class doesn't provide such a method.

I thought, all right, I will implement my own to fit my needs. I wanted the new class to follow the Collections framework API so I had it implement and extend the very same classes the standard LinkedList did. Soon I realized that I was just recreating LinkedList and all of this was pointless. At that point I might as well just copy paste the code and add the methods that I need.

On the same note, I can't find a reason (besides perhaps thread-safety which I am far from fully grasping yet) why there isn't such a method. Everything seemed like a standard linked list implementation and a method similar to splice() from the C++ STL could fit in there.

Am I missing something?

LinkedList<Integer> list1 = new LinkedList();
list1.add(4); 
list1.add(2);
list1.add(7);
// list1 = {4 , 2 , 7}

LinkedList<Integer> list2 = new LinkedList();
list2.add(9);
list2.add(4);
list2.add(6);
// list2 = {9 , 4 , 6}

list1.join(list2); // in O(1)
// at this point list2 should be invalidated/empty
// list1 = {4 , 2 , 7 , 9 , 4 , 6}
// list2 = {}
John Kugelman
  • 349,597
  • 67
  • 533
  • 578
fvalasiad
  • 173
  • 1
  • 10
  • 1
    Are you asking how to add another List’s elements into a List at a particular index in that List? You may want to edit your question and add a simple example/illustration of what a List’s elements would look like before and after the operation you’re describing. – VGR May 19 '21 at 11:52
  • 1. the Java collections framework isn't trying to solve *all* possible collection-related issues (see the absence of primitive-valued collections as an example). 2. this operation doesn't fit neatly into the other operations which always only modify one of the lists. This operation would leave the second list either empty or unusable. Unusable is even worse, because that's not a state that Java Collections usually find themselves in. – Joachim Sauer May 19 '21 at 12:11
  • I understand that collections should follow some rules to actually make them easier to use and more generic , but throwing out such an operation from linked lists seems as damaging as throwing out searching in HashTables . Shouldn't we value efficiency above all? – fvalasiad May 19 '21 at 12:18
  • 2
    Efficiency above all? Absolutely not. Readability and usability are at least as important, especially for Java. And the operation that you describe isn't even as frequent as you seem to think it is (and doing the "wrong" way is probably not as slow as you think it is). And I have no idea what you mean about HashTable. Note that even the author of `LinkedList` doesn't use it ([source](https://twitter.com/joshbloch/status/583813919019573248)). [`ArrayList` straight up behaves better in most circumstances](https://stackoverflow.com/questions/322715). – Joachim Sauer May 19 '21 at 12:29
  • @JoachimSauer mind posting that as an answer? – fvalasiad May 19 '21 at 12:43
  • @fvalasiad: I don't feel like this rises to the level of objectively correct information to be worth posting, but if you like feel free to copy/paste and edit as appropriate to post as an answer yoursefl. – Joachim Sauer May 19 '21 at 12:44
  • 2
    Did you spot *any* method in `LinkedList` exploiting the advantages of linked lists? – Holger May 19 '21 at 13:50
  • @Holger LinkedList methods no . Even if someone points out that pushing/removing from front/end is more efficient than an array i still don't consider that a major advantage since i'd pick an ArrayDeque or even better an `std::deque` java implementation which i bet will perform better . LinkedList iterators though have the advantage of performing O(1) Insertions next to them and that is something the previous two data structures i mentioned can't do . – fvalasiad May 19 '21 at 14:04
  • 2
    Exactly. Changing the head is not a major advantage and any other update not at the head or tail requires an O(n) traversal. Even worse, list iterators which could remember a reference to a node for O(1) insertions or removals get invalidated when a structural change is made through a different iterator. So, maintaining two or more list iterators to transfer elements from one position to another without traversal does not work. And there’s no dedicated API for any O(1) link manipulation. – Holger May 19 '21 at 15:46
  • @Holger I wasn't even aware that iterators get invalidated , what's the point of using linked lists in the first place at this point . You saved me from a lot of future bugs . Better off creating my own implementation to use i guess . – fvalasiad May 19 '21 at 16:04
  • 2
    @fvalasiad - As you've commented, you can create your own implementation of a single or double linked list, using references to nodes in lieu of iterators, and pretty much duplicate C++ std::list functionality. – rcgldr May 19 '21 at 16:29
  • @rcgldr I'm planning to implement both versions and also more data structures like std::deque , trees , etc . Duplicating c++ collections won't work perfectly though because we are lacking the algorithms header , perhaps we could make an Algorithms static class in java which will contain all of those methods , doesn't seem like java code though . – fvalasiad May 19 '21 at 16:37
  • 2
    I’d say, the `LinkedList` was more of a proof-of-concept, to demonstrate that it is possible to implement `List` in a different way than `ArrayList` (prior to the Collection API of JDK 1.2 there only was the array based `Vector`). [This statement](https://twitter.com/joshbloch/status/583813919019573248) of the author says it all… – Holger May 19 '21 at 16:39

1 Answers1

2

Java's implementation of native linkedlist has issues. There's no way to move nodes within a list or between lists, no equivalent to C++ std::list::splice(). All iterators to a link list become invalidated if there is an insertion or a deletion of a node anywhere in a linked list, except for the case where delete is done using an iterator parameter, in which case all iterators but the one used to do the insert or delete are invalidated. Iterators can't be shallow copied, assignment just points the destination iterator to the same iterator object pointed to by the source iterator.

These issues make operations like merging or merge sort difficult, even more so for an iterator based operation.

In the case of Visual Studio C++ std::list, deletion of nodes only invalidates iterators to deleted nodes, and only in a debug build. In a release build, no iterators are invalidated, and it's up to the programmer to ensure deleted nodes don't result in iterators pointing to deleted objects.

As for why Java's native linkedlist has these limitations, Sun's stated reason at the time is they wanted a "compact framework" rather than be consistent with C++, which predates Java collections by 4 years (1998 for Java collections, 1994 HP copyright date shown at the end of most or all STL include files in the case of Visual Studio 2005 and prior versions of Microsoft and other C++ compilers). This is in spite of the fact that one of the predecessors to collections, JGL, did have the goal of being consistent with C++.

https://en.wikipedia.org/wiki/Java_collections_framework#History

There are other criticisms of Java, such as not having unsigned integers, treating primitives and objects differently, with a limited set of operations for primitives, ...

rcgldr
  • 27,407
  • 3
  • 36
  • 61
  • I don't see how this answers the question of *why*. – Joachim Sauer May 19 '21 at 20:29
  • 1
    @JoachimSauer - I updated my answer to include Sun's choice, but I question if a "compact framework" is a valid reason to give up functionality, especially when one of the pre-collection implementations, JGL, had the goal of being consistent with C++ and it's STL. – rcgldr May 19 '21 at 21:15
  • 1
    "unless the insert or delete is done using an iterator" you can't insert using an `Iterator`. Only delete. With a `ListIterator`, you can also set, but you still can't insert. – Andy Turner Aug 18 '21 at 20:29
  • 1
    @AndyTurner - yet a further limitation. I still don't get the "why" they decided to do this, since it was implemented "properly" already with the prior JGL. I updated my answer. – rcgldr Aug 18 '21 at 23:31