Why does LinkedList not expose its Node class?

If I develop the linked list from scratch, I can store a pointer to a Node object inside my business entity class and achieve constant O(1) remove and insertAfter operations. In the java standard library implementation, they are O(n) which can differ tremendously when processing large data sets.

Why don’t they just made the Node class public and encapsulated some details inside it still making the class itself (via interface maybe) accessable? It would make LinkedList more flexible.

Do we have something like FlexibleLinkedList in Apache Commons or Guava?

Answer

ListIterator

Why don’t they just made the Node class public and encapsulated some details inside it still making the class itself (via interface maybe) accessable?

There is no need to.

Why don’t they just made the Node class public and encapsulated some details inside it still making the class itself (via interface maybe) accessable? It would make LinkedList more flexible.

That already exists.

If you want to have the benefits of node-based operations, like:

• Give me the next item, based on current node
• Delete the node I already have, without locating it
• Insert something after my node that I already have

you just have to use a ListIterator as returned by list.listIterator(). This method is offered by all Lists.

This class encapsulates the logic of knowing the current node in an iteration and offers efficient methods for manipulation that directly use the Nodes, such as:

• add – The element is inserted immediately before the element that would be returned by next()
• set – Replaces the last element returned by next() or previous() with the specified element
• remove – Removes from the list the last element that was returned by next() or previous()

While offering methods to control the iteration with next() and previous().

---

Example

So you could for example change every second element:

LinkedList<Integer> values = new LinkedList<>(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));

int i = 0;
ListIterator<Integer> iter = values.listIterator();
while (iter.hasNext()) {
    iter.next();

    if (i % 2 == 0) {
        iter.set(100);
    }

    i++;
}

Resulting in

[100, 2, 100, 4, 100, 6, 100, 8, 100, 10]

And this code runs in O(n), it does not need to re-locate the nodes each time. In contrast to the bad equivalent of

for (int i = 0; i < list.size(); i++) {
    if (i % 2 == 0) {
        list.set(i, 100);
    }
}

which runs in O(n^2) for the reasons you have stated.

---

Benefits of hiding Node

In general, it is much better to encapsulate and hide your private inner workings. An user should not bother how LinkedList does its job behind the curtain.

Also, if it would expose the Node, an user could sneakily edit them and the whole list goes bonkers.

For example an user could then do

Node a = list.getNodeAtIndex(3);   
Node b = a.next;
Node c = b.next;

// Remove b
a.next = c;
c.previous = a;

Without also adjusting the size of the list. So list.size() would return a wrong number now, probably leading to crashes during iterations.

Or you could also introduce a dangerous loop:

a.next = b;
b.next = a;

Or forget to set previous, resulting in a different list when iterated backwards:

a.next = c;
c.previous = b;

---

ListIterator ensures that such stuff can not happen, while offerring the same functionality. So instead of exposing the nodes directly to the user, it exposes only the desired functionality, in form of methods for which it has full control over.