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?

  • 2
    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. – Kilian Foth Nov 6 '13 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 '13 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 '13 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 '13 at 18:31
  • 1
    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. – Jimmy Hoffa Nov 26 '13 at 18:27

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.

| improve this answer | |
  • now I understand! It makes complete sense. – DPM Nov 6 '13 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 '13 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 '13 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 '13 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 '13 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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