71

I've recently started learning scala, and I've come across the :: (cons) function, which prepends to a list.
In the book "Programming in Scala" it states that there is no append function because appending to a list has performance o(n) whereas prepending has a performance of o(1)

Something just strikes me as wrong about that statement.

Isn't performance dependent on implementation? Isn't it possible to simply implement the list with both forward and backward links and store the first and last element in the container?

The second question I suppose is what I'm supposed to do when I have a list, say 1,2,3 and I want to add 4 to the end of it?

1
  • 4
    "Isn't performance dependent on implementation?": don't forget that List is a concrete class in Scala, and has nothing to do with the Java List interface. Jul 29, 2014 at 16:19

5 Answers 5

83

The key is that x :: somelist does not mutate somelist, but instead creates a new list, which contains x followed by all elements of somelist. This can be done in O(1) time because you only need to set somelist as the successor of x in the newly created, singly linked list.

If doubly linked lists were used instead, x would also have to be set as the predecessor of somelist's head, which would modify somelist. So if we want to be able to do :: in O(1) without modifying the original list, we can only use singly linked lists.

Regarding the second question: You can use ::: to concatenate a single-element list to the end of your list. This is an O(n) operation.

List(1,2,3) ::: List(4)
2
  • 2
    what is the complexity of ::: ?
    – Jus12
    Sep 2, 2011 at 11:35
  • 6
    @Jus: The runtime complexity of ::: is O(n) where n is the length of the first list. So you definitely shouldn't do that in a loop.
    – sepp2k
    Sep 2, 2011 at 11:41
22

Other answers have given good explanations for this phenomenon. If you are appending many items to a list in a subroutine, or if you are creating a list by appending elements, a functional idiom is to build up the list in reverse order, cons'ing the items on the front of the list, then reverse it at the end. This gives you O(n) performance instead of O(n²).

15

Since the question was just updated, it's worth noting that things have changed here.

In today's Scala, you can simply use xs :+ x to append an item at the end of any sequential collection. (There is also x +: xs to prepend. The mnemonic for many of Scala's 2.8+ collection operations is that the colon goes next to the collection.)

This will be O(n) with the default linked implementation of List or Seq, but if you use Vector or IndexedSeq, this will be effectively constant time. Scala's Vector is probably Scala's most useful list-like collection—unlike Java's Vector which is mostly useless these days.

If you are working in Scala 2.8 or higher, the collections introduction is an absolute must read.

12

Prepending is faster because it only requires two operations:

  1. Create the new list node
  2. Have that new node point to the existing list

Appending requires more operations because you have to traverse to the end of the list since you only have a pointer to the head.

I've never programmed in Scala before, but you could try a List Buffer

1
  • Notice that in order not to traverse to the end, one could have a pointer to the tail. But than, you would have to change the pointer in the last element. That would require further operations to be made (e.g. copy of element(s)) since List is immutable in Scala, as mentioned in other answers. Jul 5, 2018 at 14:58
6

Most functional languages prominently figure a singly-linked-list data structure, as it's a handy immutable collection type. When you say "list" in a functional language, that's typically what you mean (a singly-linked list, usually immutable). For such a type, append is O(n) whereas cons is O(1).

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

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

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