Scala List's 'Prepend' Smartness

Do you remember Time Complexity and the ever complex O notation? Well if you do not let me remind you of that. Remember Semester 3 course Computer Algorithms? Well you got it. Wiki definition of Complexity says : "In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem."

If you have written those for loops which traverse lists or array to search an element in them or to add an element at the end you already know that the Time required to traverse a list grows with its size. Well what you were doing was a linear search and A linear search looks down a list, one item at a time, without jumping. In complexity terms this is an O(n) search - the time taken to search the list gets bigger at the same rate as the list does. It is true for implementations of Lists or Array's in programming languages.

Here Scala's List comes to your rescue. Scala's List type allows you to create an immutable list of items.

val oneTwoThree = List(1, 2, 3)

The most common operation on scala List is ‘::’, which is pronounced “cons.” Cons prepends a new element to the beginning of an existing list, and returns the resulting list. For example, if you run this script:

val twoThree = List(2, 3)
val oneTwoThree = 1 :: twoThree
println(oneTwoThree)

You’ll see:

List(1, 2, 3)

In the expression “1 :: twoThree”, :: is a method of its right operand, the list, twoThree. You might suspect there’s something amiss with the associativity of the :: method, but it is actually a simple rule to remember: If a method is used in operator notation, such as a * b, the method is invoked on the left operand, as in a.*(b)—unless the method name ends in a colon. If the method name ends in a colon, the method is invoked on the right operand. Therefore, in 1 :: twoThree, the :: method is invoked on twoThree, passing in 1, like this: twoThree.::(1).

The time it takes to append to a list grows linearly with the size of the list, whereas prepending with :: takes constant time. So in Scala whenever you want to work with a sequence of items or build it, if you use Scala List you could achieve building a list in Constant time no matter what is the size of the list.