title: Complexity of List concatentation( ::: ) in Scala?
body: <p>I am reading Martin Odersky's Scala book and have come accross an example I just do not understand.
  So basically he is explaining how to implement an immutable queue data structure, that is backed by an immutable list.
  This is the code:</p>
  
  <pre><code>class SlowAppendQueue[T](elems: List[T]) {
    def head = elems.head
    def tail = new SlowAppendQueue(elems.tail)
    def enqueue(x: T) = new SlowAppendQueue(elems ::: List(x))
  }
  </code></pre>
  
  <p>He mentions that enqueue is an O(n) operation, as it takes time proptional to the number of elements in the queue.</p>
  
  <p>But why is the case? Is enqueue not just a matter of making the last element of the new List(x), which is also the first element as it has only one element, point to the head of elems? Which is an O(1) operation...</p>
  
  <p>Any help on clearing this up would be great thanks! </p>