Habiendo leído esta pregunta¿Inmutable o no inmutable? y al leer las respuestas a mis preguntas anteriores sobre la inmutabilidad, todavía estoy un poco desconcertado acerca de la implementación eficiente de LinkedList simple que es inmutable. En términos de matriz, esto parece ser fácil: copie la matriz y devuelva la nueva estructura basada en esa copia.

Supuestamente tenemos una clase general de Nodo:

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

Y la clase LinkedList, basada en lo anterior, permite al usuario agregar, eliminar, etc. Ahora, ¿cómo aseguraríamos la inmutabilidad? ¿Deberíamos copiar recursivamente todas las referencias a la lista cuando insertamos un elemento?

También tengo curiosidad por las respuestas en¿Inmutable o no inmutable? que mencionan la optimización de cerain que lleva a registrar (n) el tiempo y el espacio con la ayuda de un árbol binario. Además, leí en alguna parte que agregar un elemento al frente es también 0 (1). Esto me desconcierta enormemente, ya que si no proporcionamos la copia de las referencias, en realidad estamos modificando las mismas estructuras de datos en dos fuentes diferentes, lo que rompe la inmutabilidad ...

¿Alguna de sus respuestas también funcionaría en listas doblemente enlazadas? Espero cualquier respuesta / puntero a cualquier otra pregunta / solución. Gracias de antemano por tu ayuda.