title: Efficient implementation of immutable (double) LinkedList
body: <p>Having read this question <a href="https://stackoverflow.com/questions/9009627/immutable-or-not-immutable">Immutable or not immutable?</a> and reading answers to my previous questions on immutability, I am still a bit puzzled about efficient implementation of simple LinkedList that is immutable. In terms of array tha seems to be easy - copy the array and return new structure based on that copy.</p>
  
  <p>Supposedly we have a general class of Node:</p>
  
  <pre><code>class Node{
      private Object value;
      private Node next;
  }
  </code></pre>
  
  <p>And class LinkedList based on the above allowing the user to add, remove etc. Now, how would we ensure immutability? Should we recursively copy all the references to the list when we insert an element?</p>
  
  <p>I am also curious about answers in <a href="https://stackoverflow.com/questions/9009627/immutable-or-not-immutable">Immutable or not immutable?</a> that mention cerain optimization leading to log(n) time and space with a help of a binary tree. Also, I read somewhere that adding an elem to the front is 0(1) as well. This puzzles me greatly, as if we don't provide the copy of the references, then in reality we are modifying the same data structures in two different sources, which breaks immutability...</p>
  
  <p>Would any of your answers alo work on doubly-linked lists? I look forward to any replies/pointers to any other questions/solution. Thanks in advance for your help.</p>