I just read that the execution time of the append operation for a List (:+) grows linearly with the size of the List.

Appending to a List seems like a pretty common operation. Why should the idiomatic way to do this be prepending the components and then reversing the list? It can't also be a design failure as implementation could be changed at any point.

From my point of view, both prepending and appending should be O(1).

Is there any legitimate reason for this?

  • 3
    Depends on your definition of "legitimate". Scala is heavily into immutable data structures, ubiquitous anonymous lists, functional composition, etc. The default list implementation (without an extra mutable pointer to the list tail) works well for that style. If you need a more powerful list, at least it's very easy to write your own container which is almost indistinguishable from the standard ones. Nov 6, 2013 at 18:11
  • 1
    Cross site related - Appending an element to the end of a list in Scala - there is some bit in there about the nature of it. It appears that a list in scala is immutable, thus you need to copy it, which is O(N).
    – user40980
    Nov 6, 2013 at 18:12
  • You could use one of the many available mutable data structures, or immutable data structures with O(1) append time (Vector) that Scala provides. List[T] assumes you're using it the way you would in a pure functional language - generally working from the head with deconstruction and prepends.
    – KChaloux
    Nov 6, 2013 at 18:14
  • 3
    Prepending will put the next node pointer of the new head to the existing immutable list - which can't change. Thats O(1).
    – user40980
    Nov 6, 2013 at 18:31
  • 2
    For the seminal work and analysis on the general topic of data structure complexity measurements in pure FP have a read of Okasaki's thesis which was later published as a book. It's highly regarded and very good reading for anyone learning some FP to understand how to think about organizing data in FP. It's also well written and easy to read and follow so altogether a quality text. Nov 26, 2013 at 18:27

1 Answer 1


I'll expand my comment a bit. The List[T] data structure, from scala.collection.immutable is optimized to work the way an immutable list in a more purely functional programming language works. It has very fast prepend times, and it is assumed that you will be working on the head for almost all of your access.

Immutable lists get to have very fast prepend times due to the fact that they model their linked lists as a series of "cons cells". The cell defines a single value, and a pointer to the next cell (classic singly-linked-list style):

Cell [Value| -> Nil]

When you prepend to a list, you're really just making a single new cell, with the rest of the existing list being pointed to:

Cell [NewValue| -> [Cell[Value| -> Nil]]

Because the list is immutable, you're safe to do this without any actual copying. There's no danger of the old list changing and causing all the values in your new list to become invalid. However, you lose the ability to have a mutable pointer to the end of your list as a compromise.

This lends itself very well to recursively working on lists. Let's say you defined your own version of filter:

def deleteIf[T](list : List[T])(f : T => Boolean): List[T] = list match {
  case Nil => Nil
  case (x::xs) => f(x) match {
    case true => deleteIf(xs)(f)
    case false => x :: deleteIf(xs)(f)

That's a recursive function that works from the head of the list exclusively, and takes advantage of pattern matching via the :: extractor. This is something you see a lot of in languages like Haskell.

If you really want fast appends, Scala provides a lot of mutable and immutable data structures to choose from. On the mutable side, you might look into ListBuffer. Alternatively, Vector from scala.collection.immutable has a fast append time.

  • now I understand! It makes complete sense.
    – DPM
    Nov 6, 2013 at 18:28
  • I don't know any Scala, but isn't that else an infinite loop? I think it should be something like x::deleteIf(xs)(f).
    – svick
    Nov 6, 2013 at 18:59
  • @svick Uh... yes. Yes it is. I wrote it quickly and didn't verify my code, because I had a meeting to go to :p (Should be fixed now!)
    – KChaloux
    Nov 6, 2013 at 19:10
  • @Jubbat Because head and tail access with this kind of list is very fast - faster than using any hash-based map or array - it is an excellent type for recursive functions. This is one reason why lists are a core type in most functional languages (e.g. Haskell or Scheme)
    – itsbruce
    Nov 11, 2013 at 14:00
  • Excellent answer. I would perhaps add a TL;DR that simply says "because you should be prepending, not appending" (might help clear up the base assumptions most developers have about Lists and appending / prepending).
    – Daniel B
    Nov 27, 2013 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.