We would like to add this last feature, the ability to modify the list at both its head and its tail, to our mutable lists. With our current implementation, adding or removing elements at the end would require traversing the whole list from the front, and would be very inefficient for large lists. We are going to need to make a fundamental change in implementation strategy.
One possible new strategy is to define a new kind of list whose firsts and rests can be modified. For example, we might revise the MutList class Cons by adding get and set methods for the first and rest fields. To avoid confusion with our immutable Cons class, let us the renamed the Cons class Node. The weakness of this approach is that exposes the imperative character of the implementation to other classes: anyone with access to a Node can make changes to its fields. The imperative operations are no longer controlled by the MutList container, and we cannot guarantee that they will be used in a disciplined way.
We can avoid this problem by making Node a static private nested class. For example, we might write
class MutList {
static private class Node {
...
}
Node head;
Node tail;
....
}
Making Node a private nested class of MutList makes it inaccessible to classes outside. Only the methods of MutList can use Nodes, so once again we can control how and when imperative operations on lists are performed.