Tweeted twitter.com/#!/StackProgrammer/status/633944105698127872
    Question Protected by gnat
3 Made the lines in the example into arrows
source | link

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 -> 4

and 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.

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 - 4

and 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.

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 -> 4

and 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.

2 Added details as to why this isn't a duplicate.
source | link

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 - 4

and 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.

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 - 4

and 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 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 - 4

and 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.

1
source | link

Is there any practical way for a linked node structure to be immutable?

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 - 4

and 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?