3

I never understood this: why is it that I can't seem to find a core collections api somewhere that Allows me to retrieve elements that have a direct .next() or .previous() method on them without all the boilerplate or having to implement my own version of a LinkdList. The benefit? I can iterate directly over my returned elements without the need of an iterator, which seems to me one possible main motivator of having a LinkedList in the first place.

class Link { ... }
LinkedList<Link> linksByPosition = ...
Map<String,Link> linksByName = ...
Link linkWithName = linksByName.get("name");
Link nextLink = ??? // Do you get how complex it is?

Do you get how complex the ??? might be? I need to consider a scan through every element to find the matching one first to know at what position it is, before I can get the next one ...

Now consider this altered form, with a SmarterLinkedList that returns me implements of a predefined LinkdListNode.

class Link extends AbstractLinkedListNode<Link> { ... }
SmarterLinkedList<Link> linksByPosition = ...
Map<String,Link> linksByName = ...
Link linkWithName = linksByName.get("name");
Link nextLink = linkWithName.next();

If internally, it is already tracking the linking, why would you not want to expose that part of the API to the developer? It seems to me endlessly useful?

Now lets say, I will make the requirements a little complexer, now I also want to append an item right after the one I am holding. In the first version of the code, while searching for the matching Link, I can also maintain an index so I know at which point to insert. This way I can call the LinkedList.add(index+1,newLink) method. You know what this is doing behind the scenes right? Yes, internally, it again iterates to the right position index+1 times until it reaches the right position for the insertion.

However if the LinkedListNode also requires me to expose methods for insertAfter, insertBefore, removeSelf ... makes it more powerful, would it not?

UPDATE

It seems already that the consensus is going to be 'implement one your own'. But I am thinking 'too much boilerplate code' that can be avoided without overly risking exposing node management innards.

I hope that eventually someone will stumble upon this, and tell me that there is something that does exactly offer that.

  • add doesn't work the way you think it does. (see grepcode). – user40980 Mar 11 '16 at 3:25
  • You are looking at the wrong add - see correct grepcode, where it does exactly what I think it does. I am refering to the add(index,element) method, not the add(element) method. – YoYo Mar 11 '16 at 3:28
  • If you find yourself wanting to perform indexed inserts or retrieval, might I suggest that LinkedList isn't the datastructure you should be using? ArrayList does that job fine. LinkedList is better suited for sequential access and head/tail insertion, as you seem to be aware. – Chris Cooper Mar 15 '16 at 16:21
12

It is exposed.

That's an Iterator.

Exposing the innards of the implementation however, breaks the encapsulation of the class. The how it's implemented is under the covers - singly linked, doubly linked, dequeue (incidentally, the implementation changed from Java 1.5 to 1.6 with the addition of the Deque interface), stream accessible (it slightly changed again between 1.6 and 1.8).

The iterator is exposed. If you want to iterate over that, it's there. If you want to implement your own linked list (and I have in the past for exactly this reason - to be able to get access to the underlying representation and work with it), it isn't that hard to do.

Providing access to the underlying Node (or Entry depending on version of Java) class would mean that the LinkedList itself could enter an inconsistent state. In particular, the LinkedList knows the start and end elements. It has the ability to remove first, remove last, get last, get first and so on (all part of the deque). Providing access to the node would mean that someone else may unlink the head, or change the size (size() in LinkedList is returning a value - not counting all the nodes).

If you don't know where the end of the list is, add(E e) (add at the end of the list) becomes O(n) instead of O(1). If you don't know how big the list is through access via LinkedList.add(E e), the size() method becomes O(n) rather than O(1). These are important guarantees about how the List works.

Then there is also the issue of synchronizing the list. This can be done by restricting the add and remove type methods on the list itself. Giving access to the underlying class and all the guarantees about how synchronization work goes out the window because you no longer control the synchronization of add and remove on each element.

  • I get all this with encapsulation, and how sun/oracle structured their Collection libraries. A lecture well given - but it doesn't help me. And I also considered the iterator. However in having methods that return me an Iterator rather than elements, just so I can get to the next element, is highly dangerous: Iterators carry state as to which position they are at. Iterators are modified while traversing. – YoYo Mar 11 '16 at 3:36
  • It isn't too hard to write your own LinkedList that gives you the nodes. But the guarantees that the java.util.LinkedList provides make it necessary to hide that structure from you. – user40980 Mar 11 '16 at 3:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.