title: join two sequences in scala
body: <p>This is rewritten question. Previous one is unclear.</p>
  
  <p><strong>1) Introduction</strong></p>
  
  <p>I need some cool structure, that would <strong>store</strong> my values. I need that my cool structure can <strong>add</strong> items to it, and sometimes I need that my cool structure can <strong>fold</strong> containing elements into something based on passed <em>foldFunction</em> . Generally something like <code>scala.collection.immutable.List</code> is great, besides point 2.
  See this in action:</p>
  
  <pre><code>val coolContainer = 1 :: 2 :: 3 :: 4 :: Nil
  val folded = coolContainer.foldLeft("")((acc, curr)=&gt; acc + curr)
  </code></pre>
  
  <p>Yea! I got what I wanted - the shiny <code>"1234"</code> String :)</p>
  
  <p><strong>2) Additional requirements</strong>
  Then I want that my cool structure can be appended to another one. More over this is very important that such operation must be efficient because my program will mostly do such operations. Because of that, the "appending of two containers" algorithm with complexity <strong>O(1)</strong> is very expected.</p>
  
  <p>So, lets just try to append two Lists, one to another using standard way with the <code>++</code> function.</p>
  
  <pre><code>val locomotive = (1 to 1000000).toList
  val vehicle = (1000000 to 2000000).toList
  val train = locomotive ++ vehicle
  </code></pre>
  
  <p>So what is going here? As most of you probably know, the <code>List</code> in Scala Standard Library API is implemented as <em>head</em> prepended to <em>tail</em> where tail is another List. Finally the last element in list is prepended to empty List <code>Nil</code>. </p>
  
  <p>This architecture implies that if you join two lists using the <code>++</code> function, algoirithm under the hood will traverse <code>locomotive</code> through all elements until the last item and then replace the <em>tail</em> (which is the <code>Nil</code>) with the value of another List - with the <code>vehicle</code> in our example. The <strong>complexity is O(size_of_loclomotive)</strong>. Ehh, :/ I want it to be O(1).</p>
  
  <p>Finally the question. </p>
  
  <p><strong>Is there in scala container, that behaves similarly to the <code>List</code> and meets the above requirements?</strong></p>
  
  <hr>
  
  <p>Deprecated, old question. Just in case if you are just interested how it was reasked and don't.</p>
  
  <p>Basically I want to choose the best pair: structure and method for appending one sequence to another. The efficiency is the <strong>key</strong> in this scenario.</p>
  
  <p>Read below snipped to understand what I want to achieve but more efficient:</p>
  
  <pre><code>val seq1 = List(1,2,3)
  val seq2 = List(4,5,6)
  val seq3 = seq1 ++ seq2   //I am afraid that seq1 and seq2 will be traversed 
                            //what is not the most efficient way to join two seqs
  </code></pre>