LinkedList - why no direct .next() on elements?

Question

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.

Answer 1

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.