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 add operations):1 -> 2 -> 3 -> 4and say I want to append a 5.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 3...Or in other words, to do an append, the entire list seems to need to be copied.My questions: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.
Is there any practical way for a linked node structure to be immutable?
java;immutability;linked list
With lists in functional languages, you nearly always work with a head and tail, the first element and the remainder of the list.  Prepending is much more common because, as you surmised, appending requires copying the entire list (or other lazy data structures that don't precisely resemble a linked list).In imperative languages, appending is much more common, because it tends to feel more natural semantically, and you don't care about invalidating references to previous versions of the list.As an example of why prepending doesn't require copying the entire list, consider you have:2 -> 3 -> 4Prepending a 1 gives you:1 -> 2 -> 3 -> 4But note that it doesn't matter if someone else is still holding a reference to 2 as the head of their list, because the list is immutable and the links only go one way.  There's no way to tell the 1 is even there if you only have a reference to 2.  Now, if you appended a 5 onto either list, you'd have to make a copy of the entire list, because otherwise it would appear on the other list as well.