Tendo lido esta perguntaImutável ou não imutável? e lendo as respostas às minhas perguntas anteriores sobre a imutabilidade, ainda estou um pouco confuso sobre a implementação eficiente de LinkedList simples que é imutável. Em termos de array, parece ser fácil - copiar o array e retornar uma nova estrutura baseada nessa cópia.

Supostamente temos uma classe geral de nó:

<code>class Node{
    private Object value;
    private Node next;
}
</code>

E class LinkedList baseado no acima, permitindo que o usuário adicione, remova etc. Agora, como podemos garantir a imutabilidade? Devemos recursivamente copiar todas as referências para a lista quando inserimos um elemento?

Eu também estou curioso sobre respostas emImutável ou não imutável? isso menciona a otimização cerain que leva ao log (n) tempo e espaço com a ajuda de uma árvore binária. Além disso, eu li em algum lugar que adicionar um elem à frente é 0 (1) também. Isso me intriga muito, como se não fornecessemos a cópia das referências, então, na realidade, estamos modificando as mesmas estruturas de dados em duas fontes diferentes, o que quebra a imutabilidade ...

Alguma de suas respostas trabalharia em listas duplamente ligadas? Estou ansioso para quaisquer respostas / indicações para quaisquer outras perguntas / solução. Agradeço antecipadamente por sua ajuda.