I decided to write a singly-linked list, and had the plan going in to make the internal linked node structure immutable.
I ran into a snag though. Say I have the following linked nodes (from previous
1 -> 2 -> 3 -> 4
and say I want to append a
To do this, since node
4 is immutable, I need to create a new copy of
4, but replace its
next field with a new node containing a
5. The problem is now,
3 is referencing the old
4; the one without the appended
5. Now I need to copy
3, and replace its
next field to reference the
4 copy, but now
2 is referencing the old
Or in other words, to do an append, the entire list seems to need to be copied.
Is my thinking correct? Is there any way to do an append without copying the entire structure?
Apparently "Effective Java" contains the reccomendation:
Classes should be immutable unless there's a very good reason to make them mutable...
Is this a good case for mutability?
I don't think this is a duplicate of the suggested answer since I'm not talking about the list itself; that obviously has to be mutable to conform to the interface (without doing something like keeping the new list internally and retrieving it via a getter. On second thought though, even that would require some mutation; it would just be kept to a minimum). I'm talking about whether or not the internals of the list must be immutable.